Linked Lists Explained (Python)

A linked list is a linear data structure where elements are not stored at contiguous memory locations. Instead, the elements are linked using pointers. Each element, often called a node, consists of two parts: data and a reference (or link) to the next node in the sequence. The last node typically points to None or null, indicating the end of the list.

Characteristics of Linked Lists:

Dynamic Size: Linked lists can easily grow or shrink during program execution.
Non-contiguous Memory: Nodes can be scattered in memory.
Sequential Access: Elements must be accessed sequentially starting from the first node (head). Random access is not efficient (O(n)).
Efficient Insertions/Deletions: Adding or removing nodes can be done in O(1) time if the position of the node (or its predecessor) is known, as it only involves updating pointers. However, finding the node might take O(n) time.

Types of Linked Lists:

Singly Linked List: Each node points only to the next node in the list. Traversal is unidirectional.
Doubly Linked List: Each node has two pointers: one to the next node and one to the previous node. This allows for bidirectional traversal.
Circular Linked List: The last node points back to the first node (or head), forming a circle. Can be singly or doubly circular.

Singly Linked List Implementation in Python:

First, we define a Node class:


class Node:
    def __init__(self, data):
        self.data = data  # Assign data
        self.next = None  # Initialize next as null

Then, we define the LinkedList class:


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

    # Method to add a new node at the beginning
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # Method to add a new node at the end
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    # Method to insert a new node after a given previous node
    def insert_after_node(self, prev_node_data, data):
        new_node = Node(data)
        current = self.head
        while current:
            if current.data == prev_node_data:
                new_node.next = current.next
                current.next = new_node
                return
            current = current.next
        print(f"Node with data {prev_node_data} not found.")

    # Method to delete a node by key
    def delete_node(self, key):
        current = self.head
        # If head node itself holds the key to be deleted
        if current and current.data == key:
            self.head = current.next
            current = None
            return
        
        prev = None
        # Search for the key to be deleted
        while current and current.data != key:
            prev = current
            current = current.next
        
        # If the key is not present
        if not current:
            print(f"Node with key {key} not found.")
            return
        
        # Unlink the node from linked list
        prev.next = current.next
        current = None

    # Method to print the linked list
    def print_list(self):
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements) if elements else "List is empty")

# Example Usage:
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.prepend(0)
llist.print_list()  # Output: 0 -> 1 -> 2 -> 3

llist.insert_after_node(1, 1.5)
llist.print_list()  # Output: 0 -> 1 -> 1.5 -> 2 -> 3

llist.delete_node(2)
llist.print_list()  # Output: 0 -> 1 -> 1.5 -> 3

llist.delete_node(0) # Delete head
llist.print_list() # Output: 1 -> 1.5 -> 3

llist.delete_node(4) # Node not found

Advantages of Linked Lists:

Dynamic Size: Can easily grow and shrink without overallocating memory.
Ease of Insertion/Deletion: Inserting or deleting elements is more efficient than arrays if the pointer to the node is known (O(1) complexity after locating the node).

Disadvantages of Linked Lists:

No Random Access: Elements must be accessed sequentially from the head (O(n)).
Extra Memory for Pointers: Each node requires extra space to store the pointer(s).
Cache Performance: Nodes are not stored contiguously, which can lead to poorer cache locality compared to arrays.

Linked lists are foundational for other data structures like stacks, queues, and are used in various applications such as implementing adjacency lists for graphs, hash table chaining, and managing dynamic memory allocation.