Understanding Linked Lists

Unlike arrays which require contiguous memory blocks, a linked list is a linear data structure where elements, called nodes, are linked using pointers. Each node contains data and a reference (or link) to the next node in the sequence.

Advantages Over Arrrays

Arrays have fixed sizes, requiring resizing and element shifting for insertion/deletion. Linked lists allow dynamic memory allocation, enabling efficient insertions and deletions without reallocation.

Basic Node Structure

class ListNode:
    def __init__(self, data):
        self.data = data  # Store the element
        self.next = None   # Reference to next node

Singly Linked List Implementation

A singly linked list contains nodes where each node points only to its successor.

Core Operations

• is_empty(): Check if list is empty
• size(): Count elements
• traverse(): Display all elements
• insert_front(): Add element at beginning
• insert_end(): Add element at end
• insert_at(): Insert at specific position
• delete(): Remove an element
• contains(): Check if element exists

Complete Implementation

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    
    def is_empty(self):
        return self.head is None
    
    def size(self):
        current = self.head
        elements = 0
        while current:
            elements += 1
            current = current.next
        return elements
    
    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")
    
    def insert_front(self, value):
        new_node = ListNode(value)
        new_node.next = self.head
        self.head = new_node
    
    def insert_end(self, value):
        new_node = ListNode(value)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
    
    def insert_at(self, position, value):
        if position <= 0:
            self.insert_front(value)
        elif position >= self.size():
            self.insert_end(value)
        else:
            new_node = ListNode(value)
            current = self.head
            for _ in range(position - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node
    
    def delete(self, value):
        if self.is_empty():
            return
        
        if self.head.data == value:
            self.head = self.head.next
            return
        
        previous = self.head
        current = self.head.next
        
        while current:
            if current.data == value:
                previous.next = current.next
                return
            previous = current
            current = current.next
    
    def contains(self, value):
        current = self.head
        while current:
            if current.data == value:
                return True
            current = current.next
        return False

# Example Usage
if __name__ == "__main__":
    sll = SinglyLinkedList()
    sll.insert_front(10)
    sll.insert_end(20)
    sll.insert_at(1, 15)
    sll.traverse()
    print("Size:", sll.size())
    print("Contains 15:", sll.contains(15))
    sll.delete(15)
    sll.traverse()

Doubly Linked List Implemantation

Each node in a doubly linked list contains references to both next and previous nodes, enabling bidirectional traversal.

Node Structure

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

Key Methods

class DoublyLinkedList:
    def __init__(self):
        self.head = None
    
    def insert_front(self, value):
        new_node = DoublyListNode(value)
        if not self.head:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
    
    def insert_end(self, value):
        new_node = DoublyListNode(value)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current
    
    def delete(self, value):
        current = self.head
        while current:
            if current.data == value:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                
                if current.next:
                    current.next.prev = current.prev
                return
            current = current.next

Circular Linked List

A circular linked list connects the last node back to the first, forming a circle. In singly circular lists, the last node points to the head.

Implementation Highlights

class CircularLinkedList:
    def __init__(self):
        self.head = None
    
    def insert_end(self, value):
        new_node = ListNode(value)
        if not self.head:
            self.head = new_node
            new_node.next = new_node
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head
    
    def traverse(self):
        if not self.head:
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("(back to head)")

Performance Comparison

*Amortized O(1) for dynamic arrays with capacity management

Linked lists excel at frequent insertions/deletions, particularly at the beginning, while arrays provide faster random access and better cache locality.