Chapter 3: Linked Lists | Data Structures & Algorithms Complete Book

1.0

What is a Linked List?

A linked list is a linear data structure where elements (nodes) are linked together via pointers or references, rather than stored in contiguous memory like arrays.

Concept & Node Structure

Unlike arrays that store elements in consecutive memory locations, linked lists distribute nodes across memory. Each node contains two things:

Data: The value stored in the node
Link(s): Reference(s) to the next (or previous) node

ℹ

Key Difference: Arrays require contiguous memory; linked lists allow scattered memory locations. This trade-off has profound implications for performance and flexibility.

Visual Node Layout

Singly Linked Node:

┌──────────┬──────┐
│ Data │ Next │─→ (points to next node)
└──────────┴──────┘

Doubly Linked Node:

┌──────┬──────────┬──────┐
←───│ Prev │ Data │ Next │───→
└──────┴──────────┴──────┘

Memory Layout Comparison

Array (Contiguous):

Memory: │ 10 │ 20 │ 30 │ 40 │ 50 │
Index: │ 0 │ 1 │ 2 │ 3 │ 4 │
Address: 1000 1008 1016 1024 1032 (sequential)

Linked List (Scattered):

Node A: Data=10, Next→(addr 5000)
Node B: Data=20, Next→(addr 3000)
Node C: Data=30, Next→(addr 7000)
(Memory addresses are random)

Pointers & References

In C#, we use null references. A node's "next" is either:

A reference to another Node object
null if it's the last node (or first node has no "previous")

C#

// Basic Node Class
public class Node<T>
{
    public T Data { get; set; }
    public Node<T> Next { get; set; }

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

2.0

Singly Linked List

A singly linked list has nodes with a single "Next" reference. You can only traverse forward.

Complete Implementation

C#

public class SinglyLinkedList<T>
{
    private Node<T> head;
    public int Count { get; private set; }

    // Constructor
    public SinglyLinkedList()
    {
        head = null;
        Count = 0;
    }

    // Insert at head - O(1)
    public void InsertAtHead(T data)
    {
        Node<T> newNode = new Node<T>(data);
        newNode.Next = head;
        head = newNode;
        Count++;
    }

    // Insert at tail - O(n)
    public void InsertAtTail(T data)
    {
        Node<T> newNode = new Node<T>(data);

        if (head == null)
        {
            head = newNode;
        }
        else
        {
            Node<T> current = head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
        Count++;
    }

    // Insert at position - O(n)
    public bool InsertAt(int position, T data)
    {
        if (position < 0 || position > Count)
            return false;

        if (position == 0)
        {
            InsertAtHead(data);
            return true;
        }

        Node<T> current = head;
        for (int i = 0; i < position - 1; i++)
        {
            current = current.Next;
        }

        Node<T> newNode = new Node<T>(data);
        newNode.Next = current.Next;
        current.Next = newNode;
        Count++;
        return true;
    }

    // Delete at head - O(1)
    public bool DeleteAtHead()
    {
        if (head == null)
            return false;

        head = head.Next;
        Count--;
        return true;
    }

    // Delete by value - O(n)
    public bool Delete(T data)
    {
        if (head == null)
            return false;

        if (head.Data.Equals(data))
        {
            head = head.Next;
            Count--;
            return true;
        }

        Node<T> current = head;
        while (current.Next != null)
        {
            if (current.Next.Data.Equals(data))
            {
                current.Next = current.Next.Next;
                Count--;
                return true;
            }
            current = current.Next;
        }
        return false;
    }

    // Search - O(n)
    public bool Contains(T data)
    {
        Node<T> current = head;
        while (current != null)
        {
            if (current.Data.Equals(data))
                return true;
            current = current.Next;
        }
        return false;
    }

    // Get value at index - O(n)
    public T GetAt(int index)
    {
        if (index < 0 || index >= Count)
            throw new IndexOutOfRangeException();

        Node<T> current = head;
        for (int i = 0; i < index; i++)
        {
            current = current.Next;
        }
        return current.Data;
    }

    // Traverse and display - O(n)
    public void Display()
    {
        Node<T> current = head;
        while (current != null)
        {
            Console.Write(current.Data + " → ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }
}

Usage Example

C#

var list = new SinglyLinkedList<int>();
list.InsertAtHead(10);
list.InsertAtTail(20);
list.InsertAt(1, 15);
list.Display();  // Output: 10 → 15 → 20 → null

Console.WriteLine(list.Contains(15));  // true
list.Delete(15);
list.Display();  // Output: 10 → 20 → null

3.0

Doubly Linked List

A doubly linked list allows traversal in both directions with both "Next" and "Previous" references.

Node Structure with Prev & Next

C#

public class DoublyNode<T>
{
    public T Data { get; set; }
    public DoublyNode<T> Next { get; set; }
    public DoublyNode<T> Prev { get; set; }

    public DoublyNode(T data)
    {
        Data = data;
        Next = null;
        Prev = null;
    }
}

Doubly Linked List Implementation

C#

public class DoublyLinkedList<T>
{
    private DoublyNode<T> head;
    private DoublyNode<T> tail;
    public int Count { get; private set; }

    public DoublyLinkedList()
    {
        head = null;
        tail = null;
        Count = 0;
    }

    // Insert at head
    public void InsertAtHead(T data)
    {
        DoublyNode<T> newNode = new DoublyNode<T>(data);

        if (head == null)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            newNode.Next = head;
            head.Prev = newNode;
            head = newNode;
        }
        Count++;
    }

    // Insert at tail - O(1) with tail pointer!
    public void InsertAtTail(T data)
    {
        DoublyNode<T> newNode = new DoublyNode<T>(data);

        if (tail == null)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            newNode.Prev = tail;
            tail.Next = newNode;
            tail = newNode;
        }
        Count++;
    }

    // Delete at tail - O(1)
    public bool DeleteAtTail()
    {
        if (tail == null)
            return false;

        if (head == tail)
        {
            head = null;
            tail = null;
        }
        else
        {
            tail = tail.Prev;
            tail.Next = null;
        }
        Count--;
        return true;
    }

    // Traverse forward
    public void DisplayForward()
    {
        DoublyNode<T> current = head;
        while (current != null)
        {
            Console.Write(current.Data + " ⇄ ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }

    // Traverse backward
    public void DisplayBackward()
    {
        DoublyNode<T> current = tail;
        while (current != null)
        {
            Console.Write(current.Data + " ⇄ ");
            current = current.Prev;
        }
        Console.WriteLine("null");
    }
}

💡

Key Advantage: Doubly linked lists allow O(1) tail insertion/deletion if you maintain a tail pointer. Singly lists need O(n) for tail operations (unless they track tail separately).

4.0

Circular Linked List

A circular linked list's last node points back to the first, creating a loop with no end.

Singly Circular Implementation

In a singly circular list, tail.Next points to head instead of null.

C#

public class CircularLinkedList<T>
{
    private Node<T> head;
    private Node<T> tail;
    public int Count { get; private set; }

    public CircularLinkedList()
    {
        head = null;
        tail = null;
        Count = 0;
    }

    // Insert at head
    public void InsertAtHead(T data)
    {
        Node<T> newNode = new Node<T>(data);

        if (head == null)
        {
            head = newNode;
            tail = newNode;
            newNode.Next = newNode;  // Points to itself
        }
        else
        {
            newNode.Next = head;
            tail.Next = newNode;
            head = newNode;
        }
        Count++;
    }

    // Insert at tail - O(1)
    public void InsertAtTail(T data)
    {
        Node<T> newNode = new Node<T>(data);

        if (tail == null)
        {
            head = newNode;
            tail = newNode;
            newNode.Next = newNode;
        }
        else
        {
            newNode.Next = head;  // Circular reference
            tail.Next = newNode;
            tail = newNode;
        }
        Count++;
    }

    // Display (careful with circular!)
    public void Display()
    {
        if (head == null)
            return;

        Node<T> current = head;
        do
        {
            Console.Write(current.Data + " → ");
            current = current.Next;
        } while (current != head);  // Stop when we reach head again
        Console.WriteLine("(back to head)");
    }
}

Doubly Circular Linked List

A doubly circular list combines both prev/next pointers and circular references. Useful for round-robin scheduling and LRU caches.

⚠

Infinite Loop Risk: When traversing circular lists, always have a stopping condition. Without it, your code will loop forever. Use a counter or check if you've returned to the starting node.

5.0

Operations & Complexity

Understanding time complexity is essential for choosing the right linked list variant.

Comprehensive Complexity Table

Operation	Singly (Head Only)	Singly (No Tail)	Singly (With Tail)	Doubly (No Tail)	Doubly (With Tail)
Insert at Head	O(1)	O(1)	O(1)	O(1)	O(1)
Insert at Tail	O(n)	O(n)	O(1)	O(n)	O(1)
Insert at Position	O(n)	O(n)	O(n)	O(n)	O(n)
Delete at Head	O(1)	O(1)	O(1)	O(1)	O(1)
Delete at Tail	O(n)	O(n)	O(n)	O(1)	O(1)
Delete at Position	O(n)	O(n)	O(n)	O(n)	O(n)
Search	O(n)	O(n)	O(n)	O(n)	O(n)
Access by Index	O(n)	O(n)	O(n)	O(n)	O(n)
Traverse	O(n)	O(n)	O(n)	O(n)	O(n)

Detailed Operation Breakdowns

Insertion at Head: Constant time because we don't traverse—just create a new node, set its next pointer, and update head.

Insertion at Tail: With a tail pointer, it's O(1). Without it, we must traverse n nodes, making it O(n).

Insertion at Position: We must traverse to find the position (O(n)), then insert (O(1)). Result: O(n).

Search: Linear search always requires checking every node in the worst case, hence O(n).

Random Access: Unlike arrays, we can't jump to index i—we must follow n pointers. O(n) always.

6.0

Linked Lists vs Arrays

Each data structure excels in different scenarios. Understanding the trade-offs helps you choose wisely.

Detailed Comparison Table

Aspect	Array	Linked List
Memory Layout	Contiguous blocks	Scattered (with pointers)
Random Access	O(1)	O(n)
Insert at Head	O(n) - must shift	O(1)
Delete at Head	O(n) - must shift	O(1)
Insert at Tail	O(1) amortized	O(1) with tail ptr
Memory Overhead	Minimal	Extra pointers (8+ bytes)
Cache Locality	Excellent	Poor (random jumps)
Size Flexibility	Fixed (or resize)	Dynamic, grows naturally
Insertion in Middle	O(n)	O(n) to find position
Search	O(n) linear, O(log n) binary	O(n) only

When to Use Each

✓ Use Arrays When:

Frequent random access (index-based)

Memory is limited (no pointer overhead)

Cache performance matters (CPUs prefer contiguous)

Data size is known and stable

Need O(1) indexing

✓ Use Linked Lists When:

Frequent insertions/deletions at head

Size changes dramatically

No random access needed

Implementing specialized structures (stacks, queues)

Need O(1) head operations

7.0

Advanced Techniques

Master key algorithmic patterns that unlock solutions to many linked list interview problems.

Fast & Slow Pointer (Floyd's Cycle Detection)

Use two pointers moving at different speeds to detect cycles and find cycle start in O(n) time and O(1) space.

C#

// Detects if a cycle exists
public static bool HasCycle<T>(Node<T> head)
{
    Node<T> slow = head;
    Node<T> fast = head;

    while (fast != null && fast.Next != null)
    {
        slow = slow.Next;           // Move 1 step
        fast = fast.Next.Next;     // Move 2 steps

        if (slow == fast)                // They met!
            return true;
    }
    return false;
}

💡

Why it works: If there's a cycle, fast pointer will eventually lap the slow pointer. If no cycle, fast reaches null first. Time: O(n), Space: O(1).

Dummy Head Node Pattern

Simplify code by introducing a dummy head that points to the real head. Eliminates edge case handling for the head node.

C#

// Remove duplicate nodes (using dummy head)
public static Node<int> RemoveDuplicates(Node<int> head)
{
    // Dummy node simplifies logic
    Node<int> dummy = new Node<int>(0);
    dummy.Next = head;

    Node<int> prev = dummy;
    Node<int> current = head;

    while (current != null)
    {
        if (current.Next != null &&
            current.Data == current.Next.Data)
        {
            current = current.Next.Next;  // Skip duplicates
        }
        else
        {
            prev.Next = current;
            prev = current;
            current = current.Next;
        }
    }

    prev.Next = null;  // Terminate the list
    return dummy.Next;  // Return the real head
}

Recursion on Linked Lists

Recursion is natural for linked lists but watch stack depth for large lists.

C#

// Recursive reverse - elegant but O(n) stack space
public static Node<T> ReverseRecursive<T>(Node<T> head)
{
    if (head == null || head.Next == null)
        return head;

    Node<T> newHead = ReverseRecursive(head.Next);

    // Reverse the link
    head.Next.Next = head;
    head.Next = null;

    return newHead;
}

Runner Technique (Two Pointers)

Use two pointers at different distances to find middle or solve problems needing context.

C#

// Find middle node in one pass
public static Node<T> FindMiddle<T>(Node<T> head)
{
    Node<T> slow = head;
    Node<T> fast = head;

    while (fast != null && fast.Next != null)
    {
        slow = slow.Next;
        fast = fast.Next.Next;
    }
    return slow;  // slow is now at middle
}

8.0

Classic Problems with Full Solutions

Interview favorites that test your understanding of linked list fundamentals.

1. Reverse a Linked List

Given a linked list, reverse it both iteratively and recursively. A classic problem testing pointer manipulation.

Two Pointer O(n) Time O(1) Space

1

C#

// Iterative approach - O(n) time, O(1) space
public static Node<T> ReverseIterative<T>(Node<T> head)
{
    Node<T> prev = null;
    Node<T> current = head;

    while (current != null)
    {
        Node<T> nextTemp = current.Next;  // Save next
        current.Next = prev;                // Reverse link
        prev = current;                     // Move prev
        current = nextTemp;                // Move current
    }
    return prev;  // New head
}

// Test
var list = new Node<int>(1);
list.Next = new Node<int>(2);
list.Next.Next = new Node<int>(3);
// Before: 1 → 2 → 3 → null

var reversed = ReverseIterative(list);
// After: 3 → 2 → 1 → null

2. Detect Cycle in Linked List

Determine if a linked list contains a cycle using Floyd's algorithm. Also find the node where the cycle begins.

Floyd Cycle O(n) Time O(1) Space

2

C#

// Detect cycle and find start node
public static Node<T> DetectCycleStart<T>(Node<T> head)
{
    Node<T> slow = head;
    Node<T> fast = head;

    // Step 1: Detect if cycle exists
    while (fast != null && fast.Next != null)
    {
        slow = slow.Next;
        fast = fast.Next.Next;
        if (slow == fast)
            break;
    }

    if (fast == null || fast.Next == null)
        return null;  // No cycle

    // Step 2: Find cycle start
    slow = head;  // Reset slow to head
    while (slow != fast)
    {
        slow = slow.Next;
        fast = fast.Next;
    }
    return slow;  // This is the cycle start
}

3. Find Middle of Linked List

Find the middle node in a single pass using the two-pointer technique.

Runner Technique O(n) Time O(1) Space

3

C#

public static Node<T> FindMiddle<T>(Node<T> head)
{
    if (head == null)
        return null;

    Node<T> slow = head;
    Node<T> fast = head;

    // Move fast by 2, slow by 1
    while (fast != null && fast.Next != null)
    {
        slow = slow.Next;
        fast = fast.Next.Next;
    }
    return slow;
}

// Example: 1 → 2 → 3 → 4 → 5 → null
// Middle is 3

4. Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list in-place.

Merge O(n+m) Time O(1) Space

4

C#

public static Node<int> MergeSortedLists(
    Node<int> l1, Node<int> l2)
{
    Node<int> dummy = new Node<int>(0);
    Node<int> current = dummy;

    while (l1 != null && l2 != null)
    {
        if (l1.Data <= l2.Data)
        {
            current.Next = l1;
            l1 = l1.Next;
        }
        else
        {
            current.Next = l2;
            l2 = l2.Next;
        }
        current = current.Next;
    }

    // Attach remaining nodes
    current.Next = (l1 != null) ? l1 : l2;

    return dummy.Next;
}

// Example:
// l1: 1 → 3 → 5 → null
// l2: 2 → 4 → 6 → null
// Result: 1 → 2 → 3 → 4 → 5 → 6 → null

5. LRU Cache Implementation

Build a Least Recently Used cache using doubly linked list + dictionary for O(1) get/put operations.

Design Pattern O(1) Get/Put Doubly List

5

C#

public class LRUCache
{
    private int capacity;
    private DoublyNode<int> head;
    private DoublyNode<int> tail;
    private Dictionary<int, DoublyNode<int>> cache;

    public LRUCache(int capacity)
    {
        this.capacity = capacity;
        cache = new Dictionary<int, DoublyNode<int>>();
        head = new DoublyNode<int>(0);
        tail = new DoublyNode<int>(0);
        head.Next = tail;
        tail.Prev = head;
    }

    public int Get(int key)
    {
        if (!cache.ContainsKey(key))
            return -1;

        DoublyNode<int> node = cache[key];
        MoveToHead(node);  // Mark as recently used
        return node.Data;
    }

    public void Put(int key, int value)
    {
        if (cache.ContainsKey(key))
        {
            DoublyNode<int> node = cache[key];
            node.Data = value;
            MoveToHead(node);
        }
        else
        {
            DoublyNode<int> newNode = new DoublyNode<int>(value);
            cache.Add(key, newNode);
            AddToHead(newNode);

            if (cache.Count > capacity)
            {
                DoublyNode<int> lru = tail.Prev;
                RemoveNode(lru);
                cache.Remove(lru.Data);
            }
        }
    }

    private void MoveToHead(DoublyNode<int> node)
    {
        RemoveNode(node);
        AddToHead(node);
    }

    private void AddToHead(DoublyNode<int> node)
    {
        node.Next = head.Next;
        node.Prev = head;
        head.Next.Prev = node;
        head.Next = node;
    }

    private void RemoveNode(DoublyNode<int> node)
    {
        node.Prev.Next = node.Next;
        node.Next.Prev = node.Prev;
    }
}

9.0

C# LinkedList<T> Class

When to use the built-in doubly linked list implementation and its capabilities.

Built-In Implementation Details

C# provides LinkedList<T> which is a doubly linked list with O(1) head and tail operations.

C#

// Using C# LinkedList<T>
var linkedList = new LinkedList<int>();

// O(1) operations
linkedList.AddFirst(10);   // Add to head
linkedList.AddLast(20);    // Add to tail

// LinkedListNode<T> for reference
LinkedListNode<int> node = linkedList.Find(10);  // O(n)

// Insert relative to node
linkedList.AddBefore(node, 5);   // O(1) if node exists
linkedList.AddAfter(node, 15);   // O(1) if node exists

// Traversal
foreach (int value in linkedList)
{
    Console.WriteLine(value);
}

// Backward traversal
LinkedListNode<int> current = linkedList.Last;
while (current != null)
{
    Console.WriteLine(current.Value);
    current = current.Previous;
}

When to Use Built-In vs Custom

Use LinkedList<T>

When:

Solving production code problems
Quick prototyping needed
Only need standard operations

Note: Built-in is thoroughly tested and optimized.

Use Custom Implementation

When:

In interviews (shows understanding)
Need custom node data/behavior
Educational purposes

Note: Demonstrates pointer manipulation skills.

10.0

Interview Tips & Common Mistakes

Ace your linked list interviews by avoiding common pitfalls and handling edge cases.

Critical Edge Cases

Edge Case 1

Empty List (Null Head)

Always check if head == null before accessing head.Next. Null pointer exceptions are instant failures.

Edge Case 2

Single Node List

A list with only one node has head.Next == null. Test this separately from empty lists.

Edge Case 3

Two-Node List

Operations like "reverse" or "remove second-to-last" have special behavior with exactly 2 nodes.

Common Mistakes

⚠

Mistake 1: Losing the head pointer. If you're manipulating pointers, always return or save the head. Many solutions fail silently.

⚠

Mistake 2: Infinite loops in traversal. Without proper termination conditions, your code hangs. Always check for null or cycles.

⚠

Mistake 3: Not saving next pointer before modification. When you do current.Next = something, you lose the reference to the rest of the list.

⚠

Mistake 4: Forgetting to update count/size. If you modify the list, remember to track how many nodes exist.

Interview Checklist

1

Clarify the problem: Is the list sorted? Can it be modified in-place? What if it's empty?

2

Draw examples: Sketch 1, 2, and 3-node lists. Show before/after.

3

Handle edge cases first: Write null checks and boundary conditions before main logic.

4

Test pointer changes: Verify every pointer assignment won't cause data loss.

5

Walk through code: Trace execution with actual values, not just conceptually.

6

Analyze complexity: State time and space complexity clearly. Explain why.

Patterns to Master

Pattern	Use Case	Key Insight
Two Pointers (Slow/Fast)	Detect cycle, find middle, remove nth-to-last	Different speeds reveal relationships
Dummy Head Node	Simplify head-related logic	Eliminate special cases for head
Save Next Reference	Before modifying pointers	Prevent losing the rest of the list
Recursion	Reverse, traverse (small lists)	Stack uses O(n) space; watch depth
Three Pointers	Swapping nodes, rearranging	prev, current, next for safety

Linked ListsDynamic Data Structures

What is a Linked List?

Concept & Node Structure

Visual Node Layout

Memory Layout Comparison

Pointers & References

Singly Linked List

Complete Implementation

Usage Example

Doubly Linked List

Node Structure with Prev & Next

Doubly Linked List Implementation

Circular Linked List

Singly Circular Implementation

Doubly Circular Linked List

Operations & Complexity

Comprehensive Complexity Table

Detailed Operation Breakdowns

Linked Lists vs Arrays

Detailed Comparison Table

When to Use Each

Advanced Techniques

Fast & Slow Pointer (Floyd's Cycle Detection)

Dummy Head Node Pattern

Recursion on Linked Lists

Runner Technique (Two Pointers)

Classic Problems with Full Solutions

C# LinkedList<T> Class

Built-In Implementation Details

When to Use Built-In vs Custom

Interview Tips & Common Mistakes

Critical Edge Cases

Common Mistakes

Interview Checklist

Patterns to Master

Linked Lists
Dynamic Data Structures