Implementing Linkedlists using Golang

Introduction

While learning about Go I noticed that Go’s standard library doesn’t have a package for various data sturctures like linkedList, tree, graph, stack, queue, heap, etc. So, I thought why not do it by myself. Hence I wrote dsa_go, a Go module which has datastructures not implemented in Go’s standard library.

With this blog I will try my best to cover these topics:

• What is Linkedlist?
  • Array vs Linkedlists
  • What comprises a linked list?
• Types of linkedlists.
• Use of linkedlists in real life.

So, lets get to it!

Note: for this blog I am considering that the reader has some prior or minimal knowledge of Golang.

What is Linkedlist?

A linkedlist is a linear data structure in which data is stored at non-contiguous(non-consecutive) memory locations. Each element in a linked list is linked to the next element using a pointer called a next pointer.

Array vs Linkedlists

An array is a linear sequence of elements and linkedlist is also a linear sequence of elements. So, what’s the difference between the two? Let’s take a look at few differences between an array and a linkedlist:

• Memory allocation: An array’s elements are stored at contiguous(consecutive) memory locations whereas a linkedlist’s elements are stored at non-contiguous(non-consecutive) memory locations. In an array memory is allocated at runtime whereas a linkedlist is dynamically initialized.
• Size: Arrays have fixed size whereas a linkedlist can increase and decrease in size.
• Accessing elements: In an array we can easily access elements with their index whereas in a linkedlist no matter what we need to traverse it to fetch the element.
• Insertion and deletion: Insertion and deletion in an array takes more time than a linkedlist.

What comprises a linkedlist?

A linked list is made up of multiple nodes where each node points to the next node in the sequence.

Node

A node can be thought of as a struct which comprises of data to store and a reference to next node in sequence.

A node struct looks like this:

type Node struct{
    data int
    next *Node
}

data can be of any datatype(string, double, struct, etc) available in Go.

First node in a linkedlist is called head of a linked list and last data node is called tail of a linked list. Tail of the linkedlist always points to a null node.

A linkedlist struct will look like this:

type LinkedList struct{
    head *Node
    size int
}

size is not mandatory in a linkedlist, its good to have. size makes it easier to keep track of size of linkedlist.

Types of linkedlists

Linkedlists are broadly of 3 types:

• Singly linkedlist: In this type of linkedlist each node points only to the next node in sequence.
• Doubly linkedlist: In this type of linkedlist each node can point to next as well as the previous node in the sequence. Hence in doubly linkedlist we have one more pointer in node called previous.
• Circular linkedlist: In this type of linkedlist each node points to the next node sequence, except the tail points to the head of linkedlist. Circular linkedlist is pretty much a Singly Linkedlist whose tail points to it’s head rather then pointing to a null node.

Use of linkedlists in real life

There are various uses of linkedlists in our real life, some of them are:

• Web browser: A doubly linkedlist is used to maintain previous and next web pages for a user’s session.
• Music player: A doubly linked list is used by a music player to maintain its previous and next track in a playlist.
• Redo and Undo: A doubly linked list can be used to implement undo and redo operations for a text editor.
• Implementation of stack and queue: A linked list can also be used to implement stack and queue.

Closing words

In upcoming blogs we will look at:

• Implementation of singly linkedlist
• Implementation of doubly linkedlist
• Implementation of circular linkedlist and also all the code associated with these.

I hope you enjoyed reading this blog and it added some value.