Memory Layout Comparison Array vs Linked List in DSA C - Complexity Comparison

Time Complexity: Memory Layout Comparison Array vs Linked List

O(1) for array access, O(n) for linked list access

Understanding Time Complexity

We want to understand how the memory layout of arrays and linked lists affects the speed of accessing elements.

How does the way data is stored impact the time it takes to find or use elements?

Scenario Under Consideration

Analyze the time complexity of accessing elements in array and linked list.

// Access element at index i in array
int getArrayElement(int arr[], int i) {
    return arr[i];
}

// Access element at index i in linked list
int getLinkedListElement(Node* head, int i) {
    Node* current = head;
    int count = 0;
    while (current != NULL && count < i) {
        current = current->next;
        count++;
    }
    if (current == NULL) return -1; // not found
    return current->data;
}
    

This code shows how we get the element at position i in an array and in a linked list.

Identify Repeating Operations

Look at what repeats when accessing elements.

• Primary operation: For array, direct access with no loop; for linked list, a loop moves through nodes.
• How many times: Array accesses once; linked list loops i times to reach element.

How Execution Grows With Input

Accessing an element in an array stays fast no matter the size.

Accessing an element in a linked list takes longer as the position i grows.

Input Size (n)	Array Access Steps	Linked List Access Steps (worst case i=n)
10	1	10
100	1	100
1000	1	1000

Pattern observation: Array access time stays the same; linked list access time grows linearly with position.

Final Time Complexity

Time Complexity: O(1) for array access, O(n) for linked list access

Array access is instant because elements are stored together; linked list access takes longer because we must follow links one by one.

Common Mistake

[X] Wrong: "Accessing any element in a linked list is as fast as in an array."

[OK] Correct: Linked lists store elements separately, so you must move through nodes one at a time, making access slower for far elements.

Interview Connect

Understanding these differences helps you choose the right data structure and explain your choices clearly in interviews.

Self-Check

"What if the linked list was doubly linked? How would that affect the time complexity of accessing elements?"