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

Why Linked List Exists and What Problem It Solves

📖 Scenario: Imagine you have a collection of books that you want to organize on a shelf. Sometimes you want to add a new book in the middle or remove one without moving all the other books. Using a simple list means shifting many books, which takes time. A linked list is like a chain where each book holds a note pointing to the next book, making it easier to add or remove books anywhere.

🎯 Goal: Build a simple linked list in Python to understand why linked lists exist and how they solve the problem of adding and removing items efficiently compared to regular lists.

📋 What You'll Learn

Create a linked list node class with a value and a pointer to the next node

Create a linked list with three nodes connected in order

Add a new node in the middle of the linked list

Print the linked list to show the order of nodes after insertion

💡 Why This Matters

🌍 Real World

Linked lists are used in music players to keep track of songs in order, allowing easy addition or removal of songs without rearranging the entire list.

💼 Career

Understanding linked lists is fundamental for software developers to manage dynamic data efficiently and is often asked in coding interviews.

1

Create the Node class and initial linked list

Create a class called Node with an __init__ method that takes value and sets self.value = value and self.next = None. Then create three nodes named node1, node2, and node3 with values 10, 20, and 30 respectively. Connect them by setting node1.next = node2 and node2.next = node3.

DSA Python

# Create the Node class and three connected nodes
# Your code here

Hint

Define the Node class first. Then create three nodes and link them by setting the next attribute.

2

Add a new node in the middle

Create a new node called node_new with value 15. Insert it between node1 and node2 by setting node_new.next = node2 and node1.next = node_new.

DSA Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

node1.next = node2
node2.next = node3

# Create node_new with value 15 and insert it between node1 and node2
# Your code here

Hint

Make a new node with value 15. Point its next to node2. Then point node1's next to this new node.

3

Create a function to print the linked list

Define a function called print_linked_list that takes a head node. Use a while loop to traverse nodes starting from head. Print each node's value followed by ' -> ' until the last node, then print 'None'.

DSA Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

node1.next = node2
node2.next = node3

node_new = Node(15)
node_new.next = node2
node1.next = node_new

# Define print_linked_list function to print all node values
# Your code here

Hint

Start from the head node. Keep moving to the next node until you reach None. Print each value with an arrow.

4

Print the linked list after insertion

Call the function print_linked_list with node1 as the argument to print the linked list values after inserting the new node.

DSA Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

node1.next = node2
node2.next = node3

node_new = Node(15)
node_new.next = node2
node1.next = node_new

def print_linked_list(head):
    current = head
    while current is not None:
        print(str(current.value) + ' -> ', end='')
        current = current.next
    print('None')

# Call print_linked_list with node1
# Your code here

Hint

Just call print_linked_list(node1) to see the linked list values.

Practice

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

easy

A. Because linked lists are faster for accessing elements by index

B. Because linked lists use less memory than arrays always

C. Because linked lists store data in contiguous memory locations

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

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 linked 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 D

4. Quick Check:

   Linked list insertion/deletion = easy without shifting [OK]

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

Common Mistakes:

• Thinking linked lists use less memory always
• Believing linked lists store data contiguously
• Assuming linked lists are faster for index access

2. Which of the following is the correct way to define a node class for a singly linked list in Python?

easy

A. class Node:
def __init__(self):
self.data = None
self.next = None

B. class Node:
def __init__(self, data):
self.data = data
self.next = None

C. class Node:
def __init__(self, data):
self.next = data
self.data = None

D. class Node:
def __init__(self, data, next):
self.data = next
self.next = data

Solution

1. Step 1: Check correct attribute assignment

   The node should store data in self.data and link to next node in self.next, initialized to None.

2. Step 2: Verify constructor parameters and assignments

   class Node: def __init__(self, data): self.data = data self.next = None correctly assigns data to self.data and sets self.next to None by default.

3. Final Answer:

   class Node:\n def __init__(self, data):\n self.data = data\n self.next = None -> Option B

4. Quick Check:

   Node stores data and next pointer correctly = class Node: def __init__(self, data): self.data = data self.next = None [OK]

Hint: Node class: data stored, next pointer set to None initially [OK]

Common Mistakes:

• Swapping data and next assignments
• Not initializing next to None
• Missing data parameter in constructor

3. What will be the output of the following code?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
second = Node(2)
third = Node(3)

head.next = second
second.next = third

current = head
while current:
    print(current.data, end=' -> ')
    current = current.next
print('None')

medium

A. 1 -> 2 -> 3 -> None

B. None -> 1 -> 2 -> 3

C. 1 -> 2 -> None -> 3

D. 3 -> 2 -> 1 -> None

Solution

1. Step 1: Understand linked list construction

   Nodes 1, 2, 3 are created and linked in order: head -> second -> third.

2. Step 2: Trace the while loop printing

   Loop prints current.data then moves to next node until current is None, printing 1, 2, 3 in order.

3. Final Answer:

   1 -> 2 -> 3 -> None -> Option A

4. Quick Check:

   Print linked list from head to end = 1 -> 2 -> 3 -> None [OK]

Hint: Traverse from head, print data until next is None [OK]

Common Mistakes:

• Confusing order of nodes
• Printing None at wrong place
• Not linking nodes correctly

4. The following code tries to insert a new node with value 4 after the second node in a linked list. What is the error?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
second = Node(2)
third = Node(3)
head.next = second
second.next = third

new_node = Node(4)
second.next = new_node
new_node.next = third

medium

A. No error, code correctly inserts new_node after second

B. new_node.next should be assigned before second.next

C. new_node.next should point to second, not third

D. head.next should be updated instead of second.next

Solution

1. Step 1: Analyze insertion steps

   New node 4 is inserted after second by setting second.next to new_node, then new_node.next to third.

2. Step 2: Check pointer updates correctness

   Order of assignments is correct; new_node links to third, second links to new_node, preserving list order.

3. Final Answer:

   No error, code correctly inserts new_node after second -> Option A

4. Quick Check:

   Insertion after second node done correctly = No error, code correctly inserts new_node after second [OK]

Hint: Assign second.next to new_node, then new_node.next to third [OK]

Common Mistakes:

• Assigning pointers in wrong order
• Pointing new_node.next to second instead of third
• Updating head.next instead of second.next

5. You want to store a list of tasks where you frequently add and remove tasks from the middle. Why is a linked list better than an array here, and what problem does it solve?

hard

A. Linked list uses less memory than arrays, solving memory overflow issues

B. Linked list stores tasks in sorted order automatically, solving sorting problems

C. Linked list allows fast middle insertions/removals without shifting elements, solving array's slow shifting problem

D. Linked list allows direct access by index, solving array's slow access problem

Solution

1. Step 1: Identify array problem with middle operations

   Arrays require shifting elements when inserting or deleting in the middle, which is slow for large lists.

2. Step 2: Explain linked list advantage

   Linked lists use pointers to link nodes, so inserting or removing in the middle only changes pointers, no shifting needed.

3. Final Answer:

   Linked list allows fast middle insertions/removals without shifting elements, solving array's slow shifting problem -> Option C

4. Quick Check:

   Linked list solves slow shifting in arrays for middle insert/delete [OK]

Hint: Linked list avoids shifting by pointer changes for middle operations [OK]

Common Mistakes:

• Thinking linked lists use less memory always
• Believing linked lists sort data automatically
• Assuming linked lists allow fast index access