⛓️ Singly Linked List

👉 What is a Singly Linked List?

A singly linked list is the most basic type of linked list. It is a collection of nodes that are linked together in a sequence, allowing for traversal in only one direction (forward). Each node contains data and a single pointer that references the next node in the list.

📝 Node Structure

Every node in a singly linked list consists of two parts:

Data: The value stored in the node (e.g., a number, string, or any other object).
Next Pointer: A reference to the very next node in the list. For the last node, this pointer points to None (or null), signifying the end of the list.

linked-list/singly.py #Node


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

⭐ Operations and Traversal

👉 Traversal

Traversal means visiting each node in the list exactly once, starting from the head. This is the foundation for most other operations. The process is strictly sequential and forward-only.

Process:
1. Create a temporary reference, let’s call it current, and point it to the list’s head.
2. While current is not None, you are at a valid node.
3. Process the data in the current node (e.g., read or print it).
4. Move to the next node by updating current to point to current.next.
Complexity: O(n), because in the worst case, you must visit all n nodes in the list.

👉 Insertion

Inserting a node involves creating a new node and carefully rearranging pointers to place it correctly in the list.

🔹 At the Head (Prepending)

This is the most efficient insertion operation.

Process:
1. Create a new node with the desired data.
2. Set the new node’s next pointer to the current head of the list.
3. Update the list’s head to point to this new node.
Complexity: O(1), as it involves a fixed number of steps regardless of list size.

🔹 At the End (Appending)

Process:
1. Create a new node with the desired data.
2. Traverse the list until you find the last node (the one whose next is None).
3. Set that last node’s next pointer to the new node.
Complexity: O(n), because you must traverse the entire list to find the end.

🔹 In the Middle

Process:
1. Create a new node with the desired data.
2. Traverse the list to find the node before your desired insertion point. Let’s call this previous_node.
3. Set the new node’s next pointer to whatever previous_node.next was pointing to.
4. Update previous_node.next to point to the new node.
Complexity: O(n), as you need to traverse to the correct position first.

👉 Deletion

Deletion involves “bypassing” a node by redirecting the pointers around it.

🔹 From the Head

Process:
1. Simply update the list’s head to point to the second node (head.next). The old head is now disconnected from the list.
Complexity: O(1).

🔹 From the End or Middle

Process:
1. Traverse the list to find the node before the one you want to delete (previous_node).
2. Let the node to be deleted be target_node (previous_node.next).
3. Update previous_node.next to point to target_node.next. This skips over the target_node.
Complexity: O(n), because finding the previous_node requires traversal.

👉 Searching

Searching for a value involves traversing the list and checking each node’s data.

Process: Follow the same steps as traversal. In each step, compare the current node’s data with the value you are searching for. If they match, you’ve found the node. If you reach the end of the list (None), the value is not present.
Complexity: O(n).

linked-list/singly.py #SinglyLinkedList


class SinglyLinkedList:
    """
    Manages the overall Linked List.
    """
    def __init__(self):
        self.head = None
 
    def display(self):
        """
        Traverses and prints the entire list.
        Complexity: `O(n)`
        """
        nodes = []
        current_node = self.head
        while current_node:
            nodes.append(str(current_node.data))
            current_node = current_node.next
        print(" -> ".join(nodes))
 
    def prepend(self, data):
        """
        Inserts a new node at the beginning of the list.
        Complexity: `O(1)`
        """
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
 
    def append(self, data):
        """
        Inserts a new node at the end of the list.
        Complexity: `O(n)`
        """
        new_node = Node(data)
        # If the list is empty, the new node is the head
        if not self.head:
            self.head = new_node
            return
 
        # Traverse to the last node
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        
        # Set the last node's next pointer to the new node
        last_node.next = new_node
 
    def delete_by_value(self, data):
        """
        Deletes a node by its data value.
        Complexity: `O(n)`
        """
        if not self.head:
            print("Error: List is empty.")
            return
 
        # Case 1: The node to delete is the head
        if self.head.data == data:
            self.head = self.head.next
            return
 
        # Case 2: The node is in the middle or at the end
        current_node = self.head
        # Find the node *before* the one to be deleted
        while current_node.next and current_node.next.data != data:
            current_node = current_node.next
 
        if current_node.next:
            # Bypass the node to be deleted
            current_node.next = current_node.next.next
        else:
            print(f"Error: Node with data '{data}' not found.")
 
    def search(self, data):
        """
        Searches for a node with the given data.
        Returns the node if found, otherwise None.
        Complexity: `O(n)`
        """
        current_node = self.head
        while current_node:
            if current_node.data == data:
                return current_node
            current_node = current_node.next
        return None

linked-list/singly.py #Example Usage


if __name__ == "__main__":
    sll = SinglyLinkedList()
 
    print("🔹 Appending 10, 20, 30...")
    sll.append(10)
    sll.append(20)
    sll.append(30)
    sll.display() # Output: 10 -> 20 -> 30
 
    print("\n🔹 Prepending 5...")
    sll.prepend(5)
    sll.display() # Output: 5 -> 10 -> 20 -> 30
 
    print("\n🔹 Deleting node with value 20...")
    sll.delete_by_value(20)
    sll.display() # Output: 5 -> 10 -> 30
 
    print("\n🔹 Deleting head node (value 5)...")
    sll.delete_by_value(5)
    sll.display() # Output: 10 -> 30
 
    print("\n🔹 Searching for value 30...")
    found_node = sll.search(30)
    if found_node:
        print(f"Node with data '{found_node.data}' found.") # This will print
    else:
        print("Node not found.")
 
    print("\n🔹 Searching for value 99...")
    found_node = sll.search(99)
    if found_node:
        print(f"Node with data '{found_node.data}' found.")
    else:
        print("Node with data '99' not found.") # This will print

👍 Advantages

Simplicity: It’s simpler to implement than other types of linked lists.
Memory: Uses slightly less memory per node compared to a doubly linked list because it only stores one pointer.

👎 Disadvantages

Unidirectional Traversal: The biggest limitation is that you cannot traverse the list in reverse. Finding the previous node for a given node is an O(n) operation.
Complex Deletions: To delete a specific node, you need a reference to the node before it, which complicates the operation if you only have a reference to the node you want to delete.

⚠️ Important Note: Choose a singly linked list when you need a simple, memory-efficient, dynamic data structure and your primary use case involves forward traversal or frequent insertions/deletions at the head of the list.