← Back to Tutorials Chapter 3

Linked Lists

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node. Unlike arrays, linked lists do not require contiguous memory and can grow or shrink dynamically.

Node Structure

Each node contains two fields: the data and a pointer (or reference) to the next node. The list is accessed through a head pointer that points to the first node.

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

Singly Linked List

In a singly linked list, each node has a single pointer to the next node. The last node points to None.

Insert at Head

def insert_at_head(head, data):
    new_node = Node(data)
    new_node.next = head
    return new_node

Insert at Tail

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

Traverse

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

Search

def search(head, target):
    current = head
    while current:
        if current.data == target:
            return True
        current = current.next
    return False

Delete a Node

def delete_node(head, key):
    if head is None:
        return None
    if head.data == key:
        return head.next
    current = head
    while current.next and current.next.data != key:
        current = current.next
    if current.next:
        current.next = current.next.next
    return head

Reverse

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

Doubly Linked List

Each node has two pointers: prev (to the previous node) and next (to the next node). This allows traversal in both directions and makes deletion at the tail O(1) when a tail pointer is maintained.

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

Circular Linked List

The last node points back to the head, forming a circle. Useful for round-robin scheduling and applications that cycle through a list repeatedly.

Use case: Circular linked lists are used in operating systems for CPU scheduling (round-robin), in multiplayer games for turn management, and in music playlists that loop.

Linked List vs Arrays

Memory: Linked lists use non-contiguous memory; arrays use contiguous memory.
Access: Arrays provide O(1) random access; linked lists require O(n) traversal.
Insertion/Deletion: Linked lists offer O(1) at head/tail (given a pointer); arrays are O(n) for insertions and deletions except at the end.
Cache performance: Arrays benefit from spatial locality; linked lists suffer from cache misses due to scattered nodes.
Size: Linked lists grow naturally; static arrays have a fixed size.

Key insight: Linked lists shine when you need frequent insertions and deletions at arbitrary positions. Arrays shine when you need fast random access and iteration with good cache locality.

Time Complexities

Access: O(n)
Search: O(n)
Insert at head: O(1)
Insert at tail (with tail pointer): O(1)
Delete at head: O(1)
Delete by value: O(n)

Exercise: Implement a function that detects if a linked list has a cycle (i.e., a node's next pointer eventually points back to a previous node). Use Floyd's tortoise-and-hare algorithm (two pointers moving at different speeds).