• Overview
• Singly Linked Lists
• Doubly Linked Lists
• Circular Linked Lists
• Common Operations
• Comparison and Trade-offs
• Exercises

Linked lists are fundamental linear data structures where elements (nodes) are connected via pointers rather than stored contiguously in memory. Unlike arrays, linked lists provide efficient insertion and deletion operations at the cost of direct access.

Each node contains data and one or more pointers to other nodes. The three primary variants—singly, doubly, and circular—differ in their pointer structure and traversal capabilities.

Key characteristics:

• Dynamic size allocation
• Efficient insertion/deletion (O(1) with pointer)
• Sequential access (O(n) for search)
• No memory waste from pre-allocation
• Cache-unfriendly due to non-contiguous memory

The simplest form of linked list where each node contains data and a single pointer to the next node. The last node points to null.

Structure:

struct Node {
    int data;
    Node* next;
};

Advantages:

• Minimal memory overhead (one pointer per node)
• Simple implementation
• Efficient forward traversal
• Easy insertion at head (O(1))

Disadvantages:

• Cannot traverse backwards
• Deletion requires tracking previous node
• No direct access to tail (unless maintained separately)

Common use cases:

• Stack implementation
• Simple queues (with tail pointer)
• Hash table collision resolution (chaining)
• Adjacency lists in graphs

Each node contains data and two pointers: one to the next node and one to the previous node. This enables efficient bidirectional traversal and deletion.

Structure:

struct Node {
    int data;
    Node* next;
    Node* prev;
};

Advantages:

• Bidirectional traversal
• Easier deletion (no need to track previous)
• Efficient insertion before a given node
• Can traverse from any node in either direction

Disadvantages:

• Higher memory overhead (two pointers per node)
• More complex pointer management
• Slightly slower operations due to extra pointer updates

Common use cases:

• LRU cache implementation
• Browser history (forward/back navigation)
• Undo/redo functionality
• Music playlist with previous/next
• Deque (double-ended queue)

A variation where the last node points back to the first node (or head), forming a circle. Can be implemented as singly or doubly circular.

Singly circular: Last node's next points to head.

Doubly circular: Last node's next points to head, and head's prev points to last node.

Advantages:

• Can reach any node from any starting point
• No null pointers to check (except for empty list)
• Natural for round-robin scheduling
• Efficient for cyclic operations

Disadvantages:

• Risk of infinite loops if not handled carefully
• Slightly more complex termination conditions
• Harder to detect end of traversal

Common use cases:

• Round-robin CPU scheduling
• Circular buffers
• Multiplayer game turn management
• Josephus problem
• Music playlist with repeat all

Operation	Singly	Doubly	Circular
Insert at head	O(1)	O(1)	O(1)
Insert at tail	O(n) or O(1)*	O(1)*	O(1)*
Delete at head	O(1)	O(1)	O(1)
Delete given node	O(n)	O(1)	O(1) or O(n)
Search	O(n)	O(n)	O(n)
Access by index	O(n)	O(n)	O(n)
Reverse traversal	O(n) space	O(1)	O(1) if doubly

* With tail pointer maintained

Space complexity:

• Singly: O(n) with n pointers
• Doubly: O(n) with 2n pointers
• Circular: Same as base type (singly or doubly)

When to use singly linked lists:

• Memory is constrained
• Only forward traversal needed
• Implementing stacks or simple queues
• Hash table chaining

When to use doubly linked lists:

• Need bidirectional traversal
• Frequent deletions of arbitrary nodes
• Implementing deques or LRU caches
• Undo/redo functionality

When to use circular linked lists:

• Round-robin scheduling
• Cyclic operations (playlist, game turns)
• Need to loop continuously through elements
• Josephus-type problems

vs. Arrays:

• Linked lists win: Dynamic size, efficient insertion/deletion at known positions
• Arrays win: Cache locality, random access, less memory overhead

Implementation tips:

• Use sentinel/dummy nodes to simplify edge cases
• Maintain tail pointer for O(1) tail operations
• Consider XOR linked lists for space optimization (advanced)
• Use skip lists for O(log n) search in sorted lists

1. Reverse a singly linked list - Implement iterative and recursive solutions. Time: O(n), Space: O(1) for iterative.
2. Detect cycle in linked list - Use Floyd's cycle detection (tortoise and hare). Return the node where cycle begins.
3. Merge two sorted linked lists - Combine two sorted lists into one sorted list. Can you do it in-place?
4. Find middle element - Use slow/fast pointer technique. Handle both odd and even length lists.
5. Remove nth node from end - Single pass solution using two pointers with n-gap.
6. Implement LRU cache - Use doubly linked list + hash map. O(1) get and put operations.
7. Flatten multilevel doubly linked list - Handle child pointers that create nested levels.
8. Clone linked list with random pointer - Each node has next and random pointer. Clone without extra space.
9. Josephus problem - Use circular linked list. Every kth person is eliminated until one remains.
10. Add two numbers represented as linked lists - Each node contains a digit. Handle carry propagation.