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.

Practice

1. Which data structure is better when you need fast random access to elements by index?

easy

A. Array

B. Linked List

C. Stack

D. Queue

Solution

1. Step 1: Understand random access in arrays

   Arrays store elements in contiguous memory, so accessing any element by index is fast and direct.

2. Step 2: Compare with linked list access

   Linked lists require traversal from the head to reach an element, making random access slower.

3. Final Answer:

   Array -> Option A

4. Quick Check:

   Random access = Array [OK]

Hint: For fast index access, choose arrays [OK]

Common Mistakes:

• Thinking linked lists provide fast random access
• Confusing stack or queue with random access
• Ignoring memory layout differences

2. Which of the following is the correct way to declare an array of 5 integers in C?

easy

A. int arr{};

B. int arr();

C. int arr[5];

D. int arr = new int[5];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with type, name, and size in square brackets, like int arr[5];

2. Step 2: Check other options for errors

   int arr(); uses parentheses which is a function declaration, C uses braces which is invalid, D uses 'new' which is C++ syntax.

3. Final Answer:

   int arr[5]; -> Option C

4. Quick Check:

   C array declaration = int arr[5]; [OK]

Hint: Use square brackets for arrays in C [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using C++ 'new' keyword in C
• Using braces for array declaration

3. Consider the following C code snippet:

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

Node* head = NULL;

// Insert 3 nodes at the beginning
for (int i = 1; i <= 3; i++) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = i;
  newNode->next = head;
  head = newNode;
}

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

What is the printed output?

medium

A. 1 -> 2 -> 3 -> NULL

B. 3 -> 2 -> 1 -> NULL

C. NULL

D. 3 -> 1 -> 2 -> NULL

Solution

1. Step 1: Understand insertion at beginning in linked list

   Each new node is added at the head, so the last inserted node becomes the first in the list.

2. Step 2: Trace the loop values and list order

   Insert 1: list is 1 -> NULL Insert 2: list is 2 -> 1 -> NULL Insert 3: list is 3 -> 2 -> 1 -> NULL

3. Final Answer:

   3 -> 2 -> 1 -> NULL -> Option B

4. Quick Check:

   Insertion at head reverses order [OK]

Hint: Insertion at head reverses order [OK]

Common Mistakes:

• Assuming insertion appends at end
• Confusing order of nodes after insertion
• Ignoring pointer updates

4. The following code tries to insert a node at the end of a singly linked list but causes a runtime error. What is the error?

void insertEnd(Node** head, int val) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = val;
  newNode->next = NULL;

  Node* temp = *head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = newNode;
}

medium

A. Dereferencing NULL pointer when list is empty

B. Memory leak due to missing free()

C. Incorrect data assignment to newNode

D. Missing return statement in void function

Solution

1. Step 1: Analyze behavior when list is empty

   If *head is NULL, then temp = NULL. Accessing temp->next causes a runtime error (segmentation fault).

2. Step 2: Identify fix for empty list case

   Need to check if *head is NULL before loop and assign newNode as head if true.

3. Final Answer:

   Dereferencing NULL pointer when list is empty -> Option A

4. Quick Check:

   Empty list causes NULL pointer error [OK]

Hint: Check for empty list before traversal [OK]

Common Mistakes:

• Ignoring empty list case
• Confusing memory leak with pointer error
• Thinking missing return causes runtime error

5. You need to store a large number of elements where insertions and deletions happen frequently at random positions. Which data structure is more suitable and why? A) Array because it uses less memory B) Linked List because it allows efficient insertions and deletions C) Array because it provides faster random access D) Linked List because it uses contiguous memory

hard

A. Array because it uses less memory

B. Linked List because it uses contiguous memory

C. Array because it provides faster random access

D. Linked List because it allows efficient insertions and deletions

Solution

1. Step 1: Understand insertion and deletion costs

   Arrays require shifting elements for insertions/deletions at random positions, which is costly.

2. Step 2: Compare with linked list behavior

   Linked lists allow insertions and deletions by changing pointers without shifting elements, making them efficient for frequent changes.

3. Final Answer:

   Linked List because it allows efficient insertions and deletions -> Option D

4. Quick Check:

   Frequent insert/delete = Linked List [OK]

Hint: Frequent insert/delete? Choose linked list [OK]

Common Mistakes:

• Choosing array for frequent insertions
• Thinking linked list uses contiguous memory
• Ignoring cost of shifting in arrays