Memory Layout Comparison Array vs Linked List in DSA C - Trade-offs & Analysis

Mental Model

Arrays store items one after another in a single block of memory. Linked lists store items scattered in memory, each pointing to the next.

Analogy: Imagine a row of mailboxes (array) all side by side on a street versus houses spread out in a neighborhood (linked list), where each house has a sign pointing to the next house.

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: Compare memory layout of array with elements 1,2,3 and linked list with nodes 1,2,3

Goal: Understand how elements are stored in memory for array vs linked list

Step 1: Visualize array elements stored contiguously

[1][2][3]

Why: Array elements are placed one after another in memory for fast access

Step 2: Visualize linked list nodes scattered with pointers

1 -> 2 -> 3 -> null

Why: Linked list nodes can be anywhere in memory but each node points to the next

Step 3: Note array memory addresses increase by fixed size

Addr 1000:1, Addr 1004:2, Addr 1008:3

Why: Array elements are stored in continuous memory blocks with fixed spacing

Step 4: Note linked list nodes have separate addresses

Node1 Addr 5000:1 + next->Addr 7000, Node2 Addr 7000:2 + next->Addr 9000, Node3 Addr 9000:3 + next->null

Why: Linked list nodes are scattered but linked by pointers

Result:

Array memory: [1][2][3] contiguous
Linked list memory: scattered nodes 1 -> 2 -> 3 linked by pointers

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to print array
void printArray(int arr[], int size) {
    printf("Array: ");
    for (int i = 0; i < size; i++) {
        printf("[%d]", arr[i]);
    }
    printf("\n");
}

// Function to print linked list
void printList(Node* head) {
    printf("Linked List: ");
    Node* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next; // advance curr to next node
    }
    printf("null\n");
}

int main() {
    // Array with 3 elements
    int arr[3] = {1, 2, 3};

    // Linked list with 3 nodes
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    printArray(arr, 3);
    printList(head);

    // Print memory addresses for array elements
    printf("Array element addresses:\n");
    for (int i = 0; i < 3; i++) {
        printf("Element %d at address %p\n", arr[i], (void*)&arr[i]);
    }

    // Print memory addresses for linked list nodes
    printf("Linked list node addresses:\n");
    Node* curr = head;
    while (curr != NULL) {
        printf("Node with data %d at address %p, next points to %p\n", curr->data, (void*)curr, (void*)curr->next);
        curr = curr->next; // advance curr to next node
    }

    return 0;
}

curr = curr->next; // advance curr to next node

advance curr pointer to traverse linked list nodes

for (int i = 0; i < size; i++) { printf("[%d]", arr[i]); }

iterate array elements to print them

printf("Element %d at address %p\n", arr[i], (void*)&arr[i]);

show contiguous memory addresses of array elements

printf("Node with data %d at address %p, next points to %p\n", curr->data, (void*)curr, (void*)curr->next);

show scattered memory addresses and next pointers of linked list nodes

Output

Array: [1][2][3]

Linked List: 1 -> 2 -> 3 -> null

Array element addresses:

Element 1 at address 0x7ffee3b7a9a0

Element 2 at address 0x7ffee3b7a9a4

Element 3 at address 0x7ffee3b7a9a8

Linked list node addresses:

Node with data 1 at address 0x600003f80010, next points to 0x600003f80030

Node with data 2 at address 0x600003f80030, next points to 0x600003f80050

Node with data 3 at address 0x600003f80050, next points to (nil)

Complexity Analysis

Time: O(n) because printing or traversing all elements requires visiting each once

Space: O(n) because both array and linked list store n elements

vs Alternative: Array uses contiguous memory for fast access but fixed size; linked list uses scattered memory with pointers allowing dynamic size but slower access

Edge Cases

Empty array and empty linked list

Array prints nothing; linked list head is NULL and prints null

DSA C

while (curr != NULL) { ... }

Single element array and linked list

Both print one element; linked list next pointer is NULL

DSA C

head->next = NULL;

When to Use This Pattern

When a problem asks about memory usage or access speed differences between data structures, think about array vs linked list memory layout to choose the right one.

Common Mistakes

Mistake: Assuming linked list elements are stored next to each other in memory
Fix: Remember linked list nodes can be anywhere in memory and are connected by pointers

Mistake: Confusing array indexing with linked list traversal
Fix: Use index for arrays but pointer moves for linked lists

Summary

Shows how arrays store elements contiguously and linked lists store nodes scattered with pointers.

Use arrays when you want fast access and fixed size; use linked lists when you want dynamic size and easy insertions.

The key insight is arrays use continuous memory blocks, linked lists use scattered nodes linked by pointers.

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