Linked List Tutorial for New Gophers
This article discusses the concept of a linear linked list and its implementation in Go.
What Singly Linked List is
A singly linked list is a linear, dynamic data structure where each element is a separated object. Together, they represent a sequence. A basic form of a node is data and a pointer to the next node.
The first node is called head and the last node is called tail. Head gives access to the entire linked list and tail gives access to the last node. The next field of the last node is nil, which indicates the end of the linked list.
Advantages:
- A linked list is dynamic in size which means they can grow and shrink as needed.
- A linked list has an efficient memory utilization. You do not need to specify the number of elements during a declaration. Memory is allocated when you need to insert a node and deallocated when a node is removed.
Disadvantages:
- A linked list consumes more space because of a pointer to store an address.
- Searching for a node can be time-consuming due to traverse. We cannot randomly access a node with an index N, instead, we iterate the list to find the node.
Linked List Type
Before writing the code we need to declare two data types:
- A List type will encapsulate all the complexity related to work with pointers. The List type consists of a head which points to the first node and a tail which points to the last node.
- A Node type is a struct with a data field and a reference to a node of the same type. The data has a type interface{}, so we can insert values of any type in the linked list. The next field is a pointer to the next node. Since a node contains a pointer to a node of the same type, the node is called self-referential.
Linked List Methods
This section discusses the implementation of a linked list (or list) methods and its illustrations.
In these code samples we use a mark node, which has the same structure as the Node type. Mark is a specific node, before/after we insert a new node, or we need to delete, or we use to get the previous node.
We do not compare nodes by the data field because it is not clear what type of data nodes have. For example string, integer, float etc. So, we compare only nodes.
list.InsertLast(value Data) *Node
This method inserts a new node at the end of the list and returns the inserted node.
Before inserting a node we need to consider two cases:
- the list is empty,
- the list is non-empty.
In the first case we check with list.head == nil. And we insert a new node in the list as a head and a tail (only one node in the list).
The second case is illustrated in picture #2. Here we have a list which consists of several nodes: 1→ 2→nil. A new node is Node{data:3, next:nil}. Since we have access to the tail, we do not need to traverse the list. We insert the new node in list.tail.next and change the old tail with the new one list.tail = newNode.
list.InsertFront(value Data) *Node
This method inserts a new node at the beginning of the list and returns the inserted node.
Here, we check the same cases as in the InsertLast() method.
If a list is empty, we create both a head and a tail. We assign a new node with the following code list.head = newNode and list.tail = newNode to the head and the tail respectively.
In the picture #3 we insert Node{data:3,next:nil} in the non-empty list. To connect newNode to the first node in the list we use newNode.next = list.head, because the current head is Node{data:1,next: next node}, and then change the head in the list with list.head = newNode.
list.InsertBefore(value Data, mark *Node) *Node
This method inserts a new node before mark in the list and returns the inserted node.
The first step is to check that mark != nil. If mark is nil, the method stops the execution because we can not insert a nil node in the list. Nil node contains neither data nor a link to the next node.
Then we check whether the head is equal to mark or not. If it is equal, we assign the current head to newNode and return newNode. If it is not equal, we traverse the list to find node.next == mark.
In the following picture we show how to find mark in a full list, which has a head, a middle node, and a tail. Here we have a list 3→ 1→ 2→nil. We need to insert Node{data:4, next: mark} before mark. Mark is Node{data:1, next: next node}. Starting from the head we iterate the list and check a condition node.next == mark. If it is true, we assign newNode to node.next with the following statement node.next = newNode. So, the new node now goes before mark.
If the method returns nil, mark does not exist in the list.
list.InsertAfter(value data, mark *Node) *Node
This method inserts a new node after mark in the list, and returns the inserted node.
Checking mark is equal to the InsertBefore() method.
If mark is not nil, we iterate the list to find the node that is equal to mark. In the picture #5 you see an illustration of how the method works. Initially, we have a list with several nodes 3 → 1 → 2→nil. If we need to insert newNode after mark, we go through the list and search for node == mark. If found, we assign newNode to node.next. So, now newNode goes after mark.
If mark is not found, mark does not exist in the list.
Also, mark can be equal to the tail. In this case, we just assign newNode to the tail with the following expression list.tail = newNode.
Both InsertBefore() and InsertAfter() methods do not check that head == nil because it is assumed that the list must be non-empty to insert a new node before or/and after the existing one.
node.Next() *Node
This method returns the next node.
Since we have a link to the next node, we can return the node with return node.next code. A receiver for the method is a node, instead of a list.
list.Prev(mark *Node) *Node
This method returns the node before mark.
In a linear linked list we do not have access to the previous node. In this case, we traverse the list and compare node.next with mark. If they are equal, we return the current node. If they are not equal, mark does not exist.
list.Delete(mark *Node) error
This method deletes mark from the list.
There are two cases to check before deleting mark:
- mark can be head,
- mark can be after head.
The first case is checked with the following expression:
In other words, if the first node is equal mark, we assign the next node (after the first) to the head. And if under this condition mark is also equal tail (this happens when there is one node in a list) then list.tail == nil.
The second case is checked with the following statement:
In picture #6 you see how we implement the preceding if condition.
We have a list which consists of several nodes 3→ 1→ 4→ 2→nil. Mark is Node{data:4, next: next node}. On the second iteration we get node.next == mark. Then, the current node in this iteration connects to the mark.next. So, mark is deleted from the list.
In this condition we check if the last node is also equal mark. If true, we change list.tail = node.
The method returns an error, if mark does not exist.
list.Size() int
This method returns a size of the list.
If the head == nil, we return 0. If the list is non-empty we traverse it and increment the size variable unless the end of the list.
GitHub
Source code with tests you can see here.
