Understanding Singly Linked List in Python | Complete Explanation and Implementation Guide

A singly linked list is a key data structure in computer science, often used for dynamic memory allocation and for cases where frequent insertions and deletions are needed. Let’s explore the concept thoroughly by breaking down the step-by-step implementation of a singly linked list (SLL) in Python. We will cover all foundational aspects, from how nodes are defined, to adding (append/insert), removing (delete), and traversing (printing) elements.

1. Defining a Node

A singly linked list is composed of basic building blocks called nodes. Each node holds two important pieces of information:

• Value: The actual data stored in the node.
• Next: A reference (or pointer) to the next node in the list.

Here’s how you define a node in Python:

class Node:
    def __init__(self, val=None):
        self.val = val          # Stores the value of this node
        self.next = None        # Points to the next node (initially None)

Every time a new node is created, it is initialized with a value (val) and a pointer to the next node (next). By default, the next pointer is set to None because when a node is created, it does not yet link to another node.

2. The Singly Linked List Class

The SinglyLinkedList class is responsible for managing the linked list. It maintains a reference to the first node (called the head) and provides the functionality for various operations.

class SinglyLinkedList:
    def __init__(self):
        self.head = None    # Head points to the first node in the list

At initialization, the list is empty, so self.head is set to None.

3. Appending a Node (Add to End)

The append operation adds a new node at the end (tail) of the list. This requires traversing the whole list until the last node is found, then adding the new node after it.

def append(self, data):
    new_node = Node(data)      # Create a new node with the given value
    if not self.head:          # If the list is empty, set head to new node
        self.head = new_node
    else:
        current = self.head
        while current.next is not None:   # Traverse to the last node
            current = current.next
        current.next = new_node           # Link the last node to the new node

How it works:

• If the list is empty (self.head is None), the new node becomes the head.
• Otherwise, we traverse the list to the last node (the one whose next points to None), then set its next pointer to the newly created node.

4. Traversing the List (Printing All Nodes)

Traversal means visiting each node in the sequence and performing an action—here, we’ll print all the values stored in the nodes.

def traverse(self):
    if not self.head:
        print("Singly Linked List is empty")
    else:
        current = self.head
        while current is not None:
            print(current.val, end=" ")
            current = current.next
        print()

How it works:

• If the list is empty, it notifies the user.
• Otherwise, it starts at the head and follows the next pointers until the end, printing each value.

5. Inserting a Node at a Specific Position

To insert a node at a particular position in the list, we must handle two scenarios: inserting at the head and inserting somewhere else within or at the end of the list.

def insert_at(self, data, position):
    new_node = Node(data)
    if position == 0:
        new_node.next = self.head
        self.head = new_node
    else:
        current = self.head
        prev_node = None
        count = 0
        while current is not None and count < position:
            prev_node = current
            current = current.next
            count += 1
        new_node.next = current
        if prev_node:
            prev_node.next = new_node

How it works:

• If the insertion position is zero, the new node becomes the head. The old head is moved to the second position.
• For other positions, we traverse to the node just before the desired position, link the new node into the chain, and update pointers accordingly.

6. Deleting the Head Node (First Node)

Removing the first node simply means updating the head to point to the second node.

def delete_head(self):
    if not self.head:
        print("Cannot delete. Singly Linked List is already empty")
    else:
        self.head = self.head.next  # The second node (or None) becomes the new head

How it works:

• If the list is empty, a notification is printed.
• Otherwise, the head is updated to the next node, effectively removing the first node.

7. Deleting a Node by Value

This operation deletes a node containing a specific value. We need to track both the current node and its predecessor (previous node).

def delete(self, val):
    temp = self.head
    if temp and temp.val == val:
        self.head = temp.next
        return

    prev = None
    found = False

    while temp is not None:
        if temp.val == val:
            found = True
            break
        prev = temp
        temp = temp.next

    if found:
        prev.next = temp.next
    else:
        print("Node not found")

How it works:

• If the value is in the head node, we remove it by updating the head.
• Otherwise, we search for the node with the target value. If found, it is bypassed by updating the previous node’s next pointer.

8. Demonstration: Using the Singly Linked List

Let’s see how each operation behaves step by step.

sll = SinglyLinkedList()

# Append nodes
sll.append(100)
sll.append(200)
sll.append(50)
sll.append(20)
sll.traverse()      # Output: 100 200 50 20

# Insert nodes
sll.insert_at(43, 0)      # Insert 43 at the beginning
sll.traverse()            # Output: 43 100 200 50 20

sll.insert_at(400, 3)     # Insert 400 at position 3
sll.traverse()            # Output: 43 100 200 400 50 20

# Delete head node
sll.delete_head()
sll.traverse()            # Output: 100 200 400 50 20

# Attempt to delete a non-existent node
sll.delete(2000)          # Value not found
sll.traverse()            # Output: 100 200 400 50 20 (unchanged)

Walkthrough of the Outputs:

• Appending: Nodes are always added at the end. After successive appends: 100 → 200 → 50 → 20
• Traversing: Prints all the elements in order.
• Insertion: You can insert at the beginning (position 0) or any other position. E.g. inserting 43 at position one gives: 43 → 100 → 200 → 50 → 20
• Deletion by Head: Removes the first node.
• Deletion by Value: Searches and deletes the first node with the matching value, if found.

Time and Space Complexity Analysis

• N is the number of nodes in the linked list.
• Most operations require traversal (linear time), except deletion/insertion at the head (constant time).
• All operations use only a constant amount of extra space.

Summary

• Linked Lists organize data in nodes, which are linked using pointers.
• Operations like insertion, deletion, and traversal are commonly performed in linked lists.
• Linked lists are especially useful when you need fast insertions and deletions from the list, or when the size of your data changes frequently.
• Unlike arrays, linked lists do not require contiguous memory and can grow or shrink as needed.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.