Data Structures: 4. Doubly Linked List

Data Structures: 4. Doubly Linked List

Mar 26, 2022
Programming, Go, Data-Structures

Introduction #

A doubly linked list is the same as a linked list, execept that now each item is linked to both the next one and the previous one. So if you have a linked list with the following items (1, 2, 3, 4) it would look like this:

flowchart LR; H(["HEAD"]) --> A([1]); A([1]) <--> B([2]); B([2]) <--> C([3]); C([3]) <--> D([4]); D([4]) --> E(["NIL"])

The operations available on a doubly linked list can vary - in this case we provide a function to check to see if the doubly linked list is empty or not, a function to get the length of the list, a function to get the items without removing them, a function to list the items without removing them, a function to search the doubly linked list, as well as functions to add or remove items from the front of the list, the back of the list, as well as a specified position in the list.

Solution # 

package main

import "fmt"

type Node struct {
    data any
    prev *Node
    next *Node
}

type DoublyLinkedList struct {
    head *Node
}

func (l *DoublyLinkedList) IsEmpty() bool {

    if l.head == nil {
        return true
    }

    return false
}

func (l *DoublyLinkedList) Length() int {

    count := 0

    if l.head == nil {
        return count
    }

    current := l.head
    count += 1

    for current.next != nil {
        count += 1
        current = current.next
    }

    return count
}

func (l *DoublyLinkedList) List() {

    tmp := []any{}
    current := l.head
    tmp = append(tmp, current.data)

    for current.next != nil {
        current = current.next
        tmp = append(tmp, current.data)
    }

    fmt.Printf("Nodes: %+v\n", tmp)

    tmp = []any{}
    tmp = append(tmp, current.data)

    for current.prev != nil {
        current = current.prev
        tmp = append(tmp, current.data)
    }

    fmt.Printf("Nodes in Reverse: %+v\n", tmp)
}

func (l *DoublyLinkedList) Get() []any {

    tmp := []any{}
    current := l.head
    tmp = append(tmp, current.data)

    for current.next != nil {
        current = current.next
        tmp = append(tmp, current.data)
    }

    return tmp
}

func (l *DoublyLinkedList) Search(term any) any {

    current := l.head

    if current.data == term {
        return current.data
    }

    for current.next != nil {
        current = current.next
        if current.data == term {
            return current.data
        }
    }

    return nil
}

func (l *DoublyLinkedList) Push(value any) {

    n := &Node{}
    n.data = value
    n.next = nil
    n.prev = nil
    current := &Node{}

    if l.head == nil {
        l.head = n
        return
    } else {
        current = l.head

        for current.next != nil {
            current = current.next
        }
    }

    current.next = n
    n.prev = current
}

func (l *DoublyLinkedList) PushAt(index int, value any) {

    at := 0
    n := &Node{}
    n.data = value
    n.next = nil
    n.prev = nil
    current := &Node{}

    if l.head == nil {
        l.head = n
        n.prev = l.head
        return
    } else {
        current = l.head

        for current.next != nil {
            at++

            if index == at {
                if current.next == nil {
                    l.Push(value)
                    return
                } else {
                    n.next = current.next
                    n.next.prev = n
                    n.prev = current
                    current.next = n
                }

                break
            }

            current = current.next
        }

        return
    }

    fmt.Println("Index out of range")
}

func (l *DoublyLinkedList) PushBack(value any) {

    n := &Node{}
    n.data = value
    n.next = nil
    n.prev = nil

    if l.head == nil {
        l.head = n
        return
    } else {
        n.next = l.head
        l.head.prev = n
        l.head = n
    }

}

func (l *DoublyLinkedList) Pop() {

    current := l.head

    for current.next != nil {
        if current.next.next != nil {
            current = current.next
            current.next.prev = current
            continue
        }

        break
    }

    current.next = nil
}

func (l *DoublyLinkedList) PopAt(index int) {
    at := 0
    current := l.head

    if index == 0 {
        l.PopBack()
        return
    }

    for current.next != nil {
        at++

        if at == index {
            if current.next != nil {
                if current.next.next != nil {
                    current.next.next.prev = current
                }
                current.next = current.next.next
                break
            }
        }

        current = current.next
    }
}

func (l *DoublyLinkedList) PopBack() {

    if l.head != nil {
        if l.head.next == nil {
            l.head = nil
        } else {
            l.head.next.prev = nil
            l.head = l.head.next
        }
    } else {
        fmt.Println("Linked list is empty")
    }
}

func main() {

    fmt.Println("Create a new linked list")

    l := &DoublyLinkedList{}

    fmt.Printf("Length of list: %d\n", l.Length())
    fmt.Printf("List is empty?: %v\n", l.IsEmpty())
    fmt.Println("Push seven items into the list")
    fmt.Println("('One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven')")

    l.Push("One")
    l.Push("Two")
    l.Push("Three")
    l.Push("Four")
    l.Push("Five")
    l.Push("Six")
    l.Push("Seven")

    fmt.Println("Display the list")
    l.List()
    fmt.Printf("Length of list: %d\n", l.Length())
    fmt.Printf("List is empty?: %v\n", l.IsEmpty())

    fmt.Println("Search the list")
    fmt.Printf("Find 'One': %v\n", l.Search("One"))
    fmt.Printf("Find 'Seven': %v\n", l.Search("Seven"))
    fmt.Printf("Find 'Ten': %v\n", l.Search("Ten"))

    fmt.Println("Test getting the entire list")
    fmt.Printf("List = %+v\n", l.Get())

    fmt.Println("Pop the last item from the list")
    l.Pop()
    l.List()

    fmt.Println("Pop the first item from the list")
    l.PopBack()
    l.List()

    fmt.Println("Pop the third item from the list (first item is item 0)")
    l.PopAt(2)
    l.List()

    fmt.Println("Pop the fourth item from the list")
    l.PopAt(3)
    l.List()

    fmt.Println("Pop the first item from the list")
    l.PopAt(0)
    l.List()

    fmt.Println("Push an item (1) at the start of the list")
    l.PushBack(1)
    l.List()

    fmt.Println("Push an item (2) into the list at position 1 in the list")
    l.PushAt(1, 2)
    l.List()

    fmt.Println("Push an item (4) into the list at position 3 in the list")
    l.PushAt(3, 4)
    l.List()

    fmt.Println("Push an item (6) at the end of the list")
    l.Push(6)
    l.List()

    fmt.Println("Trying searching for an integer item")
    fmt.Printf("Find 4: %v\n", l.Search(4))
}

Testing # 

Create a new linked list
Length of list: 0
List is empty?: true
Push seven items into the list
('One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven')
Display the list
Nodes: [One Two Three Four Five Six Seven]
Nodes in Reverse: [Seven Six Five Four Three Two One]
Length of list: 7
List is empty?: false
Search the list
Find 'One': One
Find 'Seven': Seven
Find 'Ten': <nil>
Test getting the entire list
List = [One Two Three Four Five Six Seven]
Pop the last item from the list
Nodes: [One Two Three Four Five Six]
Nodes in Reverse: [Six Five Four Three Two One]
Pop the first item from the list
Nodes: [Two Three Four Five Six]
Nodes in Reverse: [Six Five Four Three Two]
Pop the third item from the list (first item is item 0)
Nodes: [Two Three Five Six]
Nodes in Reverse: [Six Five Three Two]
Pop the fourth item from the list
Nodes: [Two Three Five]
Nodes in Reverse: [Five Three Two]
Pop the first item from the list
Nodes: [Three Five]
Nodes in Reverse: [Five Three]
Push an item (1) at the start of the list
Nodes: [1 Three Five]
Nodes in Reverse: [Five Three 1]
Push an item (2) into the list at position 1 in the list
Nodes: [1 2 Three Five]
Nodes in Reverse: [Five Three 2 1]
Push an item (4) into the list at position 3 in the list
Nodes: [1 2 Three 4 Five]
Nodes in Reverse: [Five 4 Three 2 1]
Push an item (6) at the end of the list
Nodes: [1 2 Three 4 Five 6]
Nodes in Reverse: [6 Five 4 Three 2 1]
Trying searching for an integer item
Find 4: 4