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

Why Linked List Exists and What Problem It Solves

📖 Scenario: Imagine you have a line of boxes where you can put toys. Sometimes you want to add a new box in the middle or remove one without moving all the other boxes. Using a linked list helps with this because each box knows where the next box is, so you can easily add or remove boxes without shifting everything.

🎯 Goal: You will create a simple linked list of toy boxes, add boxes one by one, and then show how the list looks. This will help you understand why linked lists are useful compared to just using a simple list where adding or removing in the middle is hard.

📋 What You'll Learn

Create a linked list node structure called Node with an integer data and a pointer next

Create a linked list by adding nodes with values 10, 20, and 30

Traverse the linked list and print the values in order

Understand how linked list nodes connect to each other

💡 Why This Matters

🌍 Real World

Linked lists are used in music players to keep track of songs in a playlist where songs can be added or removed easily.

💼 Career

Understanding linked lists is important for software developers to manage data efficiently and build complex data structures.

1

Create the Node structure

Create a struct Node with an int data and a Node* next pointer. Then create a Node* head and set it to nullptr.

DSA C++

// Define the Node structure and create head pointer
// Your code here

Hint

Think of Node as a box holding a number and a pointer to the next box.

2

Add nodes with values 10, 20, and 30

Create three Node objects named node1, node2, and node3. Set their data to 10, 20, and 30 respectively. Link them by setting node1.next = &node2, node2.next = &node3, and node3.next = nullptr. Finally, set head = &node1.

DSA C++

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

Node* head = nullptr;

// Create nodes and link them
// Your code here

Hint

Each node points to the next node, and the last node points to nullptr.

3

Traverse the linked list

Use a Node* pointer named current starting at head. Use a while loop to go through the list until current is nullptr. Inside the loop, print current->data followed by " -> ", then move current to current->next.

DSA C++

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

Node* head = nullptr;

Node node1, node2, node3;
node1.data = 10;
node2.data = 20;
node3.data = 30;

node1.next = &node2;
node2.next = &node3;
node3.next = nullptr;

head = &node1;

// Traverse and print the linked list
// Your code here

Hint

Move through each node and print its data until you reach the end.

4

Print the linked list result

Print the linked list nodes in order separated by " -> " and end with "null". The output should be: 10 -> 20 -> 30 -> null

DSA C++

#include 

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

int main() {
    Node* head = nullptr;

    Node node1, node2, node3;
    node1.data = 10;
    node2.data = 20;
    node3.data = 30;

    node1.next = &node2;
    node2.next = &node3;
    node3.next = nullptr;

    head = &node1;

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

    // Print the linked list
    // Your code here

    return 0;
}

Hint

The output shows the linked list nodes connected with arrows and ends with null.

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