Singly linked list structure in Data Structures Theory - Step-by-Step Execution

Concept Flow - Singly linked list structure

Create new node

↓

Set node data and next pointer

↓

If list empty?

Yes→Set head to new node

↓

Traverse to last node

↓

Insert new node at end

↓

Done

This flow shows how a new node is created and added to a singly linked list, either as the first node or appended at the end.

Execution Sample

Data Structures Theory

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

new_node = Node(5)
if head is None:
    head = new_node
else:
    current = head
    while current.next:
        current = current.next
    current.next = new_node

This code creates a new node with data 5 and inserts it at the end of a singly linked list.

Analysis Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	None	head = None	head -> None
2	Create new node with data=5	Node(5)	new_node created	head -> None, new_node(5) -> None
3	Check if list empty	Node(5)	head is None (True)	head -> None
4	Set head to new_node	Node(5)	head = new_node	head -> Node(5) -> None
5	End of insertion	Node(5)	No pointer changes	head -> Node(5) -> None

💡 Insertion done because list was empty and head was set to new_node

State Tracker

Variable	Start	After Step 2	After Step 4	Final
head	None	None	Node(5)	Node(5)
new_node	None	Node(5)	Node(5)	Node(5)
current	None	None	None	None

Key Insights - 3 Insights

Why do we check if head is None before inserting?

Because if head is None, the list is empty and the new node becomes the first node (see execution_table step 3 and 4). Without this, we wouldn't know where to start inserting.

What does the 'next' pointer in a node represent?

It points to the next node in the list or None if it is the last node. This is shown in the Visual State column where Node(5) points to None.

Why don't we need to traverse the list when it is empty?

Because there are no nodes to traverse. The new node becomes the head immediately (execution_table step 3 and 4). Traversal happens only if the list is not empty.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what does the head pointer point to?

A The previous node

B None

C The new node with data 5

D An empty list

💡 Hint

Check the Pointer Changes and Visual State columns at step 4 in execution_table.

At which step does the list change from empty to having one node?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the Pointer Changes column where head is assigned to new_node.

If the list was not empty, what would happen instead of setting head to new_node?

A Delete the head node

B Traverse to last node and set its next to new_node

C Set head to None

D Do nothing

💡 Hint

Refer to the concept_flow where the 'No' branch leads to traversal and insertion at the end.

Concept Snapshot

Singly linked list stores nodes where each node points to the next.
Head points to the first node or None if empty.
To insert, create a new node.
If empty, set head to new node.
Else, traverse to last node and link new node.
Each node's 'next' points to the following node or None.

Full Transcript

A singly linked list is a chain of nodes where each node holds data and a pointer to the next node. The list starts with a head pointer. When inserting a new node, if the list is empty (head is None), the new node becomes the head. Otherwise, we traverse the list to find the last node and set its next pointer to the new node. This process ensures nodes are linked in order. The 'next' pointer of the last node is always None, marking the list's end.

Practice

1. What does each node in a singly linked list contain?

easy

A. Only data without any pointers

B. Data and pointers to both next and previous nodes

C. Data and a pointer to the next node

D. Only a pointer to the previous node

Solution

1. Step 1: Understand node structure in singly linked list

   Each node stores some data and a pointer to the next node only, not to the previous one.

2. Step 2: Compare options with definition

   Data and a pointer to the next node matches the definition exactly. Data and pointers to both next and previous nodes describes a doubly linked list. Options C and D miss the pointer to the next node.

3. Final Answer:

   Data and a pointer to the next node -> Option C

4. Quick Check:

   Node = data + next pointer [OK]

Hint: Remember: singly linked means one pointer per node [OK]

Common Mistakes:

• Confusing singly linked with doubly linked list
• Thinking nodes have no pointers
• Assuming pointer to previous node exists

2. Which of the following is the correct way to represent the head of a singly linked list in code?

easy

A. head = None

B. head = head.next

C. head = head.prev

D. head = data

Solution

1. Step 1: Understand the head pointer initialization

   The head points to the first node or is None if the list is empty.

2. Step 2: Analyze options

   head = None correctly initializes head as None for an empty list. head = head.next tries to move head to next node, which is invalid if list is empty. head = head.prev uses prev pointer which does not exist in singly linked list. head = data assigns data to head, which is incorrect.

3. Final Answer:

   head = None -> Option A

4. Quick Check:

   Empty list head = None [OK]

Hint: Head starts as None when list is empty [OK]

Common Mistakes:

• Using prev pointer in singly linked list
• Assigning data directly to head
• Moving head before list has nodes

3. Given the following singly linked list nodes:

node1 = Node(data=10, next=node2)
node2 = Node(data=20, next=node3)
node3 = Node(data=30, next=None)
head = node1

What is the data value of head.next.next?

medium

A. 20

B. 30

C. 10

D. None

Solution

1. Step 1: Trace the linked nodes from head

   head points to node1 with data 10. head.next points to node2 with data 20. head.next.next points to node3 with data 30.

2. Step 2: Identify the data at head.next.next

   The data at node3 is 30.

3. Final Answer:

   30 -> Option B

4. Quick Check:

   head.next.next.data = 30 [OK]

Hint: Follow next pointers step-by-step [OK]

Common Mistakes:

• Confusing node positions
• Assuming next of last node is not None
• Mixing data values with node references

4. Identify the error in this singly linked list insertion code snippet:

new_node = Node(data=5)
new_node.next = head
head = new_node.next

medium

A. new_node.next should be None

B. No error, code is correct

C. Data assignment to new_node is missing

D. head should be assigned to new_node, not new_node.next

Solution

1. Step 1: Understand insertion at head

   To insert new_node at the start, new_node.next should point to current head, then head should be updated to new_node.

2. Step 2: Analyze the code error

   The code sets new_node.next = head correctly, but then sets head = new_node.next, which points to old head, not new_node. This loses the new node as head.

3. Final Answer:

   head should be assigned to new_node, not new_node.next -> Option D

4. Quick Check:

   head = new_node after insertion [OK]

Hint: After linking, head must point to new_node [OK]

Common Mistakes:

• Assigning head to new_node.next instead of new_node
• Forgetting to link new_node.next to old head
• Not updating head pointer after insertion

5. You want to reverse a singly linked list with nodes:

head -> node1 -> node2 -> node3 -> None

Which sequence of pointer changes correctly reverses the list?

hard

A. Change each node's next pointer to the previous node, then update head to last node

B. Swap data values between nodes without changing pointers

C. Set head to None and create a new list with reversed data

D. Change each node's next pointer to None

Solution

1. Step 1: Understand reversal of singly linked list

   Reversing means changing each node's next pointer to point to the previous node instead of the next.

2. Step 2: Identify correct pointer update sequence

   Change each node's next pointer to the previous node, then update head to last node correctly describes reversing pointers and updating head to the last node. Swap data values between nodes without changing pointers only swaps data, not pointers. Set head to None and create a new list with reversed data discards the list unnecessarily. Change each node's next pointer to None breaks links without reversing.

3. Final Answer:

   Change each node's next pointer to the previous node, then update head to last node -> Option A

4. Quick Check:

   Reverse = reverse pointers + update head [OK]

Hint: Reverse pointers, then reset head to last node [OK]

Common Mistakes:

• Swapping data instead of pointers
• Not updating head after reversal
• Breaking links without reconnecting