Creating a Singly Linked List from Scratch in DSA Python - Algorithm Mechanics

Overview - Creating a Singly Linked List from Scratch

What is it?

A singly linked list is a simple chain of elements called nodes, where each node holds some data and a link to the next node. It starts with a head node and ends when a node points to nothing, called null. This structure allows easy insertion and removal of elements without shifting others. It is a basic way to organize data in a sequence.

Why it matters

Without linked lists, managing sequences of data would be less flexible and efficient, especially when adding or removing items in the middle. Arrays require shifting elements, which can be slow. Linked lists let programs grow and shrink data smoothly, which is important in many real-world applications like music playlists, undo features, or navigation paths.

Where it fits

Before learning linked lists, you should understand basic programming concepts like variables, functions, and simple data types. After mastering singly linked lists, you can explore more complex structures like doubly linked lists, stacks, queues, and trees, which build on similar ideas.

Mental Model

Core Idea

A singly linked list is a chain of nodes where each node points to the next, forming a simple, flexible sequence.

Think of it like...

Imagine a treasure hunt where each clue (node) tells you where to find the next clue, but you can only move forward from one clue to the next.

Head -> [Data | Next] -> [Data | Next] -> [Data | null]
Each box is a node with data and a pointer to the next node.

Build-Up - 7 Steps

1

Foundation

Understanding Node Structure Basics

Concept: Introduce the basic building block of a linked list: the node, which stores data and a reference to the next node.

In Python, a node can be a simple class with two parts: one for the data it holds and one for the link to the next node. For example: class Node: def __init__(self, data): self.data = data self.next = None Here, 'data' stores the value, and 'next' points to the next node or None if it is the last.

Result

You can create a node that holds a value and points to nothing yet. Example: node = Node(5) creates a node with data 5 and next None.

Understanding that each node is a small container with data and a pointer is the foundation for building the whole linked list.

2

Foundation

Creating the Linked List Container

Concept: Introduce the linked list class that manages nodes, starting with an empty list having no head.

A linked list needs a starting point called 'head' which points to the first node. Initially, the list is empty, so head is None. class SinglyLinkedList: def __init__(self): self.head = None This class will hold methods to add, remove, and display nodes.

Result

You have a linked list object with no nodes yet, ready to add elements.

Separating the list container from nodes helps organize operations on the whole sequence.

3

Intermediate

Adding Nodes at the Beginning

🤔Before reading on: do you think adding a node at the start requires changing the head pointer or just adding a node somewhere else? Commit to your answer.

Concept: Learn how to insert a new node at the start by updating the head to point to the new node.

To add a node at the beginning: 1. Create a new node with the data. 2. Set its next to the current head. 3. Update the head to this new node. Example method: def add_first(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node This makes the new node the first in the list.

Result

After adding 3, then 5 at start, list looks like: 5 -> 3 -> null

Knowing that the head pointer must move to the new node is key to correctly inserting at the front.

4

Intermediate

Traversing the List to Display

🤔Before reading on: do you think you can access nodes by index like an array, or must you move step-by-step? Commit to your answer.

Concept: Learn to visit each node from head to end to read or print data, moving one node at a time.

To display all nodes: 1. Start at head. 2. While current node is not None: - Print its data. - Move to next node. Example method: def display(self): current = self.head while current: print(current.data, end=' -> ') current = current.next print('null') This prints the list in order.

Result

If list is 5 -> 3 -> null, output is: 5 -> 3 -> null

Understanding that linked lists require step-by-step traversal helps grasp why random access is slower than arrays.

5

Intermediate

Adding Nodes at the End

🤔Before reading on: do you think adding at the end is as simple as adding at the start, or requires finding the last node first? Commit to your answer.

Concept: Learn to insert a new node at the end by traversing to the last node and linking it to the new node.

To add at the end: 1. Create a new node. 2. If list is empty, set head to new node. 3. Else, start at head and move until next is None. 4. Set last node's next to new node. Example method: def add_last(self, data): new_node = Node(data) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node This appends the node at the end.

Result

Adding 7 at end to 5 -> 3 -> null results in 5 -> 3 -> 7 -> null

Knowing that adding at the end requires traversal explains why linked lists are slower for some operations than arrays.

6

Advanced

Removing a Node by Value

🤔Before reading on: do you think removing a node requires changing the previous node's next pointer or just deleting the node itself? Commit to your answer.

Concept: Learn to find a node by value and remove it by adjusting links to skip it.

To remove a node: 1. Check if head is the node to remove; if yes, move head to next. 2. Else, traverse list keeping track of previous node. 3. When node with target value found, set previous node's next to current node's next. Example method: def remove(self, data): current = self.head previous = None while current: if current.data == data: if previous: previous.next = current.next else: self.head = current.next return previous = current current = current.next This removes the first node with matching data.

Result

Removing 3 from 5 -> 3 -> 7 -> null results in 5 -> 7 -> null

Understanding that removal requires changing the link of the previous node prevents losing parts of the list.

7

Expert

Handling Edge Cases and Efficiency

🤔Before reading on: do you think linked lists can be made faster for adding at the end without traversal? Commit to your answer.

Concept: Explore how to handle empty lists, single-node lists, and improve efficiency by tracking the tail node.

Edge cases: - Empty list: adding/removing must update head carefully. - Single-node list: removal sets head to None. Efficiency: - Traversing to add at end is O(n). - To improve, keep a tail pointer updated on insertions. Example: class SinglyLinkedList: def __init__(self): self.head = None self.tail = None def add_last(self, data): new_node = Node(data) if not self.head: self.head = new_node self.tail = new_node else: self.tail.next = new_node self.tail = new_node This makes adding at end O(1).

Result

Adding nodes at end is faster with tail pointer, no traversal needed.

Knowing how to handle special cases and optimize common operations is key for real-world linked list use.

Under the Hood

Each node is an object in memory holding data and a reference (pointer) to the next node's memory address. The list itself holds a reference to the first node (head). Traversing means following these pointers step-by-step. Adding or removing nodes changes these pointers to insert or skip nodes without moving data around.

Why designed this way?

Linked lists were designed to allow dynamic memory use without needing contiguous blocks like arrays. This flexibility was crucial when memory was limited and fragmentation was a problem. The simple pointer structure keeps overhead low and operations like insertion/removal efficient compared to arrays.

Singly Linked List Structure:

[Head] --> [Node1: data | next] --> [Node2: data | next] --> [Node3: data | None]

Operations:
- Add First: NewNode.next = Head; Head = NewNode
- Add Last: Tail.next = NewNode; Tail = NewNode (if tail tracked)
- Remove: Previous.next = Current.next (skips Current)

Myth Busters - 4 Common Misconceptions

Quick: Do you think linked lists allow direct access to the middle element like arrays? Commit yes or no.

Common Belief: Linked lists let you access any element directly by index just like arrays.

Reality: Linked lists require starting at the head and moving node by node to reach a position; no direct index access exists.

Why it matters: Assuming direct access leads to inefficient code and confusion about performance, causing slow programs when random access is needed.

Quick: Do you think adding a node at the end of a singly linked list is always fast? Commit yes or no.

Common Belief: Adding at the end of a singly linked list is always a quick operation.

Reality: Without a tail pointer, adding at the end requires traversing the whole list, which takes time proportional to the list size.

Why it matters: Ignoring this causes unexpected slowdowns in programs that add many elements at the end.

Quick: Do you think removing a node only requires deleting it without changing other nodes? Commit yes or no.

Common Belief: To remove a node, you just delete it and the list fixes itself automatically.

Reality: You must update the previous node's next pointer to skip the removed node; otherwise, the list breaks or loses nodes.

Why it matters: Failing to update links causes data loss or broken lists, leading to bugs and crashes.

Quick: Do you think a singly linked list can be traversed backwards easily? Commit yes or no.

Common Belief: You can easily move backward in a singly linked list by following pointers.

Reality: Singly linked lists only have forward pointers; moving backward requires extra work or a different structure.

Why it matters: Expecting backward traversal leads to design mistakes and inefficient workarounds.

Expert Zone

1

Maintaining a tail pointer is a common optimization but requires careful updates on removals to avoid dangling pointers.

2

Singly linked lists have poor cache locality compared to arrays, which can impact performance on modern CPUs.

3

Using sentinel (dummy) head nodes can simplify edge case handling by avoiding null checks on head.

When NOT to use

Avoid singly linked lists when you need fast random access or frequent backward traversal; arrays or doubly linked lists are better. For very large data, balanced trees or skip lists offer faster search and insertion.

Production Patterns

In real systems, singly linked lists are used for simple queues, adjacency lists in graphs, and memory management free lists. They often combine with other structures and use sentinel nodes or tail pointers for efficiency.

Connections

Arrays

Arrays and linked lists both store sequences but differ in memory layout and access speed.

Understanding linked lists clarifies why arrays are faster for random access but slower for insertions/removals, highlighting trade-offs in data structure choice.

Undo/Redo Systems

Linked lists model sequences of actions where each node represents a state or command.

Knowing linked lists helps design undo features by chaining states and moving forward or backward through them.

Supply Chain Management

Like linked lists, supply chains connect steps in a sequence where each step depends on the previous.

Seeing supply chains as linked nodes helps understand dependencies and flow control in complex systems.

Common Pitfalls

#1 Losing the rest of the list when inserting at the start.

Wrong approach:

def add_first(self, data):
new_node = Node(data)
self.head = new_node # Overwrites head without linking

Correct approach:

def add_first(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node

Root cause:

Not linking the new node to the existing list causes the old list to be lost.

#2 Forgetting to update previous node's next when removing.

Wrong approach:

def remove(self, data):
current = self.head
while current:
if current.data == data:
current = current.next # Just moves pointer, no link update
return
current = current.next

Correct approach:

def remove(self, data):
current = self.head
previous = None
while current:
if current.data == data:
if previous:
previous.next = current.next
else:
self.head = current.next
return
previous = current
current = current.next

Root cause:

Misunderstanding that removing requires changing links, not just skipping nodes.

#3 Assuming adding at end is always O(1) without tail pointer.

Wrong approach:

def add_last(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node

Correct approach:

def __init__(self):
self.head = None
self.tail = None

def add_last(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node

Root cause:

Not tracking tail pointer causes inefficient traversal on every insertion.

Key Takeaways

A singly linked list is a chain of nodes where each node points only to the next, allowing flexible data sequences.

Nodes contain data and a pointer; the list tracks the first node called head.

Operations like adding or removing nodes involve changing pointers, not moving data.

Traversal requires moving step-by-step from head, so random access is slow.

Optimizations like tail pointers and sentinel nodes improve efficiency and simplify edge cases.

Practice

1. What is the main purpose of a Singly Linked List in data structures?

easy

A. To store elements with keys and values for fast lookup

B. To store elements in a sequence where each element points to the next

C. To store elements in a sorted array for binary search

D. To store elements in a tree structure with parent and child nodes

Solution

1. Step 1: Understand the structure of a singly linked list

   A singly linked list stores elements in nodes where each node points to the next node, forming a chain.

2. Step 2: Compare with other data structures

   Unlike arrays or trees, singly linked lists do not store keys or have parent-child relationships; they only link sequentially.

3. Final Answer:

   To store elements in a sequence where each element points to the next -> Option B

4. Quick Check:

   Singly Linked List = sequence with next pointers [OK]

Hint: Remember: singly linked list nodes point only forward [OK]

Common Mistakes:

• Confusing linked lists with arrays or hash maps
• Thinking nodes have backward pointers (that's doubly linked list)
• Assuming linked lists store key-value pairs

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, data, next):
self.data = data
self.next = next
self.prev = None

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

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

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

Solution

1. Step 1: Identify the correct attributes for a singly linked list node

   A singly linked list node stores data and a pointer to the next node only, so it needs data and next.

2. Step 2: Check the constructor parameters and attributes

   class Node: def __init__(self, data): self.data = data self.next = None correctly initializes data and sets next to None by default. Other options include prev which is for doubly linked lists or incorrect parameters.

3. Final Answer:

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

4. Quick Check:

   Node has data and next only [OK]

Hint: Singly linked list nodes have no 'prev' pointer [OK]

Common Mistakes:

• Adding a 'prev' pointer by mistake
• Not initializing 'next' to None
• Using extra parameters unnecessarily

3. What will be the output of the following code that creates a singly linked list with nodes 10, 20, 30 and prints the list?

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

class LinkedList:
    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 print_list(self):
        current = self.head
        while current:
            print(current.data, end=' -> ')
            current = current.next
        print('None')

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.print_list()

medium

A. 10 -> 20 -> None

B. 30 -> 20 -> 10 -> None

C. None

D. 10 -> 20 -> 30 -> None

Solution

1. Step 1: Trace the append method calls

   Appending 10 sets head to node with data 10. Then 20 and 30 are added at the end by traversing the list.

2. Step 2: Trace the print_list method

   Prints nodes in order: 10, then 20, then 30, each followed by ' -> ', ending with 'None'.

3. Final Answer:

   10 -> 20 -> 30 -> None -> Option D

4. Quick Check:

   Append adds at end, print shows order [OK]

Hint: Append adds nodes at list end; print shows order [OK]

Common Mistakes:

• Assuming append adds at front
• Printing without 'None' at end
• Confusing order of nodes

4. The following code tries to append nodes to a singly linked list but does not work as expected. What is the error?

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

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            last = self.head
            while last.next:
                last = last.next
            last = new_node

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)

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

medium

A. The line 'last = new_node' does not link the new node to the list

B. The head is never initialized

C. The Node class is missing the 'prev' pointer

D. The while loop condition should be 'while last is not None'

Solution

1. Step 1: Analyze the append method's else block

   The code finds the last node correctly but then does 'last = new_node' which only changes the local variable, not the last node's next pointer.

2. Step 2: Identify the fix

   To link the new node, it should be 'last.next = new_node' to update the last node's next pointer.

3. Final Answer:

   The line 'last = new_node' does not link the new node to the list -> Option A

4. Quick Check:

   Assign to last.next to link nodes [OK]

Hint: Update last.next, not last variable, to link nodes [OK]

Common Mistakes:

• Assigning new_node to last instead of last.next
• Not updating the head when list is empty
• Confusing variable assignment with pointer update

5. You want to create a singly linked list from scratch that supports inserting a new node at the beginning and printing the list. Which code snippet correctly implements this?

hard

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

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

def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node

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

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

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

def insert_at_beginning(self, data):
new_node = Node(data)
new_node.prev = self.head
self.head = new_node

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

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

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

def insert_at_beginning(self, data):
new_node = Node(data)
self.head = new_node

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

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

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

def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = None
self.head = new_node

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

Solution

1. Step 1: Understand insert at beginning logic

   To insert at the beginning, new node's next should point to current head, then head updated to new node.

2. Step 2: Check each option's insert_at_beginning method

   class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insert_at_beginning(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node def print_list(self): current = self.head while current: print(current.data, end=' -> ') current = current.next print('None') correctly sets new_node.next = self.head and updates head. class Node: def __init__(self, data): self.data = data self.prev = None self.next = None class LinkedList: def __init__(self): self.head = None def insert_at_beginning(self, data): new_node = Node(data) new_node.prev = self.head self.head = new_node def print_list(self): current = self.head while current: print(current.data, end=' -> ') current = current.next print('None') wrongly uses prev pointer. class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insert_at_beginning(self, data): new_node = Node(data) self.head = new_node def print_list(self): current = self.head while current: print(current.data, end=' -> ') current = current.next print('None') misses linking new_node.next. class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insert_at_beginning(self, data): new_node = Node(data) new_node.next = None self.head = new_node def print_list(self): current = self.head while current: print(current.data, end=' -> ') current = current.next print('None') sets new_node.next to None, losing old list.

3. Final Answer:

   Option A code snippet correctly inserts at beginning and prints list -> Option A

4. Quick Check:

   New node points to old head, then head updated [OK]

Hint: New node's next = old head; update head to new node [OK]

Common Mistakes:

• Not linking new node to old head
• Using prev pointer in singly linked list
• Setting new_node.next to None incorrectly