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 connect items with pointers for flexible size.

Analogy: An array is like a row of mailboxes in a building where each mailbox has a fixed number and you can open any quickly. A linked list is like a treasure hunt where each clue points to the next location, so you follow the chain step by step.

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

Dry Run Walkthrough

Input: Compare inserting value 6 at the end in array and linked list with initial data 1,2,3,4,5

Goal: Show how insertion differs in arrays and linked lists and when each is easier

Step 1: Try to insert 6 at the end of the array

[1][2][3][4][5] (full capacity assumed)
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Array has fixed size, so adding beyond capacity needs resizing

Step 2: Resize array to bigger size and copy elements

[1][2][3][4][5][ ][ ] (extra spaces)
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Array needs contiguous space, so resizing copies all elements

Step 3: Insert 6 at the new free slot in array

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

Why: Now array can hold new element but resizing is costly

Step 4: Insert 6 at the end of linked list by creating new node

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

Why: Linked list can add new node by changing pointer without resizing

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Node class for linked list
class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// Linked list class
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* curr = head;
        while (curr->next) {
            curr = curr->next; // advance curr to next node
        }
        curr->next = newNode; // link new node at end
    }

    void print() {
        Node* curr = head;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->next; // advance curr to next node
        }
        cout << "null" << endl;
    }
};

int main() {
    // Array part
    int capacity = 5;
    int size = 5;
    int* arr = new int[capacity]{1, 2, 3, 4, 5};

    // Insert 6 at end in array
    if (size == capacity) {
        // resize array
        int newCapacity = capacity * 2;
        int* newArr = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newArr[i] = arr[i]; // copy elements
        }
        delete[] arr;
        arr = newArr;
        capacity = newCapacity;
    }
    arr[size] = 6; // insert new element
    size++;

    cout << "Array after insertion: ";
    for (int i = 0; i < size; i++) {
        cout << "[" << arr[i] << "]";
    }
    cout << endl;

    // Linked list part
    LinkedList list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    list.append(5);
    list.append(6); // insert 6 at end

    cout << "Linked List after insertion: ";
    list.print();

    delete[] arr;
    return 0;
}

while (curr->next) { curr = curr->next; // advance curr to next node }

advance curr to last node to append new node

curr->next = newNode; // link new node at end

attach new node at end of linked list

for (int i = 0; i < size; i++) { newArr[i] = arr[i]; // copy elements }

copy elements to new bigger array during resize

arr[size] = 6; // insert new element

insert new element at next free slot in array

Output

Array after insertion: [1][2][3][4][5][6]

Linked List after insertion: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Complexity Analysis

Time: O(n) for array insertion when resizing is needed because all elements must be copied; O(n) for linked list insertion to reach end node, O(1) if tail pointer is maintained

Space: O(n) for both because they store n elements; array may allocate extra space during resize

vs Alternative: Arrays provide fast random access but costly resizing; linked lists allow easy insertions/deletions but slower access

Edge Cases

Empty array or linked list

Insertion is straightforward; linked list head or array first slot is set

DSA C++

if (!head) {
    head = newNode;
    return;
}

Array at full capacity

Array resizes by allocating new memory and copying elements

DSA C++

if (size == capacity) {
    // resize array
}

Single element linked list

Appending adds new node after head

DSA C++

while (curr->next) {
    curr = curr->next;
}

When to Use This Pattern

When a problem needs frequent insertions or deletions in the middle or end, consider linked lists; when fast access by index is needed, arrays are better.

Common Mistakes

Mistake: Trying to insert into a full array without resizing
Fix: Always check capacity and resize array before insertion

Mistake: Not updating linked list pointers correctly when inserting
Fix: Ensure new node's next pointer is set and previous node points to new node

Summary

Compares when to use linked lists or arrays based on insertion and access needs.

Use arrays for fast access and fixed size; use linked lists for flexible size and frequent insertions.

Arrays need resizing which is costly; linked lists use pointers to add elements easily.

Practice

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

easy

A. Queue

B. Array

C. Stack

D. Linked List

Solution

1. Step 1: Understand random access requirement

   Random access means accessing any element directly by its position quickly.

2. Step 2: Compare array and linked list access times

   Arrays allow direct access by index in constant time, while linked lists require traversal.

3. Final Answer:

   Array -> Option B

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 traversal cost in linked lists

2. Which of the following is the correct way to declare a dynamic array in C++?

easy

A. int arr[] = new int(10);

B. int arr[10];

C. int arr = new int[10];

D. int* arr = new int[10];

Solution

1. Step 1: Identify dynamic array syntax in C++

   Dynamic arrays use pointers with 'new' keyword and size in brackets.

2. Step 2: Check each option

   int* arr = new int[10]; correctly uses 'int* arr = new int[10];'. Others are either static arrays or incorrect syntax.

3. Final Answer:

   int* arr = new int[10]; -> Option D

4. Quick Check:

   Dynamic array = new int[size] [OK]

Hint: Use 'new' with pointer for dynamic arrays in C++ [OK]

Common Mistakes:

• Using static array syntax for dynamic arrays
• Missing pointer (*) in declaration
• Incorrect use of parentheses instead of brackets

3. What will be the output of the following C++ code snippet?

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

Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};

Node* temp = head;
while(temp != nullptr) {
  std::cout << temp->data << " ";
  temp = temp->next;
}

medium

A. 1 2 3

B. 3 2 1

C. 1 3 2

D. Compilation error

Solution

1. Step 1: Understand linked list creation

   Nodes are created with values 1, 2, 3 linked in order: head -> 1 -> 2 -> 3 -> nullptr.

2. Step 2: Trace the while loop output

   Loop prints data of each node from head to end: 1, then 2, then 3, each followed by space.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Traverse linked list prints 1 2 3 [OK]

Hint: Traverse linked list from head to print data [OK]

Common Mistakes:

• Confusing order of nodes
• Forgetting to update temp pointer
• Assuming array-like indexing

4. Identify the error in the following code that tries to insert a new node at the beginning of a linked list:

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

void insertAtHead(Node* head, int val) {
  Node* newNode = new Node{val, nullptr};
  newNode->next = head;
  head = newNode;
}

medium

A. head pointer is passed by value, so original list is not updated

B. Missing return type in function

C. newNode->next should be nullptr

D. Memory leak due to not deleting old head

Solution

1. Step 1: Analyze function parameter passing

   head is passed by value, so changes inside function do not affect original head pointer.

2. Step 2: Understand effect on linked list

   Assigning head = newNode only changes local copy; original list head remains unchanged.

3. Final Answer:

   head pointer is passed by value, so original list is not updated -> Option A

4. Quick Check:

   Pass pointer by reference to update list head [OK]

Hint: Pass head by reference to modify original list [OK]

Common Mistakes:

• Assuming pointer changes affect caller without reference
• Incorrect next pointer assignment
• Ignoring memory management

5. You need to store a large collection of elements where insertions and deletions happen frequently at random positions. Which data structure is more suitable and why?

hard

A. Array, because it provides fast random access

B. Array, because it uses less memory than linked list

C. Linked List, because it allows efficient insertions and deletions without shifting elements

D. Linked List, because it supports binary search efficiently

Solution

1. Step 1: Understand operation requirements

   Frequent insertions and deletions at random positions require efficient element rearrangement.

2. Step 2: Compare array and linked list for these operations

   Arrays require shifting elements on insert/delete, which is costly. Linked lists adjust pointers, making these operations efficient.

3. Final Answer:

   Linked List, because it allows efficient insertions and deletions without shifting elements -> Option C

4. Quick Check:

   Frequent insert/delete = Linked List [OK]

Hint: Use linked list for frequent insertions/deletions [OK]

Common Mistakes:

• Choosing array for frequent insert/delete ignoring shift cost
• Thinking linked list supports fast random access
• Confusing binary search applicability