Bird
0
0
DSA Cprogramming

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

Choose your learning style9 modes available
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
OutputSuccess
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.