Linked Lists in Golang

I really enjoy learning Algorithms & Data Structures. I always implemented them with help of C++, and I still believe it is a great language to do that, though it does not align with my interests, at least not as much as Golang! Therefore, currently I try to write as much in Golang as I can - even Leetcode! 🫡

After reading this post, you will know:

• What is Linked List
• The differences between three kinds of Linked Lists
• Why Linked Lists are bad
• Why Linked Lists are good
• How to implement Linked List along with its most useful methods
• How to sort Linked List

What is Linked List

Linked List is a Data Structure, which is constructed from Nodes. Every node contains information about its value, and a link to the next node. It is similar to a normal list, but it allows for a different memory-allocation strategy. I will write more about it in the further section of this post.

Types of Linked Lists

There are three types of Linked Lists:

• Singly Linked List
• Doubly Linked List
• Circular Linked List (can be either singly or doubly)

Nodes of Singly Linked List contains information only about itself and its next element.

type Node struct {
    next  *Node
    value int
}

Therefore, it does not allow to go backwards when going through the list - if we would know that element that we are looking for is just before the last one, we would have to traverse through the entire list in order to get a reference to it. Of course, there are cases where this lack of information is meaningless, and it saves some memory!

Nodes of Doubly Linked List are alike singly ones, but they contain additional information, about its previous node.

type Node struct {
    next     *Node
    previous *Node
    value    int
}

As mentioned before, this additional information of course does not come for free, it costs some memory - 4 or 8 bytes (depending on the machine architecture) for every node to be exact!

Nodes of Circular Linked List can be the same as either singly or doubly ones, with one exception - the tail - which is last element of the list - in circular linked list it points to the head - first element in the list. On the other hand, tail in non-circular linked lists, points to null (which in Golang is represented as nil)

This circulating pointer may come in handy, but must be used wisely - wrong iteration condition can lead to an infinite loop!

Pros & Cons of Linked Lists

Pros:

• It is dynamic - it can grow/shrink at runtime by allocating/deallocating memory. No pre-allocation is required, therefore no memory is wasted. Unless you let memory leak into your code 😳
• It can be used to implement linear data structures, like Stack or Queue, so knowledge about linked list implementation can be valuable even if not directly.
• Insertion and Deletion does not require shifting values - like it does in an array -, so it is its performance advantage

Cons:

• It requires more memory, to hold information about neighboring nodes.
• Direct access is not possible
• Iterating through the linked list is just slow. Nodes are not stored contiguously in the memory, therefore iterating with pointers is not as effective, than just simply adding X bytes to a pointer of an array, that store values in contiguous memory locations.

Golang Implementation

The following implementation is Circular Doubly Linked List. It does not really differ that much from the other types, so if you learn this one, you should easily be able to write others on you own!

Structs

Let’s start from going through the structures that we will operate on.

type LinkedList[T constraints.Ordered] struct {
	head, tail *Node[T]
}

type Node[T constraints.Ordered] struct {
	next *Node[T]
	prev *Node[T]
	val  T
}

LinkedList will be used as a structure, on which we create our methods, like Insert. It containts pointers to its first and last Node.

Node contains a link to its previous and next node, because it is doubly-linked. It of course, also needs to hold information about its value.

As you can see, we also use generic types to make the code more flexible. constraints.Ordered is a type, which makes sure that < and > operations are available - which is necessary for sorting.

Methods

Insert method, as the name suggests, inserts node to the list. To the end of it, in this case. First, we need to check if the list is empty, in such a case our new node is both head & tail. If that’s not the case - our node set prev property to point to old tail, next to point to the head, in order for the list to be circular, and make the old tail point to the new one. Finally also set inserted node as new tail.

func (ll *LinkedList[T]) Insert(val T) {
	node := &Node[T]{val: val}

	if ll.head == nil {
		ll.head = node
		ll.tail = node
	}

    node.next = ll.head
	node.prev = ll.tail
	ll.tail.next = node
	ll.tail = node
}

I believe Find method is pretty self-explanatory, with the comments I provided, that explains particular blocks.

func (ll *LinkedList[T]) Find(val T) (*Node[T], error) {
	notFoundError := fmt.Errorf("node with value %v does not exist in the list", val)

    // List is empty.
	if ll.head == nil {
		return nil, notFoundError
	}

    // Iterate through the list & return the node if the value matches.
	for curr := ll.head; curr != ll.tail; curr = curr.next {
		if curr.val == val {
			return curr, nil
		}
	}

    // Handle the case of a list with only one node, 
    // that would be omitted by the for loop.
	if ll.tail.val == val {
		return ll.tail, nil
	}

	return nil, notFoundError
}

Update methods uses Find method to get reference to the node, that we want to update. If node with wanted value is not found, we simply forward an error.

If the node is found, we have a reference to it, so we can modify its original value and return nil, to show that no error occurred.

func (ll *LinkedList[T]) Update(val, newVal T) error {
	node, err := ll.Find(val)
	if err != nil {
		return err
	}

	node.val = newVal
	return nil
}

Last but not least, Delete method.

I believe in this case, it will be easier to put explanations directly in the code, so watch out for the comments :)

func (ll *LinkedList[T]) Delete(val T) error {
	node, err := ll.Find(val)
    // There is no node with such a value
	if err != nil {
		return err
	}

	if node == ll.head {
        // Deleted node is the only one node in the list,
        // so we simply delete by making it null,
        // without caring about the pointers.
		if node == ll.tail {
			node = nil
			return nil
		}
        // Deleted node is the head of linked list,
        // so we need to modify tail's next property to
        // keep the list circular.
		ll.tail.next = node.next

        // Update the head
		ll.head = node.next

        // Finally delete the node
        node = nil
		return nil
	}

    // Deleted node is somewhere in the middle, so 
    // we need to update the pointers of neighboring nodes.
	node.next.prev = node.prev
	node.prev.next = node.next

    // Delete the node and return nil to indicate no error.
	node = nil
	return nil
}

Sorting

To understand how to sort Linked List, it is extremely helpful to learn how to merge two sorted linked lists. There is a Leetcode Problem for it, if you want to try yourself, before reading further!

Let’s start with merge function, which merges two sorted linked lists. We will later discover, how we can use it.

Basically, at first we create an empty node, which will be a head of our merged list. Then, we create a curr variable, that at this moment, points to the same address as the head variable. It is needed, because we will “juggle” with it in a moment, and we do not want to lose a pointer to the head.

First, we can see the whole function, to get an overview. It will be easier for me to explain particular sections then.

func (node *Node[T]) merge(other *Node[T]) *Node[T] {
	head := &Node[T]{}
	curr := head

	for node != nil && other != nil {
		if node.val < other.val {
			curr.next = node
			node = node.next
		} else {
			curr.next = other
			other = other.next
		}
		curr = curr.next
	}

	if node != nil {
		curr.next = node
	} else {
		curr.next = other
	}

	return head.next // first node is a dummy node, so we want to skip it
}

As you can see, we operate on Node structure. It will become clear why, later in this section.

Here, basically, we just create an empty node, which will be a head of our merged list. Then, we create a curr variable, that at this moment, points to the same address as the head variable. It is needed, because we will “juggle” with it in a moment, and we do not want to lose a pointer to the head.

	head := &Node[T]{}
	curr := head

This is the most crucial part. We iterate through lists, both starting at first element. Then, we compare values of its current elements and we take the lower one - because we sort in ascending order. If the value of first list was lower, we insert it curr.next = node to our new, merged list, and then we “increase” the pointer to now hold the next node. Similarly for the other list. After the node is inserted, we update our curr pointer, so we won’t end up changing the same node over and over!

for node != nil && other != nil {
    if node.val < other.val {
        curr.next = node
        node = node.next
    } else {
        curr.next = other
        other = other.next
    }
    curr = curr.next
}

Now let’s take a look on a sort function, also defined for Node. It uses a technique called Merge Sort I won’t try to explain it deeply, because Wikipedia already does it great, along with the animations. I recommend to check the link above, before reading further.

In short:

• Check if the list is at least 2 nodes long.
• Create variables to iterate through the list.
  • slow variable iterates normally, one node at the time
  • fast variable iterates faster - two nodes at the time
• Use slow variable that points to the middle of the list in order to separate it.
• Recursively sort newly separated two halves.
• Return merged result.

I know that the last part may be tricky. Remember, that the first call of sort, that we executed on our initial list, will return as last, therefore, merge will happen on totally two different (sorted) halves, which were modified from the recursive functions.

func (node *Node[T]) sort() *Node[T] {
	if node == nil || node.next == nil {
		return node
	}

	slow, fast := node, node, node
	for fast != nil && fast.next != nil {
		slow, fast = slow.next, fast.next.next
	}
    // abandon circular linked list for now, easier to sort with nil
    slow.prev.next = nil 
	rest := slow

	node = node.sort()
	rest = rest.sort()

	return node.merge(rest)
}

And the last part - Sort defined for the LinkedList itself!

Here, we simply update pointers to head, tail & prev properties by iterating through the freshly sorted list.

func (ll *LinkedList[T]) Sort() {
	ll.tail.next = nil
	ll.head = ll.head.sort()
	for tmp := ll.head; tmp.next != nil; tmp = tmp.next {
		tmp.next.prev = tmp
	}
	ll.tail.next = ll.head
}

If you find this sorting algorithm interesting, and you’d like to implement it on your own, I recommend to solve a LeetCode problem - Sort List, which is about sorting a singly linked list, with only Node structure.

Complete Code

Thank you for reading!

If you found some mistake or possible improvement, please reach out to me!