Why Linked List Exists and What Problem It Solves in DSA C++ - Why This Pattern

Mental Model

A linked list is a chain of boxes where each box points to the next, letting us add or remove boxes easily without moving all others.

Analogy: Imagine a treasure hunt where each clue points to the next location. You don't need to rearrange all clues if you add or remove one; you just change the pointer in one clue.

Head -> [Box1] -> [Box2] -> [Box3] -> null

Dry Run Walkthrough

Input: Array: [1, 2, 3], insert 0 at start; then insert 4 at end

Goal: Show how linked list avoids shifting elements when inserting at start or end

Step 1: Start with array [1, 2, 3]

[1][2][3]

Why: Arrays store elements in fixed spots, so adding at start means moving all elements

Step 2: Insert 0 at start in array by shifting all elements right

[0][1][2][3]

Why: We must move each element one step right to make space at start, which is slow

Step 3: Insert 4 at end in array by adding at next free spot

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

Why: Adding at end is easy if space is available, but resizing array is costly if full

Step 4: Start with linked list 1 -> 2 -> 3 -> null

Head -> [1] -> [2] -> [3] -> null

Why: Linked list stores elements in boxes linked by pointers, not fixed spots

Step 5: Insert 0 at start by creating new box pointing to old head

Head -> [0] -> [1] -> [2] -> [3] -> null

Why: No shifting needed, just change head pointer to new box

Step 6: Insert 4 at end by creating new box and linking last box to it

Head -> [0] -> [1] -> [2] -> [3] -> [4] -> null

Why: No resizing or shifting, just update last box's pointer

Result:

Linked list final state: Head -> [0] -> [1] -> [2] -> [3] -> [4] -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

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

    void insertAtStart(int val) {
        Node* newNode = new Node(val); // create new box
        newNode->next = head;          // point new box to old head
        head = newNode;                // update head to new box
    }

    void insertAtEnd(int val) {
        Node* newNode = new Node(val); // create new box
        if (!head) {
            head = newNode;           // if list empty, new box is head
            return;
        }
        Node* curr = head;
        while (curr->next) {          // move to last box
            curr = curr->next;
        }
        curr->next = newNode;         // link last box to new box
    }

    void printList() {
        Node* curr = head;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "null" << endl;
    }
};

int main() {
    LinkedList list;
    list.insertAtStart(1);
    list.insertAtEnd(2);
    list.insertAtEnd(3);
    list.insertAtStart(0);
    list.insertAtEnd(4);
    list.printList();
    return 0;
}

newNode->next = head; // point new box to old head head = newNode; // update head to new box

insert at start by linking new node to current head and updating head pointer

while (curr->next) { // move to last box curr = curr->next; } curr->next = newNode; // link last box to new box

insert at end by traversing to last node and linking new node

Output

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

Complexity Analysis

Time: O(n) because inserting at end requires traversing all nodes; inserting at start is O(1)

Space: O(n) because each element needs its own node in memory

vs Alternative: Compared to arrays, linked lists avoid costly shifting when inserting at start but have slower access to elements by index

Edge Cases

empty list

inserting at start or end sets head to new node

DSA C++

if (!head) {
    head = newNode;           // if list empty, new box is head
    return;
}

single element list

inserting at end links new node after the single node

DSA C++

while (curr->next) {          // move to last box
    curr = curr->next;
}

When to Use This Pattern

When you need to add or remove items frequently at the start or middle without shifting all elements, think of linked lists because they use pointers to link elements.

Common Mistakes

Mistake: Trying to insert at start by shifting elements like an array
Fix: Use pointer changes to insert new node at start without moving existing nodes

Mistake: Not updating head pointer when inserting at start
Fix: Always update head to point to the new first node

Summary

Linked list stores elements in boxes linked by pointers, allowing easy insertions and deletions.

Use linked lists when you want to add or remove items without shifting all elements like in arrays.

The key is that each element points to the next, so you only change pointers to update the list.

Practice

1. Why do we use a linked list instead of an array in some cases?

easy

A. Because linked lists allow easy insertion and deletion without shifting elements

B. Because linked lists use less memory than arrays always

C. Because linked lists provide faster access to elements by index

D. Because linked lists store elements in contiguous memory locations

Solution

1. Step 1: Understand array limitations

   Arrays store elements in contiguous memory, so inserting or deleting elements requires shifting others, which is slow.

2. Step 2: Understand linked list advantages

   Linked lists store elements in nodes connected by pointers, so insertion and deletion can be done by changing pointers without shifting.

3. Final Answer:

   Because linked lists allow easy insertion and deletion without shifting elements -> Option A

4. Quick Check:

   Insertion/deletion ease = D [OK]

Hint: Linked lists excel at insert/delete without moving all elements [OK]

Common Mistakes:

• Thinking linked lists always use less memory
• Assuming linked lists provide fast random access
• Believing linked lists store data contiguously

2. Which of the following is the correct syntax to declare a node structure for a singly linked list in C++?

easy

A. struct Node { int data; Node& next; };

B. struct Node { int data; Node next; };

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

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

Solution

1. Step 1: Understand node pointer usage

   Each node must have a pointer to the next node, so the type should be Node* next.

2. Step 2: Check syntax correctness

   struct Node { int data; Node* next; }; correctly declares next as a pointer. Options A, B, and D have invalid pointer or reference syntax.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option C

4. Quick Check:

   Pointer to next node = C [OK]

Hint: Node next must be a pointer type Node* next [OK]

Common Mistakes:

• Using Node next instead of Node* next
• Using reference Node& next incorrectly
• Incorrect pointer syntax like next*

3. What will be the output of the following C++ code that creates a linked list and prints its elements?

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

int main() {
  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;
  }
  std::cout << "null" << std::endl;
  return 0;
}

medium

A. 1 -> 2 -> 3 -> null

B. 1 -> 2 -> null

C. 3 -> 2 -> 1 -> null

D. Compilation error

Solution

1. Step 1: Trace linked list creation

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

2. Step 2: Trace printing loop

   The loop prints each node's data followed by ' -> ' until nullptr, then prints 'null'. Output is "1 -> 2 -> 3 -> null".

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option A

4. Quick Check:

   Print linked list in order = A [OK]

Hint: Follow next pointers from head to null to print list [OK]

Common Mistakes:

• Printing nodes in reverse order
• Missing last 'null' in output
• Confusing pointer traversal causing runtime error

4. The following code attempts to insert a new node with value 5 at the beginning of a linked list. What is the error?

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

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

int main() {
  Node* head = nullptr;
  insertAtHead(head, 5);
  std::cout << head->data << std::endl;
  return 0;
}

medium

A. newNode is not allocated properly

B. head is nullptr and cannot be assigned

C. next pointer is not set correctly

D. head is passed by value, so changes don't affect original list

Solution

1. Step 1: Analyze function parameter passing

   The function receives head by value, so modifying head inside does not change the original head pointer in main.

2. Step 2: Understand pointer update requirement

   To update head in main, head must be passed by reference or pointer to pointer; otherwise, main's head remains nullptr.

3. Final Answer:

   head is passed by value, so changes don't affect original list -> Option D

4. Quick Check:

   Pointer update needs reference = B [OK]

Hint: Pass head by reference to update original pointer [OK]

Common Mistakes:

• Assuming head changes inside function affect main
• Ignoring pointer passing semantics
• Thinking newNode allocation is wrong

5. You want to implement a data structure that allows frequent insertions and deletions at both ends efficiently. Why is a linked list a better choice than an array for this problem?

hard

A. Because arrays automatically resize and handle insertions at both ends efficiently

B. Because linked lists can dynamically allocate memory and avoid shifting elements during insertions and deletions

C. Because linked lists store elements contiguously, improving cache performance

D. Because arrays use pointers to link elements making insertions faster

Solution

1. Step 1: Understand array limitations for insert/delete

   Arrays store elements contiguously, so inserting or deleting at ends may require shifting or resizing, which is costly.

2. Step 2: Understand linked list advantages for dynamic operations

   Linked lists allocate nodes dynamically and link them via pointers, allowing insertions and deletions at ends by pointer changes without shifting.

3. Final Answer:

   Because linked lists can dynamically allocate memory and avoid shifting elements during insertions and deletions -> Option B

4. Quick Check:

   Dynamic insert/delete without shifting = A [OK]

Hint: Linked lists avoid shifting by using pointers for dynamic ends [OK]

Common Mistakes:

• Believing arrays resize automatically without cost
• Confusing contiguous storage with faster insertions
• Thinking arrays use pointers like linked lists