Writing A LinkedList In Golang [Data Structures In Go]
Being a somewhat hobbyist Gopher who has been experimenting with the Go language for over a year, I thought it would be fun to share a post on how to implement a singly-linked list in Go as quickly and as simply as possible.
If you don’t know what a linked list is, you can read up about it at Tutorials Point, W3Schools, and Geeks For Geeks. The linked list we shall be implementing will have the following basic methods that are responsible for how we use them:
- Append -> Adds a node to the end of the linked list.
- Remove -> Removes a node from the linked list.
- Contains -> This returns a true or false value if the data is in the list.
- Get -> Returns the node that has the data.
Note: The Go standard library has a List package that implements the linked-list data structure.
The Node and LinkedList Type
The first thing we need is to create a structure that represents each node in the linked list. For this example, each node will have an integer value called data and a second value called next, which is a pointer to the next node.
type node struct { data int next *node}
The next thing we need is the basic structure of our linked list, which is a struct type. The linked list struct will have head and tail values, each holding a pointer reference to the beginning and end nodes of the linked list. It will also have a length value that keeps track of how long the linked list is.
type linkedList struct { head *node tail *node length int}
The Append Method
The append method, which is also known as function receiver in Go, is responsible for adding a new node containing new data to the linked list.
func (list *linkedList) append(data int) {//creates a new node that will be added to the linkedList newNode := &node{ data: data, }
if list.head == nil { list.head = newNode list.tail = newNode } else { list.tail.next = newNode list.tail = newNode } //increase the length value of the linked list by one list.length++}
The append method receives the integer data that needs to be added to the linked list as an argument. It first creates a node from the value and assigns the pointer reference to the variable newNode. The next step is to check if the current linked list has no head and, if it does, it assigns the new Node created to the head and tail of the linked list.
If there is a head node present, the tail node’s next value will be assigned the new node(newNode) and the new node created earlier will be made the tail node. Lastly, this method increases the value of the list length in order to keep track of the linked list size.
The Remove Method
The next method we will be implementing is the remove method which receives the data as an argument and removes the node containing that data. This method first checks if the head node contains that data and, if it does, removes it by changing the head node to the next node and reducing list length by one. If the head node does not contain the data, we create a variable called currentNode and assign it the value of the list head node. The currentNode variable is used to loop/traverse the linked list with the loop ending when the currentNode.next value is nil. In doing so, we stop the loop when we are at the end of the list, AKA the tail node. For every iteration in the loop, we have two if conditions that do the following:
- Check ahead if the currentNode.next pointer is our tail node and if the tail node contains the data i.e currentNode.next == list.tail && list.tail.data == data.
If that condition passes, we remove the tail node by making the currentNode the new tail node i.e list.tail = currentNode. We also reduce the list length by one and break out of the loop early since the required node has been deleted.
- The second if statement only executes if the first fails and if the currentNode.next contains the data. If that passes, it is removed by assigning currentNode.next node to the node after i.e currentNode.next = currentNode.next.next. After that is done, the length of the linked list is reduced by one and we break out of the loop.
If none of the above conditions pass in the current iteration, the currentNode variable is reassigned with the value of the next node, currentNode = currentNode.next, for the next iteration until the node holding the data is found or the loop ends.
func (list *linkedList) remove(data int) { //If it is the head, remove it if list.head.data == data { list.head = list.head.next list.length-- return } currentNode := list.head for currentNode.next != nil { //If the next node is equal to the data and it is the tail
//remove if currentNode.next == list.tail && list.tail.data == data { list.tail = currentNode list.length-- break } //If the next node is equal to the data remove if currentNode.next.data == data { currentNode.next = currentNode.next.next list.length-- break } // currentNode should be the next currentNode = currentNode.next }}
The Contains Method
Since the contains method is responsible for checking if the data is present in the linked list, all we have to do is traverse/loop down the list and check whether each node contains the data. Before we start our walk down the linked list, we first check if the head or tail nodes contain the data and if they do, we return true.
if list.head.data == data || list.tail.data == data { return true}
If the condition above fails, we start our loop by assigning a variable called currentNode to the value of the head node. The loop keeps running until we are at the end of the list. Through each iteration, we check if the currentNode contains the data and, if it does, we return true to break out of the loop. At the end of each iteration that doesn’t match the if condition, we change the value of currentNode to the next node until we have gone through the linked list. If we have no node containing the data after the loop ends, we return false.
for currentNode.next != nil { if currentNode.data == data { return true } currentNode = currentNode.next}
Now with all cases covered in our discussion above, our contains method will look like this:
func (list *linkedList) contains(data int) bool { if list.head.data == data || list.tail.data == data { return true } currentNode := list.head for currentNode.next != nil { if currentNode.data == data { return true } currentNode = currentNode.next } return false}
The Get Method
The Get method returns the node if the node contains the data. The implementation of this method is similar to that of the contains method, the only difference is it returns the node rather than a boolean.
func (list *linkedList) get(data int) *node { if list.head.data == data { return list.head } if list.tail.data == data { return list.tail } currentNode := list.head for currentNode.next != nil { if currentNode.data == data { return currentNode } currentNode = currentNode.next } return nil}
The Main Method
As usual, every go program must have a main method and we can go ahead and use the linked list we implemented above.
func main() { ll := &linkedList{} ll.append(1) ll.append(2) ll.append(3) ll.append(4) ll.append(5) ll.append(6) fmt.Printf("length is %d \n", ll.length) //length is 6 fmt.Printf("head is %d \n", ll.head.data) //head is 1 fmt.Printf("tail is %d \n", ll.tail.data) //tail is 6
//remove 2 ll.remove(2)
fmt.Printf("contains 2 = %t \n", ll.contains(2))
//contains 2 =false
fmt.Printf("contains 3 = %t \n", ll.contains(3))
//contains 3 = true
n := ll.get(1) if n != nil { fmt.Printf("Found Node %d \n", n.data) //Found Node 1 }
n = ll.get(12) if n == nil { fmt.Printf("No node found containing %d \n", 12)
//No node found containing 12 }}
That brings us to the end of this blog, I hope my explanations were clear, concise, and entertaining enough. If you need the full code, you can find them at the GitHub link below. Thanks.
