Linked List vs Array When to Choose Which in DSA C - Trade-offs & Analysis

Mental Model

Arrays store items in a fixed block of memory for quick access, while linked lists chain items with pointers for easy changes.

Analogy: An array is like a row of mailboxes where each box has a fixed spot, and a linked list is like a treasure hunt where each clue points to the next location.

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

Dry Run Walkthrough

Input: Compare adding an item at the start and accessing the 3rd item in array and linked list of 5 elements

Goal: Show when arrays or linked lists are better for adding and accessing elements

Step 1: Access 3rd item in array directly

[1][2][3][4][5]
Accessed value: 3

Why: Arrays allow direct access by index quickly

Step 2: Access 3rd item in linked list by moving through nodes

1 -> 2 -> [3] -> 4 -> 5 -> null

Why: Linked lists require moving step-by-step to reach an item

Step 3: Add new item '0' at start of array by shifting all elements right

[0][1][2][3][4][5]

Why: Arrays need to move all items to make space at start

Step 4: Add new item '0' at start of linked list by creating new node pointing to old head

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Linked lists add at start easily by changing pointers

Result:

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

Annotated Code

DSA C

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

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

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

// Add node at start of linked list
void addAtStart(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head; // link new node to old head
    *head = newNode;       // update head to new node
}

// Print linked list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n");
}

int main() {
    // Array example
    int arr[6] = {1, 2, 3, 4, 5};
    // Add 0 at start by shifting
    for (int i = 5; i > 0; i--) {
        arr[i] = arr[i - 1]; // shift right
    }
    arr[0] = 0;

    printf("Array after adding 0 at start: ");
    for (int i = 0; i < 6; i++) {
        printf("[%d]", arr[i]);
    }
    printf("\nAccess 3rd item in array: %d\n", arr[2]);

    // Linked list example
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    addAtStart(&head, 0);

    printf("Linked list after adding 0 at start: ");
    printList(head);

    // Access 3rd item in linked list
    Node* curr = head;
    for (int i = 0; i < 2; i++) {
        curr = curr->next; // move to 3rd node
    }
    printf("Access 3rd item in linked list: %d\n", curr->data);

    return 0;
}

for (int i = 5; i > 0; i--) { arr[i] = arr[i - 1]; }

Shift array elements right to make space at start

arr[0] = 0;

Insert new element at start of array

newNode->next = *head; *head = newNode;

Add new node at start of linked list by pointer update

for (int i = 0; i < 2; i++) { curr = curr->next; }

Traverse linked list to reach 3rd node

Output

Array after adding 0 at start: [0][1][2][3][4][5]

Access 3rd item in array: 3

Linked list after adding 0 at start: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Access 3rd item in linked list: 3

Complexity Analysis

Time: O(n) for adding at start in array because all elements shift; O(1) for linked list add at start because only pointers change; O(1) for array access by index; O(n) for linked list access by position because traversal needed

Space: O(n) for both because they store n elements; linked list uses extra space for pointers

vs Alternative: Arrays are faster for random access but slower for insertions/deletions at start; linked lists are slower to access but faster to insert/delete at start

Edge Cases

Empty array or linked list

Adding at start works normally; accessing 3rd item fails or invalid

DSA C

for (int i = 0; i < 2; i++) { curr = curr->next; }

Single element list or array

Adding at start still works; accessing 3rd item invalid

DSA C

for (int i = 0; i < 2; i++) { curr = curr->next; }

When to Use This Pattern

When a problem needs fast random access, arrays are best; when frequent insertions or deletions at start or middle happen, linked lists are better.

Common Mistakes

Mistake: Trying to access linked list elements by index directly like an array
Fix: Traverse nodes one by one to reach desired position

Mistake: Inserting at start of array without shifting elements
Fix: Shift all elements right before inserting at index 0

Summary

Arrays store elements in fixed positions for quick access; linked lists chain elements for easy changes.

Use arrays when you need fast access by position; use linked lists when you need fast insertions or deletions.

The key insight is arrays are like fixed mailboxes, linked lists are like chained clues pointing to next.