Linked Lists in Python

A linked list is a linear data structure where elements are stored in nodes, and each node points (links) to the next node using references. Unlike Python lists (dynamic arrays), linked lists do not store elements in contiguous memory. This makes certain operations (especially insertions/deletions in the middle) efficient because you only change links rather than shifting elements.

Key idea: In a linked list, the “order” is maintained by pointers, not by indexes.

When to use linked lists:

• You do lots of insertions/deletions in the middle of the sequence.
• You don’t need fast random indexing (because linked lists are slow for index access).

When NOT to use:

• You need frequent random access like arr[i] (Python lists are better).
• You want cache-friendly performance (arrays are usually faster in practice).

---

Introduction to Linked Lists

Singly Linked List

A singly linked list node contains:

• data
• next pointer → reference to the next node

Structure:

head -> [data|next] -> [data|next] -> [data|next] -> None

Important points:

• You can move only forward.
• Deleting a node requires access to its previous node.

Doubly Linked List

A doubly linked list node contains:

• data
• prev pointer → reference to previous node
• next pointer → reference to next node

Structure:

None <- [prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> None

Advantages over singly:

• Can traverse forward and backward.
• Deletions are easier if you have the node reference.

Disadvantages:

• Extra memory for prev.
• Slightly more complex implementation.

---

Implementing Nodes and Linked Lists in Python

Node Class (Singly)

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

Linked List Class (Core Structure)

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

Helper: Print / Debug the Linked List

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

---

Operations on Linked Lists

Insertion

Insertion is usually efficient because you only change references.

Insert at Beginning (O(1))

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

Explanation:

• New node points to current head
• Head updates to new node

Insert at End (O(n))

def insert_at_end(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return
    current = self.head
    while current.next:
        current = current.next
    current.next = new_node

Why O(n)?
You must traverse to the last node.

Optimization: Maintain a tail pointer to make end insertion O(1).

Insert at a Specific Position (O(n))

def insert_at_position(self, index, data):
    new_node = Node(data)

    if index == 0:
        new_node.next = self.head
        self.head = new_node
        return

    current = self.head
    count = 0

    while current and count < index - 1:
        current = current.next
        count += 1

    if current is None:
        raise IndexError("Index out of range")

    new_node.next = current.next
    current.next = new_node

Common mistake: forgetting index == 0 case.

---

Deletion

Deletion requires careful pointer updates.

Delete by Value (O(n))

def delete_by_value(self, value):
    current = self.head

    if current and current.data == value:
        self.head = current.next
        return

    prev = None
    while current and current.data != value:
        prev = current
        current = current.next

    if current is None:
        return  # not found

    prev.next = current.next

What’s happening:

• Find node with the value.
• Link previous node directly to current.next.

Delete by Position (O(n))

def delete_by_position(self, index):
    if self.head is None:
        raise IndexError("Delete from empty list")

    current = self.head

    if index == 0:
        self.head = current.next
        return

    prev = None
    count = 0

    while current and count < index:
        prev = current
        current = current.next
        count += 1

    if current is None:
        raise IndexError("Index out of range")

    prev.next = current.next

---

Searching (O(n))

def search(self, value):
    current = self.head
    index = 0

    while current:
        if current.data == value:
            return index
        current = current.next
        index += 1

    return -1

Note: Linked lists cannot do binary search efficiently because no random indexing.

---

Circular Linked Lists and Their Implementation

In a circular linked list, the last node points back to the head, creating a loop.

Structure:

head -> node1 -> node2 -> node3
 ^                       |
 |_______________________|

Why use circular lists?

• Useful in round-robin scheduling
• Continuous cycling (like playlists)

Example Implementation (Circular Singly Linked List)

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

    def append(self, data):
        new_node = Node(data)

        if not self.head:
            self.head = new_node
            new_node.next = self.head
            return

        current = self.head
        while current.next != self.head:
            current = current.next

        current.next = new_node
        new_node.next = self.head

Important: stopping condition is current.next != head (not None).

---

Applications of Linked Lists

• Implementing stacks and queues
• Music playlists / photo galleries
• Browser history (doubly linked list)
• Memory allocators (conceptually linked blocks)
• Graph adjacency lists (often built using linked-like structures)

---

Summary

Linked lists store data in nodes connected by references. They shine when you need efficient insertions/deletions without shifting elements. Singly linked lists are simpler, doubly linked lists allow backward traversal, and circular linked lists support cyclic processing.