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

Concept Flow - Why Linked List Exists and What Problem It Solves

Start with array

↓

Fixed size, needs resizing?

Yes→Create new bigger array

↓

Copy elements to new array

↓

Insert/Delete costly

↓

Use Linked List

↓

Dynamic size, easy insert/delete

↓

Traverse nodes one by one

↓

Access sequential elements efficiently

Shows why arrays have limits and how linked lists solve dynamic size and easy insert/delete problems.

Execution Sample

DSA C++

int arr[3] = {1, 2, 3};
// Need to add 4th element
// Array fixed size, must create new array
// Linked list allows adding nodes dynamically

Demonstrates fixed size array limitation and motivation for linked list.

Execution Table

Step	Operation	Data Structure State	Pointer Changes	Visual State
1	Initialize array with 3 elements	Array: [1, 2, 3]	None	1 -> 2 -> 3 -> null (array fixed size)
2	Try to add 4th element to array	Array full	None	Cannot add without resizing
3	Resize array (costly)	New array: [1, 2, 3, _]	None	Copy elements to new array
4	Add 4th element to new array	Array: [1, 2, 3, 4]	None	1 -> 2 -> 3 -> 4 -> null
5	Use linked list instead	Linked list empty	head = null	null
6	Add node with value 1	Linked list: 1 node	head -> node1	1 -> null
7	Add node with value 2	Linked list: 2 nodes	node1.next -> node2	1 -> 2 -> null
8	Add node with value 3	Linked list: 3 nodes	node2.next -> node3	1 -> 2 -> 3 -> null
9	Add node with value 4	Linked list: 4 nodes	node3.next -> node4	1 -> 2 -> 3 -> 4 -> null
10	Insert node between 2 and 3	Linked list: 5 nodes	node2.next -> newNode, newNode.next -> node3	1 -> 2 -> newNode -> 3 -> 4 -> null
11	Delete node with value 2	Linked list: 4 nodes	node1.next -> newNode	1 -> newNode -> 3 -> 4 -> null
12	Traverse linked list	Visit nodes in order	Move pointer from head to next	1 -> newNode -> 3 -> 4 -> null
13	End traversal	All nodes visited	Pointer at null	Traversal complete

💡 Traversal ends when pointer reaches null, linked list allows dynamic size and easy insert/delete

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	Final
head	null	node1(1)	node1(1)	node1(1)	node1(1)	node1(1)	node1(1)	node1(1)
node1.next	null	null	node2(2)	node2(2)	node2(2)	node2(2)	newNode	newNode
node2.next	null	null	null	node3(3)	node3(3)	newNode	newNode	newNode
newNode.next	null	null	null	null	null	node3(3)	node3(3)	node3(3)
node3.next	null	null	null	null	node4(4)	node4(4)	node4(4)	node4(4)
node4.next	null	null	null	null	null	null	null	null

Key Moments - 3 Insights

Why can't we just keep adding elements to an array without resizing?

Arrays have fixed size allocated in memory. Step 2 shows array is full, so adding more needs creating a new bigger array and copying elements (Step 3). This is costly.

How does linked list allow easy insertion between nodes?

Step 10 shows inserting a new node by changing pointers only, no need to move other elements. This is easier than shifting array elements.

Why does traversal stop when pointer reaches null?

Step 13 shows traversal ends when pointer is null, meaning no more nodes. This is how linked list knows where it ends.

Visual Quiz - 3 Questions

Look at the execution table at Step 4, what is the array state?

A [1, 2, 3]

B [1, 2, 3, 4]

C [1, 2, 3, _]

D Empty array

💡 Hint

Check the 'Data Structure State' column at Step 4 in execution_table

At which step does the linked list first have 3 nodes?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look at 'Operation' and 'Data Structure State' columns in execution_table for linked list node counts

If we delete node with value 2 at Step 11, what pointer changes happen?

A node1.next points to node3

B node2.next points to node3

C node1.next points to newNode

D head points to node2

💡 Hint

Check 'Pointer Changes' column at Step 11 in execution_table

Concept Snapshot

Arrays have fixed size; resizing is costly.
Linked lists store elements as nodes linked by pointers.
They allow dynamic size and easy insert/delete.
Traversal is sequential from head to null.
Useful when size changes often or insert/delete needed.

Full Transcript

Arrays have a fixed size, so adding more elements than allocated requires creating a new bigger array and copying elements, which is costly. Linked lists solve this by storing elements as nodes linked by pointers, allowing dynamic size and easy insertion or deletion without moving other elements. Traversal in linked lists happens sequentially from the head node until a null pointer is reached, marking the end. This makes linked lists useful when the number of elements changes frequently or when insertions and deletions are common.

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