Singly linked list structure in Data Structures Theory - Full Explanation

Introduction

Imagine you have a chain of paper clips linked one after another. You want to keep track of each clip and the next one in line, but you don't want to hold the whole chain at once. This is the problem a singly linked list solves: it helps organize items in a sequence where each item knows only about the next one.

Explanation

Node

A singly linked list is made up of nodes. Each node holds two things: the data (the actual value or information) and a reference (or pointer) to the next node in the list. This setup allows the list to grow or shrink easily by changing these references.

Each node stores data and a link to the next node, forming the chain.

Head

The head is the first node in the list. It acts as the starting point to access all other nodes. Without the head, you cannot reach the rest of the list because nodes only know about their immediate next node.

The head node is the entry point to the entire list.

Next Pointer

Each node has a next pointer that points to the following node in the list. If a node's next pointer is empty or null, it means that node is the last one in the list. This pointer creates the link between nodes.

The next pointer connects nodes in one direction, from first to last.

Traversal

To access or find a node, you start at the head and follow each next pointer until you reach the desired node or the end of the list. This process is called traversal and it moves step-by-step through the list.

Traversal means moving through the list by following next pointers from the head.

Dynamic Size

Unlike arrays, singly linked lists can easily grow or shrink because nodes can be added or removed by changing pointers. This makes them flexible for situations where the number of items changes often.

Singly linked lists can change size easily by updating node links.

Real World Analogy

Imagine a treasure hunt where each clue leads you to the next one. You start with the first clue, and each clue only tells you where to find the next clue, not the whole path. You follow the clues one by one until you reach the treasure.

Node → Each clue containing a hint and the location of the next clue

Head → The very first clue that starts the treasure hunt

Next Pointer → The direction or location given in each clue to find the next clue

Traversal → Following each clue step-by-step to reach the treasure

Dynamic Size → Adding or removing clues easily without changing the whole hunt

Diagram

Diagram

┌───────┐     ┌───────┐     ┌───────┐     ┌───────┐
│ Data  │ --> │ Data  │ --> │ Data  │ --> │  null │
│ Next  │     │ Next  │     │ Next  │     │       │
└───────┘     └───────┘     └───────┘     └───────┘
  Head

This diagram shows a chain of nodes where each node points to the next, starting from the head and ending with null.

Key Facts

Node → A unit in a singly linked list containing data and a pointer to the next node.

Head → The first node in a singly linked list that serves as the starting point.

Next Pointer → A reference in a node that points to the next node in the list.

Traversal → The process of visiting nodes one by one starting from the head.

Null Pointer → A special pointer indicating the end of the list with no next node.

Code Example

Data Structures Theory

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def traverse(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# Example usage
sll = SinglyLinkedList()
sll.append(10)
sll.append(20)
sll.append(30)
sll.traverse()

Common Confusions

Believing nodes know about previous nodes in the list.

Believing nodes know about previous nodes in the list. In a singly linked list, nodes only know about the next node, not the previous one.

Thinking the list can be accessed randomly like an array.

Thinking the list can be accessed randomly like an array. Accessing nodes requires traversal from the head; random access is not possible.

Assuming the last node points back to the head or another node.

Assuming the last node points back to the head or another node. The last node's next pointer is always null, marking the list's end.

Summary

A singly linked list is a chain of nodes where each node points only to the next one.

The head node is the starting point to access the entire list.

Nodes can be added or removed easily by changing the next pointers, making the list flexible.

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