LinkedList Implementation in Golang

Introduction

If a reader with a basic understanding of Golang might know that it has data structures like array, slice, map.
But being accustomed to Java, I missed the support of the Collections framework, its simplicity in usage, and multiple options like HashMap, TreeMap, ConcurrentHashMap, etc. which we can use as per our requirements.

Thus it led me to the question of whether if we can implement the same Java Collections in Golang from a curiosity perspective.
I am starting with the first of such implementation with LinkedList.

Let’s start with our implementation.

LinkedList

LinkedList

A linked list is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.

Why LinkedList?

As arrays are contiguous data structures, they can be used to store linear data which has their size already fixed, so the user will need to know the space required by data before implementation.
If a requirement where we have to maintain a dynamic structure, i.e. we don't know the size of data or avoid allocating larger array size if it might not be used later “LinkedList” can come in handy for our use case.

Representation:

A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:

• Data
• Pointer i.e. reference to the next node.

We will be implementing a LinkedList for integer node value, and also provide the below methods

• Insert() / InsertAtPosition()
• GetValue()
• Print()
• DeleteByValue() / DeleteByPosition()

1. Insert a node element in the LinkedList

To insert an element in our LinkedList we would need to perform the below steps

• If the LinkedList is empty, then add the node element as the first element

OR

• If LinkedList is not empty, traverse till the end of the list and insert the element as the last element.

Insert()

2. Insert a node value at a certain position in LinkedList

Let’s say we need to insert a new element at a certain position in the LinkedList, so we need to perform the below steps

In such a case, we have to traverse the list till the provided nth node & change its pointer to point to the new node.

InsertAtPosition()

3. Printing LinkedList Nodes

To print the node values we would be traversing the LinkedList single node at a time and printing the same till the pointer hits “nil” i.e. the end of the LinkedList.

4. Get LinkedList Node Value

We would be implementing a search/get value based on the position.
To retrieve data, we would traverse till the position and return the value/print the same.

5. Delete a node from LinkedList

Removing a node from LinkedList is similar to that of Inserting nodes in LinkedList

Following are the steps we need to do to remove a node:

1. Find the previous node of deleting a node
2. Change the next of previous node with the next of deleting a node

DeleteAtPosition()

Let’s say we don't know about the position of the node considered for deletion, we can do the same by deleting based on value.

• Traverse the list
• Compare the given value to the current node value
• if a match is found then, change the pointer value of the pos-1 node & point it to the next node of deleting node

DeleteByValue

Conclusion

This article tried to explain the basic functionality of LinkedList.
Below are some advantages and disadvantages.

Advantages:

1. Dynamic in size allocation.
2. Ease of insertion/deletion i.e O(n) in time complexity.

Disadvantages:

1. Random access is not allowed. We have to access elements sequentially starting from the first node.
2. Extra memory space for a pointer is required with each element of the list.
3. Not cache-friendly. Since array elements are contiguous locations, there is the locality of reference which is not there in the case of linked lists.

That’s all folks, hope this article has helped you in some understanding of LinkedList and its implementation in Golang.

Code is available on this Github link.