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?"

Practice

1. Which of the following best describes the memory layout of an array compared to a linked list?

easy

A. Array elements are scattered in memory, while linked list nodes are stored contiguously.

B. Array elements are stored in contiguous memory locations, while linked list nodes are scattered in memory.

C. Both array and linked list nodes are stored contiguously in memory.

D. Both array and linked list nodes are scattered randomly in memory.

Solution

1. Step 1: Understand array memory layout

   Arrays store elements in contiguous memory blocks, meaning all elements are next to each other.

2. Step 2: Understand linked list memory layout

   Linked list nodes are allocated separately and linked by pointers, so they can be scattered anywhere in memory.

3. Final Answer:

   Array elements are stored in contiguous memory locations, while linked list nodes are scattered in memory. -> Option B

4. Quick Check:

   Array = contiguous, Linked List = scattered [OK]

Hint: Arrays use continuous memory; linked lists use scattered nodes [OK]

Common Mistakes:

• Thinking linked list nodes are stored contiguously
• Confusing array and linked list memory layouts
• Assuming both use the same memory pattern

2. Which C declaration correctly defines a linked list node struct with an integer data and a pointer to the next node?

easy

A. typedef struct Node { int data; struct Node* next; } Node;

B. typedef struct Node { int data; int* next; } Node;

C. typedef struct Node { int data; Node* next; } Node;

D. typedef struct Node { int data; struct Node next; } Node;

Solution

1. Step 1: Check pointer to next node type

   The next pointer must be of type 'struct Node*' to point to the next node's address.

2. Step 2: Validate struct syntax

   Using 'struct Node* next;' inside the struct is correct. Using 'Node* next;' without typedef before is invalid here.

3. Final Answer:

   typedef struct Node { int data; struct Node* next; } Node; -> Option A

4. Quick Check:

   Pointer to struct Node = struct Node* [OK]

Hint: Use 'struct Node*' inside struct before typedef completes [OK]

Common Mistakes:

• Using 'int* next' instead of pointer to struct
• Using 'Node* next' before typedef is complete
• Declaring 'struct Node next' causing infinite size

3. Consider the following C code snippet:

int arr[3] = {10, 20, 30};
struct Node {
  int data;
  struct Node* next;
};
struct Node n1 = {10, NULL};
struct Node n2 = {20, NULL};
n1.next = &n2;
printf("%d %d\n", arr[1], n1.next->data);

What is the output?

medium

A. 20 20

B. 10 20

C. 20 10

D. 10 10

Solution

1. Step 1: Identify arr[1] value

   arr[1] is the second element of array, which is 20.

2. Step 2: Identify n1.next->data value

   n1.next points to n2, whose data is 20.

3. Final Answer:

   20 20 -> Option A

4. Quick Check:

   arr[1] = 20, n1.next->data = 20 [OK]

Hint: Array index 1 and linked list next node data both 20 [OK]

Common Mistakes:

• Confusing array index starting at 0
• Misreading pointer access syntax
• Assuming n1.next->data is 10 instead of 20

4. The following code attempts to create a linked list node but causes a runtime error. What is the main issue?

struct Node {
  int data;
  struct Node* next;
};

struct Node* createNode(int val) {
  struct Node node;
  node.data = val;
  node.next = NULL;
  return &node;
}

medium

A. Not initializing the data field before returning.

B. Missing memory allocation with malloc for the node.

C. Returning address of a local variable which becomes invalid after function ends.

D. Incorrect struct pointer type in return statement.

Solution

1. Step 1: Analyze variable lifetime

   The variable 'node' is local to createNode function and is destroyed when function returns.

2. Step 2: Understand pointer return issue

   Returning address of local variable leads to invalid pointer and undefined behavior.

3. Final Answer:

   Returning address of a local variable which becomes invalid after function ends. -> Option C

4. Quick Check:

   Local variable address returned = invalid pointer [OK]

Hint: Never return address of local variables from functions [OK]

Common Mistakes:

• Assuming pointer remains valid after function ends
• Ignoring need for dynamic memory allocation
• Confusing pointer types in return

5. You want to store 1000 integers and frequently insert and delete elements in the middle. Considering memory layout and performance, which data structure is better and why?

1. Array
2. Linked List

hard

A. Linked List, because it stores elements contiguously for faster access.

B. Array, because contiguous memory improves cache performance despite costly insertions.

C. Array, because it uses less memory than linked list nodes with pointers.

D. Linked List, because scattered nodes allow fast insertions and deletions anywhere.

Solution

1. Step 1: Consider insertion and deletion costs

   Arrays require shifting elements for insert/delete in middle, which is slow.

2. Step 2: Consider linked list advantages

   Linked lists allow quick insert/delete by changing pointers without shifting elements.

3. Step 3: Consider memory layout tradeoff

   Linked list nodes are scattered, which may reduce cache speed but improve insertion/deletion speed.

4. Final Answer:

   Linked List, because scattered nodes allow fast insertions and deletions anywhere. -> Option D

5. Quick Check:

   Fast insert/delete middle = Linked List [OK]

Hint: Linked list excels at fast insert/delete in middle despite scattered memory [OK]

Common Mistakes:

• Choosing array for fast insert/delete in middle
• Ignoring pointer overhead in linked list
• Assuming linked list stores elements contiguously