Chris's Development Blog

Implementing a Basic Linked List in Golang

Almost every language ships with basic data structures. These basic structures at minimum include Arrays and Hashes. Arrays and Hashes are great under certain circumstances, but they aren't always the best solution when trying to solve a problem efficiently.

So one solution that is used often are linked lists. A linked list is effectively a special type of array that consists of a head and tail, each object in the linked list will link to the next item. This allows the linked list to dynamically increase or decrease in memory without having to duplicate arrays when the memory limit has been hit.

Linked lists also have a speed advantage when prepending to the list with a big O of 1, as opposed to an array, which is O(n). They also have an advantage when inserting because when you insert into a linked list you only need to iterate to the desired index and change only the surrounding 2 items, whereas with an array you would need to move the entire thing to the right in order to make room.

Implementation in Golang

Basic Structure

So to start a linked list value will need to contain a value and a pointer to the next value. This value can be any value or any set of values you wish to store in the linked list, I am using an integer as an example.

type LinkedListValue struct {
    next *LinkedListValue
    value int
}

Once you have the linked list value setup, now you need to implement a parent structure.

type LinkedList struct {
    head *LinkedListValue
    tail *LinkedListValue
    length int
}

This structure will hold pointers to the head and tail of the linked list and is the starting point for going into the linked list. Now you have the very basic structures in place. Only thing left is to implement methods to insert and extract data from the linked list.

Setup Methods

I started by implementing setup methods for the structure

func SetupLinkedListValue(value int) LinkedListValue {
    v := LinkedListValue{}
    v.value = value
    return v
}

// Linked list initialize
func SetupLinkedList(startVal int) LinkedList {
    a := LinkedList{}
    first := SetupLinkedListValue(startVal)
    a.head = &first
    a.tail = &first
    a.length = 1
    return a
}

This will setup the linked list with a starting value and set that value to the head and tail of the linked list.

Append, Prepend, and Insert Methods

The next methods that need to be implemented are the append and prepend methods.

To implement append you just need to set the tail pointer to the new value and set the new tail as the linked list tail.

// Append method
func (l *LinkedList) append(value int){
    // Create value holder
    val := SetupLinkedListValue(value)
    // Set tail next to new val
    l.tail.next = &val
    // Increase list length
    l.length++
    // Set new tail
    l.tail = &val
}

And for prepend:

// Prepend method
func (l *LinkedList) prepend(value int){
    val := SetupLinkedListValue(value)
    val.next = l.head
    l.length++
    l.head = &val
    l.cursor = &val
}

Insert is a little different because you need to actually traverse to the value you want to insert.

func (l *LinkedList) traverseToIndex(index int) (val *LinkedListValue){
    val = l.head
    for i:=0; i<index; i++ {
        val = val.next
    }
    return val
}

func (l *LinkedList) insert(index int, value int){
    // Edge case check if head or tail
    if index<=0{
        l.prepend(value)
        return
    }else if index>=l.length-1{
        l.append(value)
        return
    }
    first:= l.traverseToIndex(index-1)
    middle:= SetupLinkedListValue(value)
    last:= first.next

    first.next = &middle
    middle.next = last

    l.length++
}

Get at index method

The last function for the most basic access to the new data structure is get(index).

To get a more efficient for loop you need to implement a cursor system which keeps track of the currently selected value.

// Get method. Will get out values with cursor
func (l *LinkedList) get(index int) int{
    return l.traverseToIndex(index).value
}

After these basic functions are setup it should be relatively simple to use this newly implemented data structure in your next project when you are facing a problem that linked lists can solve.

© 2019 | Chris Gresock All rights reserved