Linked Lists in GoLang - Anirudh Duggal

What is a Linked List?

Linked list is a linear data structure whose elements are not stored in continuous memory blocks, unlike array.

This provides multiple benefits in comparison to an array including easy memory allocation, faster operations like insert and delete, etc

You can read more about it here

Creating a Linked List in GoLang

Pointers in GoLang

Pointers in Go are similar to pointers in languages like C/C++. A pointer holds memory address.

Consider the following example to understand pointers better

Code snippet for the above example will look like the following in Go

package main

import "fmt"

func main() {
	var p *int
	var i int

	i = 12

	p = &i
	fmt.Printf("Value of i is stored at memory address %p and is %d", p, *p)
}

Running the above code via go run main.go gives the following output

Value of i is stored at memory address 0x1400000e1b8 and is 12%

Importance of Pointers in Linked Lists

Unlike arrays, linked lists do not store data in continuous memory blocks. Therefore, if a linked list stores 4 integers, those 4 integers could be spread anywhere in the entire memory scope.

But then how to identify where the next value of the linked list is stored? This is where pointers come into picture. Each value of a linked list will store the value itself (int in this case) and a pointer (or the memory address) to the next value

Consider the following example, where a linked list with objects {2, 5, 12, 7} is created. All the blocks in red are memory locations already occupied

Now if we were to use an array, there is no place for 4 consecutive integers in the memory and therefore we would not be able to create an array. We’ll probably get an OOMKilled.

But linked list used the available 4 blocks of memory and spread the elements throughout them. Each element has a pointer (marked with green arrow) to the next element.

In practical, we will need more than 4 bytes for each element since we will have to store int and a pointer to the next int value.

But this is how a linked list looks in memory and one of the major difference between an array and a linked list.

The int value and pointer are packed together in a struct as follows

type Node struct { // a struct of type Node. This is the Node in a LL
  Val int // Val - the actual integer the node stores
  Next *Node // a pointer to the next node
}

LinkedList Implementation

A linked list will have a head. This will point to the first element of the linked list.

Subsequent elements can then be retrieved via the Next pointers

type LinkedList struct { // a struct named LinkedList
  Head *Node // pointer to the first node - the head of the LL
}

Operations on a Linked List

There can be multiple operations that can be done on a linked list, however the most common ones are

Insertion
Deletion
Traversal

Code for these are provided below. There could be multiple different ways of implementing these

Insertion in a Linked List

Insertion in a linked list can be at any position, however we will be covering only insertion at the beginning of the linked list.

You can try the following on your own to test your understanding of linked list insertion

Addition after an element
Addition before an element
Addition at the end of the linked list
Addition to a particular position in linked list

type Node struct {
	Val int
	Next *Node
}

type LinkedList struct {
	Head *Node
}

func insertInLinkedList(ll *LinkedList, val int) {
	newNode := &Node{val, nil}
	if ll.Head == nil {
		ll.Head = newNode
	} else {
		newNode.Next = ll.Head
		ll.Head = newNode
	}
}

Deletion From A Linked List

Similar to insertion, deletion can be of many kinds in a linked list. We will however consider that we want to remove a node with a specific value from the linked list

type Node struct {
	Val int
	Next *Node
}

type LinkedList struct {
	Head *Node
}

func deleteFromLinkedList(ll *LinkedList, val int) bool {
	if ll.Head == nil {
		return false
	}

	if ll.Head.Val == val {
		ll.Head = ll.Head.Next
		return true
	}

	for prev, ptr := ll.Head, ll.Head.Next; ptr != nil; ptr = ptr.Next {
		if ptr.Val == val {
			prev.Next = ptr.Next
			return true
		}
		prev = ptr
	}

	return false
}

Traversing a Linked List

type Node struct {
	Val int
	Next *Node
}

type LinkedList struct {
	Head *Node
}

func traverseLinkedList(ll *LinkedList) {
	for ptr := ll.Head; ptr != nil; ptr = ptr.Next {
		fmt.Printf("| %d | - ", ptr.Val)
	}
	fmt.Printf("nil")
	fmt.Println()
}

Final Code

Following is the code for all of the above operations

package main

import "fmt"

type Node struct {
	Val int
	Next *Node
}

type LinkedList struct {
	Head *Node
}

func insertInLinkedList(ll *LinkedList, val int) {
	newNode := &Node{val, nil}
	if ll.Head == nil {
		ll.Head = newNode
	} else {
		newNode.Next = ll.Head
		ll.Head = newNode
	}
}

func deleteFromLinkedList(ll *LinkedList, val int) bool {
	if ll.Head == nil {
		return false
	}

	if ll.Head.Val == val {
		ll.Head = ll.Head.Next
		return true
	}

	for prev, ptr := ll.Head, ll.Head.Next; ptr != nil; ptr = ptr.Next {
		if ptr.Val == val {
			prev.Next = ptr.Next
			return true
		}
		prev = ptr
	}

	return false
}

func traverseLinkedList(ll *LinkedList) {
	for ptr := ll.Head; ptr != nil; ptr = ptr.Next {
		fmt.Printf("| %d | - ", ptr.Val)
	}
	fmt.Printf("nil")
	fmt.Println()
}

func main () {
	ll := &LinkedList{}
	insertInLinkedList(ll, 5)
	insertInLinkedList(ll, 3)
	insertInLinkedList(ll, 6)

	traverseLinkedList(ll)

	insertInLinkedList(ll, 12)
	traverseLinkedList(ll)

	deleteFromLinkedList(ll, 12)

	traverseLinkedList(ll)

}

Running the above code will yield the following output

❯ go run main.go
| 6 | - | 3 | - | 5 | - nil
| 12 | - | 6 | - | 3 | - | 5 | - nil
| 6 | - | 3 | - | 5 | - nil