↔️ Doubly Linked List Basics

Welcome back! You mastered singly linked lists where each person only knows the next person in line. Now let’s learn about Doubly Linked Lists - where each person knows BOTH the previous AND next person!

What is a Doubly Linked List? (Real Life Analogy)

Singly Linked List = One-Way Street

Each person only knows the next person
Can only walk forward
Like a conga line where you can only follow

Doubly Linked List = Two-Way Street

Each person knows both previous and next person
Can walk forward OR backward
Like a line where you can pass things back and forth

Think of it like:

Each person = A node with data
Next pointer = Knows who is in front
Previous pointer = Knows who is behind
The chain = Can move in both directions

How Doubly Linked Lists Work

The Enhanced Node

Each node now has THREE parts:

Data - The actual information
Next - Points to the next person (forward)
Prev - Points to the previous person (backward)

type Node struct {
    data int      // The actual data
    next *Node    // Points forward (next person)
    prev *Node    // Points backward (previous person)
}

The Doubly Linked List Structure

type DoublyLinkedList struct {
    head *Node    // First person in line
    tail *Node    // Last person in line
    size int      // Total people
}

Why track both head and tail?

Head: For starting from the beginning
Tail: For quickly adding to the end (no need to walk!)

Creating Your First Doubly Linked List

Step 1: Create Connected Nodes

// Create three people
person1 := &Node{data: 10}
person2 := &Node{data: 20}
person3 := &Node{data: 30}

// Connect them both ways
person1.next = person2  // person1 knows person2 is next
person2.prev = person1  // person2 knows person1 is previous
person2.next = person3  // person2 knows person3 is next
person3.prev = person2  // person3 knows person2 is previous

// Now we have: person1 <-> person2 <-> person3

Step 2: Create the List

list := &DoublyLinkedList{
    head: person1,  // First person
    tail: person3,  // Last person
    size: 3,
}

Adding Items (Two-Way Connections)

Add to Beginning

func (dll *DoublyLinkedList) addToFront(data int) {
    newPerson := &Node{data: data}

    if dll.head == nil {
        // Empty line - new person is both first and last
        dll.head = newPerson
        dll.tail = newPerson
    } else {
        // Connect new person to current first person
        newPerson.next = dll.head    // New points to old first
        dll.head.prev = newPerson   // Old first points back to new

        // New person becomes first
        dll.head = newPerson
    }

    dll.size++
}

// Example
list := &DoublyLinkedList{}
list.addToFront(10)  // Line: 10
list.addToFront(20)  // Line: 20 <-> 10
list.addToFront(30)  // Line: 30 <-> 20 <-> 10

Add to End

func (dll *DoublyLinkedList) addToEnd(data int) {
    newPerson := &Node{data: data}

    if dll.tail == nil {
        // Empty line
        dll.head = newPerson
        dll.tail = newPerson
    } else {
        // Connect current last to new person
        dll.tail.next = newPerson   // Last points to new
        newPerson.prev = dll.tail   // New points back to last

        // New person becomes last
        dll.tail = newPerson
    }

    dll.size++
}

// Example
list := &DoublyLinkedList{}
list.addToEnd(10)  // Line: 10
list.addToEnd(20)  // Line: 10 <-> 20
list.addToEnd(30)  // Line: 10 <-> 20 <-> 30

Reading in Both Directions

Forward (Normal Direction)

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

    for current != nil {
        fmt.Printf("%d -> ", current.data)
        current = current.next
    }

    fmt.Println("END")
}

// Example: 10 <-> 20 <-> 30
// Output: 10 -> 20 -> 30 -> END

Backward (Reverse Direction)

func (dll *DoublyLinkedList) printBackward() {
    current := dll.tail

    for current != nil {
        fmt.Printf("%d -> ", current.data)
        current = current.prev  // Go backward!
    }

    fmt.Println("END")
}

// Example: 10 <-> 20 <-> 30
// Output: 30 -> 20 -> 10 -> END

Removing Items (Update Both Connections)

Remove from Beginning

func (dll *DoublyLinkedList) removeFromFront() {
    if dll.head == nil {
        fmt.Println("Line is empty!")
        return
    }

    if dll.head == dll.tail {
        // Only one person
        dll.head = nil
        dll.tail = nil
    } else {
        // Second person becomes first
        dll.head = dll.head.next
        dll.head.prev = nil  // No one before first person
    }

    dll.size--
}

// Example: 10 <-> 20 <-> 30
// After removeFromFront(): 20 <-> 30

Remove from End

func (dll *DoublyLinkedList) removeFromEnd() {
    if dll.tail == nil {
        fmt.Println("Line is empty!")
        return
    }

    if dll.head == dll.tail {
        // Only one person
        dll.head = nil
        dll.tail = nil
    } else {
        // Second-to-last becomes last
        dll.tail = dll.tail.prev
        dll.tail.next = nil  // No one after last person
    }

    dll.size--
}

// Example: 10 <-> 20 <-> 30
// After removeFromEnd(): 10 <-> 20

Real Life Example: Browser Tabs

package main

import "fmt"

type BrowserTab struct {
    title string
    url   string
    prev  *BrowserTab
    next  *BrowserTab
}

type TabList struct {
    current *BrowserTab
    count   int
}

func (tl *TabList) addTab(title, url string) {
    newTab := &BrowserTab{title: title, url: url}

    if tl.current == nil {
        // First tab
        tl.current = newTab
    } else {
        // Add after current tab
        newTab.prev = tl.current
        newTab.next = tl.current.next

        if tl.current.next != nil {
            tl.current.next.prev = newTab
        }

        tl.current.next = newTab
        tl.current = newTab  // Switch to new tab
    }

    tl.count++
}

func (tl *TabList) switchToNext() {
    if tl.current != nil && tl.current.next != nil {
        tl.current = tl.current.next
        fmt.Printf("Switched to: %s\n", tl.current.title)
    } else {
        fmt.Println("No next tab!")
    }
}

func (tl *TabList) switchToPrevious() {
    if tl.current != nil && tl.current.prev != nil {
        tl.current = tl.current.prev
        fmt.Printf("Switched to: %s\n", tl.current.title)
    } else {
        fmt.Println("No previous tab!")
    }
}

func (tl *TabList) showAllTabs() {
    if tl.current == nil {
        fmt.Println("No tabs open")
        return
    }

    // Find first tab
    first := tl.current
    for first.prev != nil {
        first = first.prev
    }

    // Print all tabs
    current := first
    for current != nil {
        marker := "  "
        if current == tl.current {
            marker = "->"
        }
        fmt.Printf("%s %s (%s)\n", marker, current.title, current.url)
        current = current.next
    }
}

func main() {
    tabs := &TabList{}

    tabs.addTab("Google", "google.com")
    tabs.addTab("GitHub", "github.com")
    tabs.addTab("Stack Overflow", "stackoverflow.com")

    fmt.Println("All tabs:")
    tabs.showAllTabs()

    fmt.Println("\nSwitching to next:")
    tabs.switchToNext()
    tabs.showAllTabs()

    fmt.Println("\nSwitching to previous:")
    tabs.switchToPrevious()
    tabs.showAllTabs()
}

Output:

All tabs:
-> Google (google.com)
  GitHub (github.com)
  Stack Overflow (stackoverflow.com)

Switching to next:
  Google (google.com)
-> GitHub (github.com)
  Stack Overflow (stackoverflow.com)

Switching to previous:
-> Google (google.com)
  GitHub (github.com)
  Stack Overflow (stackoverflow.com)

Doubly vs Singly Linked Lists

Feature	Singly Linked List	Doubly Linked List
Direction	Forward only	Forward and backward
Add to start	Fast	Fast
Add to end	Slow (walk to end)	Fast (use tail)
Remove from end	Slow	Fast
Memory	Less (1 pointer)	More (2 pointers)
Complexity	Simpler	More complex

Insert at Specific Position

func (dll *DoublyLinkedList) insertAt(position int, data int) {
    if position < 0 || position > dll.size {
        fmt.Println("Invalid position")
        return
    }

    if position == 0 {
        dll.addToFront(data)
        return
    }

    if position == dll.size {
        dll.addToEnd(data)
        return
    }

    // Find the position
    current := dll.head
    for i := 0; i < position-1; i++ {
        current = current.next
    }

    // Insert between current and current.next
    newNode := &Node{data: data}
    newNode.next = current.next
    newNode.prev = current

    current.next.prev = newNode
    current.next = newNode

    dll.size++
}

Practice Problems - Build Your Skills!

Exercise 1: Music Playlist with Previous/Next

Create a doubly linked list for songs. Add functions to:

Add songs to playlist
Play next song
Play previous song
Show current song
Jump to specific song

Exercise 2: Browser History

Implement browser back/forward navigation:

Visit new page (add to history)
Go back (previous page)
Go forward (next page)
Show current page
Show full history

Exercise 3: Text Editor Cursor

Simulate text editor with cursor:

Move cursor left/right
Insert characters at cursor
Delete characters at cursor
Show current text with cursor position

Common Mistakes to Avoid

Forgetting to Update Both Pointers

// WRONG: Only updated next, forgot prev!
current.next = newNode
// Missing: newNode.prev = current

Breaking the Chain

// WRONG: This breaks backward connections!
node.prev = nil  // Now you can't go backward!

Solution: Always update both directions

// RIGHT: Update both pointers
newNode.next = current.next
newNode.prev = current

if current.next != nil {
    current.next.prev = newNode
}
current.next = newNode

Key Takeaways - Doubly Linked List Basics

Doubly linked lists have both next and prev pointers
Head and tail pointers enable fast operations at both ends
Bidirectional traversal allows moving forward and backward
More memory but more flexibility than singly linked lists
Perfect for applications needing back-and-forth navigation

Next: Master advanced doubly linked list operations and complex algorithms! 🌟

Ready for advanced doubly linked list techniques? Let’s explore complex operations and real-world applications! 🚀

Popular Topics

Categories