Data Structures: 3. Linked List

Data Structures: 3. Linked List

Mar 26, 2022
Programming, Go, Data-Structures

Introduction #

A linked list is literally that, a list where each item is linked to the next 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 linked list can vary - in this case we provide a function to check to see if the 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 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
    next *Node
}

type LinkedList struct {
    head *Node
}

func (l *LinkedList) IsEmpty() bool {

    if l.head == nil {
        return true
    }

    return false
}

func (l *LinkedList) Length() int {

    if l.head == nil {
        return 0
    }

    count := 1
    current := l.head

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

    return count
}

func (l *LinkedList) 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)
}

func (l *LinkedList) 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 *LinkedList) 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 *LinkedList) Push(value any) {

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

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

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

    current.next = n
}

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

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

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

        for current.next != nil {
            at++

            if index == at {
                if current.next != nil {
                    n.next = current.next
                }

                current.next = n
                break
            }

            current = current.next
        }
    }
}

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

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

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

func (l *LinkedList) Pop() {

    current := l.head

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

        break
    }

    current.next = nil
}

func (l *LinkedList) 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 {
                current.next = current.next.next
                break
            }
        }

        current = current.next
    }
}

func (l *LinkedList) PopBack() {

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

func main() {

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

    l := &LinkedList{}

    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]
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]
Pop the first item from the list
Nodes: [Two Three Four Five Six]
Pop the third item from the list (first item is item 0)
Nodes: [Two Three Five Six]
Pop the fourth item from the list
Nodes: [Two Three Five]
Pop the first item from the list
Nodes: [Three Five]
Push an item (1) at the start of the list
Nodes: [1 Three Five]
Push an item (2) into the list at position 1 in the list
Nodes: [1 2 Three Five]
Push an item (4) into the list at position 3 in the list
Nodes: [1 2 Three 4 Five]
Push an item (6) at the end of the list
Nodes: [1 2 Three 4 Five 6]
Trying searching for an integer item
Find 4: 4