🌟 Doubly Linked List Advanced Operations

Welcome to the final chapter of linked lists! You now understand both singly and doubly linked lists. Let’s explore advanced operations and real-world applications that make doubly linked lists shine.

Advanced Operations Overview

We’ll cover:

Reversing the entire list
Finding middle elements
Complex insertions and deletions
LRU Cache implementation
Text editor simulation
Comparison with singly linked lists

1. Reverse the Entire List

Reversing a doubly linked list is elegant because of the prev pointers!

func (dll *DoublyLinkedList) reverse() {
    current := dll.head

    // Swap head and tail
    dll.head, dll.tail = dll.tail, dll.head

    // Swap all next/prev pointers
    for current != nil {
        // Swap this node's pointers
        current.next, current.prev = current.prev, current.next

        // Move to next node (which is now the old prev)
        current = current.prev
    }
}

// Example: 10 <-> 20 <-> 30
// After reverse: 30 <-> 20 <-> 10

Why it’s elegant:

No extra space needed
Just swap all pointers
Head and tail swap places

2. Find Middle Element

Same two-pointer technique, but now we can traverse backward too!

func (dll *DoublyLinkedList) findMiddle() int {
    if dll.head == nil {
        return -1
    }

    slow := dll.head  // Moves one step
    fast := dll.head  // Moves two steps

    for fast != nil && fast.next != nil {
        slow = slow.next
        fast = fast.next.next
    }

    return slow.data
}

// Example: 10 <-> 20 <-> 30 <-> 40 <-> 50
// Middle: 30

3. Advanced Insert and Delete Operations

Insert Before a Specific Node

func (dll *DoublyLinkedList) insertBefore(target *Node, data int) {
    if target == nil {
        return
    }

    newNode := &Node{data: data}

    // Insert before target
    newNode.prev = target.prev
    newNode.next = target

    if target.prev != nil {
        target.prev.next = newNode
    } else {
        // target was head
        dll.head = newNode
    }

    target.prev = newNode
    dll.size++
}

Delete a Specific Node

func (dll *DoublyLinkedList) deleteNode(target *Node) {
    if target == nil {
        return
    }

    // Update pointers
    if target.prev != nil {
        target.prev.next = target.next
    } else {
        // target was head
        dll.head = target.next
    }

    if target.next != nil {
        target.next.prev = target.prev
    } else {
        // target was tail
        dll.tail = target.prev
    }

    dll.size--
}

Real Life Example: Text Editor Undo/Redo

package main

import "fmt"

type EditAction struct {
    description string
    prev        *EditAction
    next        *EditAction
}

type EditHistory struct {
    current *EditAction
}

func (eh *EditHistory) performAction(description string) {
    newAction := &EditAction{description: description}

    if eh.current != nil {
        eh.current.next = newAction
        newAction.prev = eh.current
    }

    eh.current = newAction
}

func (eh *EditHistory) undo() {
    if eh.current == nil {
        fmt.Println("Nothing to undo!")
        return
    }

    fmt.Printf("Undoing: %s\n", eh.current.description)
    eh.current = eh.current.prev
}

func (eh *EditHistory) redo() {
    if eh.current == nil || eh.current.next == nil {
        fmt.Println("Nothing to redo!")
        return
    }

    eh.current = eh.current.next
    fmt.Printf("Redoing: %s\n", eh.current.description)
}

func (eh *EditHistory) showHistory() {
    if eh.current == nil {
        fmt.Println("No actions")
        return
    }

    // Find first action
    first := eh.current
    for first.prev != nil {
        first = first.prev
    }

    // Show all actions
    current := first
    for current != nil {
        marker := "  "
        if current == eh.current {
            marker = "->"
        }
        fmt.Printf("%s %s\n", marker, current.description)
        current = current.next
    }
}

func main() {
    history := &EditHistory{}

    history.performAction("Typed 'Hello'")
    history.performAction("Typed ' World'")
    history.performAction("Added exclamation mark")

    fmt.Println("Action history:")
    history.showHistory()

    fmt.Println("\nUndo:")
    history.undo()
    history.showHistory()

    fmt.Println("\nUndo again:")
    history.undo()
    history.showHistory()

    fmt.Println("\nRedo:")
    history.redo()
    history.showHistory()
}

Advanced Application: LRU Cache

LRU (Least Recently Used) Cache removes oldest items when full.

package main

import "fmt"

type CacheNode struct {
    key   int
    value int
    prev  *CacheNode
    next  *CacheNode
}

type LRUCache struct {
    capacity int
    cache    map[int]*CacheNode
    head     *CacheNode // Most recently used
    tail     *CacheNode // Least recently used
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*CacheNode),
    }
}

func (c *LRUCache) Get(key int) int {
    if node, exists := c.cache[key]; exists {
        c.moveToFront(node)
        return node.value
    }
    return -1
}

func (c *LRUCache) Put(key, value int) {
    if node, exists := c.cache[key]; exists {
        node.value = value
        c.moveToFront(node)
        return
    }

    // Add new node
    newNode := &CacheNode{key: key, value: value}
    c.cache[key] = newNode
    c.addToFront(newNode)

    // Remove oldest if over capacity
    if len(c.cache) > c.capacity {
        c.removeTail()
    }
}

func (c *LRUCache) moveToFront(node *CacheNode) {
    if node == c.head {
        return
    }

    c.removeNode(node)
    c.addToFront(node)
}

func (c *LRUCache) addToFront(node *CacheNode) {
    node.next = c.head
    node.prev = nil

    if c.head != nil {
        c.head.prev = node
    }

    c.head = node

    if c.tail == nil {
        c.tail = node
    }
}

func (c *LRUCache) removeNode(node *CacheNode) {
    if node.prev != nil {
        node.prev.next = node.next
    } else {
        c.head = node.next
    }

    if node.next != nil {
        node.next.prev = node.prev
    } else {
        c.tail = node.prev
    }
}

func (c *LRUCache) removeTail() {
    if c.tail == nil {
        return
    }

    delete(c.cache, c.tail.key)
    c.removeNode(c.tail)
}

func main() {
    cache := NewLRUCache(2)

    cache.Put(1, 1)
    cache.Put(2, 2)
    fmt.Println("Get 1:", cache.Get(1)) // Returns 1

    cache.Put(3, 3) // Removes key 2
    fmt.Println("Get 2:", cache.Get(2)) // Returns -1

    cache.Put(4, 4) // Removes key 1
    fmt.Println("Get 1:", cache.Get(1)) // Returns -1
    fmt.Println("Get 3:", cache.Get(3)) // Returns 3
    fmt.Println("Get 4:", cache.Get(4)) // Returns 4
}

Advanced Application: Text Editor with Cursor

package main

import "fmt"

type CharNode struct {
    char rune
    prev *CharNode
    next *CharNode
}

type TextEditor struct {
    cursor *CharNode
    head   *CharNode
}

func (te *TextEditor) insertChar(char rune) {
    newNode := &CharNode{char: char}

    if te.cursor == nil {
        // Empty document
        te.head = newNode
        te.cursor = newNode
        return
    }

    // Insert after cursor
    newNode.next = te.cursor.next
    newNode.prev = te.cursor

    if te.cursor.next != nil {
        te.cursor.next.prev = newNode
    }

    te.cursor.next = newNode
    te.cursor = newNode // Move cursor to new char
}

func (te *TextEditor) deleteChar() {
    if te.cursor == nil {
        return
    }

    if te.cursor.prev != nil {
        // Delete current char, move cursor left
        te.cursor.prev.next = te.cursor.next
        if te.cursor.next != nil {
            te.cursor.next.prev = te.cursor.prev
        }
        te.cursor = te.cursor.prev
    } else if te.cursor.next != nil {
        // Cursor at start, delete next char
        te.cursor.next.prev = nil
        te.head = te.cursor.next
        te.cursor = te.head
    } else {
        // Only char in document
        te.head = nil
        te.cursor = nil
    }
}

func (te *TextEditor) moveCursorLeft() {
    if te.cursor != nil && te.cursor.prev != nil {
        te.cursor = te.cursor.prev
    }
}

func (te *TextEditor) moveCursorRight() {
    if te.cursor != nil && te.cursor.next != nil {
        te.cursor = te.cursor.next
    }
}

func (te *TextEditor) getText() string {
    if te.head == nil {
        return ""
    }

    result := ""
    current := te.head

    for current != nil {
        result += string(current.char)
        current = current.next
    }

    return result
}

func (te *TextEditor) getTextWithCursor() string {
    if te.head == nil {
        return "|"
    }

    result := ""
    current := te.head

    for current != nil {
        if current == te.cursor {
            result += "|"
        }
        result += string(current.char)
        current = current.next
    }

    if te.cursor == nil || te.cursor.next == nil {
        result += "|"
    }

    return result
}

func main() {
    editor := &TextEditor{}

    editor.insertChar('H')
    editor.insertChar('e')
    editor.insertChar('l')
    editor.insertChar('l')
    editor.insertChar('o')

    fmt.Println("Text:", editor.getTextWithCursor())

    editor.moveCursorLeft()
    editor.moveCursorLeft()
    fmt.Println("Cursor moved left:", editor.getTextWithCursor())

    editor.insertChar(' ')
    editor.insertChar('W')
    fmt.Println("After insert:", editor.getTextWithCursor())

    editor.deleteChar()
    fmt.Println("After delete:", editor.getTextWithCursor())
}

Performance Comparison: Singly vs Doubly

Operation	Singly Linked List	Doubly Linked List
Add to front	O(1)	O(1)
Add to end	O(n)	O(1)
Remove from front	O(1)	O(1)
Remove from end	O(n)	O(1)
Insert at position	O(n)	O(n)
Delete at position	O(n)	O(n)
Reverse	O(n)	O(n)
Find middle	O(n)	O(n)
Memory per node	1 pointer	2 pointers

When to Use Each Type

Use Singly Linked Lists when:

Memory is critical - less overhead
Only forward traversal needed
Simple operations - add/remove from front
Building stacks, queues - natural fit

Use Doubly Linked Lists when:

Bidirectional traversal needed
Frequent end operations - add/remove from back
Complex navigation - previous/next operations
Building caches, editors - back-and-forth movement

Practice Challenges - Master Level

Challenge 1: Design Browser History

Implement browser with back/forward buttons and history.

Challenge 2: LRU Cache with TTL

Extend LRU cache with time-to-live for entries.

Challenge 3: Text Editor with Undo

Add undo/redo functionality to text editor.

Challenge 4: Music Player with Shuffle

Implement playlist with shuffle, repeat, and queue management.

Simulate file system with cd, ls, mkdir operations.

Real-World Applications Summary

1. Browser History & Tabs

Back/forward navigation
Tab management
Session restoration

2. Text Editors & IDEs

Cursor movement
Undo/redo stacks
Multi-cursor support

3. Caching Systems

LRU eviction
Database query caching
Memory management

4. Media Players

Playlist navigation
Shuffle algorithms
Queue management

5. Operating Systems

Process scheduling
Memory page replacement
File system operations

Key Takeaways - Linked List Mastery

Singly linked lists: Simple, memory-efficient, forward-only
Doubly linked lists: Flexible, bidirectional, more memory
Choose based on access patterns: forward-only vs bidirectional
Real applications: browsers, editors, caches, players
Advanced techniques: LRU, undo/redo, complex traversals

What’s Next in Your DSA Journey?

You’ve conquered linked lists! Next up: Stacks and Queues - fundamental data structures that build on what you’ve learned.

Coming up: Stacks - like a stack of plates, last in, first out! 📚

Congratulations! You’ve mastered linked lists. Ready to stack things up? Let’s explore stacks and queues! 🚀

Popular Topics

Categories