A Linked List is a dynamic data structure ideal for fast insertions and deletions. Unlike arrays, its elements aren’t stored contiguously but are linked via pointers.

Anatomy of a Linked List

A Linked List is a collection of nodes, each having:

• Data: The stored value.
• Next Pointer: A reference to the next node.

The list starts with a Head node and ends with a node having a null Next pointer.

Visual Representation

Key Features

• Dynamic Size: Adapts to data volume.
• Non-Contiguous Memory: Flexibility in storage.
• Fast Insertions/Deletions: Limited pointer adjustments needed.

Types of Linked Lists

1. Singly Linked List: Each node has a single pointer to the next node. Traversal is unidirectional: from head to tail.
2. Doubly Linked List: Each node have two pointers: one pointing to the next node and another to the previous node. This allows for bidirectional traversal.
3. Circular Linked List: Like a singly linked list, but the tail node points back to the head, forming a loop.
4. Multi-level Linked List: This specialized type has nodes with multiple pointers, each pointing to different nodes. It’s often used in advanced data structures like multi-level caches.

Common Operations and Time Complexity

• Traversal: Scan through nodes — $O(n)$.
• Insertion at the Beginning: Add a node at the start — $O(1)$.
• Insertion (other cases)/Deletion: Add or remove nodes elsewhere in the list — $O(n)$.
• Search: Locate specific nodes — $O(n)$.
• Sorting: Order or organize nodes in the list. Commonly-used algorithms for linked lists like merge sort have a time complexity of $O(n \log n)$.
• Merging: Combine two lists — $O(n)$ where $n$ is the total number of nodes in both lists.
• Reversal: Flip node order — $O(n)$.

Code Example: Singly Linked List

Here is the Python code:

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

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

    def insert(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            last_node = self.head
            while last_node.next:
                last_node = last_node.next
            last_node.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# Usage
my_list = LinkedList()
my_list.insert(1)
my_list.insert(2)
my_list.insert(3)
my_list.display()

# Output:
# 1
# 2
# 3