The Go programming language is fast and that’s why it’s a great choice for building web and cloud applications at Google and many other reputable companies. This article will teach you how to implement the LinkedList data structure in Go.
What is a LinkedList?
A LinkedList is a data structure consisting of nodes in memory, and every field stores a pointer to the following field, forming a connection to nodes of the list. The data fields aren’t in the exact memory location. But using pointers, they get to connect and reference each other just like arrays.
LinkedList is more efficient and preferable to arrays because they can store heterogeneous data, are dynamically sized, insertion is faster, and they are memory-efficient than arrays.
You can use a LinkedList in any language, including Go. You can use the list package that’s part of the container package in the standard library, or you can implement a custom LinkedList using Go data structures. This tutorial will teach you about the list package and how to implement custom LinkedList in Go.
The LinkedList List Package
The container package contains the implementation of several data structures and their algorithms in Go.
The list package, on the other hand, includes an implementation of the LinkedList data structure you can use in your Go programs. It is part of the standard library, and here’s how you can import the package:
import ( "container/list" )
You can create a new LinkedList using the New method of the list package. The New method returns a pointer to the initialized list.
LinkedList := list.New()
You can use your LinkedList instance’s PushBack and PushFront methods to insert elements into your LinkedList.
LinkedList.PushBack(1) LinkedList.PushFront(2)
The PushBack method inserts at the end of the list, and the PushFront method inserts elements at the beginning of the list.
If you want to delete an element, you’ll need a reference to that element, and then you can use the Remove method.
choice := LinkedList.Back() LinkedList.Remove(choice)
The element choice is the last entry in the LinkedList. The remove method takes only the reference, as in the example above.
You can use a loop to print the elements of the LinkedList starting from the head of the LinkedList.
for node := LinkedList.Front(); node != nil; element = node.Next() {
fmt.Println(element.Value)
}
The for-loop starts from the head node to the tail and prints the values in the LinkedList if there are any.
You can learn more about the list package from the Go documentation page. Let’s see how you can implement a custom LinkedList in Go using Go’s native data structures.
Implementing a Custom LinkedList in Go
Nodes comprise LinkedLists. The nodes are linked to one another starting from the head node, and every node holds a value and a pointer to the next node. You’ll use a struct for prototyping the node.
type Node struct {
data any
next *Node
}
The Node struct has the value field that can hold any data structure and the next field that will reference the next node.
You’ll also need another struct to prototype the LinkedList. The struct would have a reference to the head node and the length of the LinkedList.
type LinkedList struct {
headNode *Node
length int
}
You’ll LinkedList struct is your custom LinkedList; you’ll implement functions on the LinkedList struct.
Adding Elements to the LinkedList
The LinkedList should be able to accept any type of data structure, so the function would take in an any type.
func (list *LinkedList) addElement(element any) {
newNode := Node{
data: element,
}
}
The addElement function implements the LinkedList struct and takes in the element as an argument. The newNode variable is an initialization of a node to hold the element that will be inserted. Next, we place the node in the tail of the LinkedList.
If the length of the LinkedList is zero, the new node is set as the head of the LinkedList.
if list.length == 0 {
list.headNode = &newNode
list.length++
return
}
If there are elements in the LinkedList, the solution is to search for the node with a nil pointer and make the new node the next node using a for-loop like starting from the head node.
else {
currentNode := list.headNode
for position := 0; position < list.length; position++ {
if currentNode.next == nil {
currentNode.next = &newNode
list.length++ // increase the length
return
}
currentNode = currentNode.next
}
}
You also have to increment the length of the LinkedList. The function would always add elements to the head node since it checks for the length before assignment.
Replacing Elements in the LinkedList
If you want to replace an element in your LinkedList, you’ll have to search for the element. You can use a for-loop to traverse the LinkedList and search for the element you want to replace.
func (list *LinkedList) replaceElement(element, replacer any){
currentPosition := list.headNode
for index := 0; index < list.length; index++ {
if currentPosition.data == element {
currentPosition.data = replacer
}
currentPosition = currentPosition.next
}
}
The replaceElement function takes in an element element and its replacement replacer and sets the replacement as the data in the node when the element is found. The function
Deleting Elements from the LinkedList
If you want to delete an element, you’ll have to search for it using a for-loop and then delete it. A more efficient way would be to check if the head node is nil or it stores the value you want to delete.
func (list *LinkedList) DeleteElement(element any) {
currentPosition := list.headNode
if list.length == 0 {
return
}
for index := 0; index < list.length; index++ {
if currentPosition.data == element {
currentPosition = nil // set the position to nil
for currentPosition.next != nil {
currentPosition = currentPosition.next
}
}
}
list.length -= 1
}
The DeleteElement function takes in the element you want to delete and checks if the LinkedList is empty. If the LinkedList isn’t empty, the for-loop traverses through the LinkedList in search of the element, and then when it’s found, it’s set to nil. Setting the element to nil isn’t enough because you’ll have a nil node in the middle of the LinkedList, and there should only be one nil (the tail node).
The second for-loop (nested) traverses through the LinkedList and replaces every node next to the deleted node before the deleted node so that the deleted node becomes the new tail node.
Printing Your LinkedList
Since your LinkedList is a struct of linked nodes, Just like the Linkedlist you created with the list package, you’ll need a for-loop to traverse through the linkedlist and print the elements.
func (list *LinkedList) PrintList() {
if list.length == 0 {
fmt.Print(nil)
}
currentPosition := list.headNode
for index := 0; index < list.length; index++ {
fmt.Println(currentPosition.data)
currentPosition = currentPosition.next
}
}
In the PrintList function, the if statement checks if there are elements in the LinkedList; if there is nil, the functions print nil. Suppose there are elements in the LinkedList, the for-loop prints the data in the Nodes of the LinkedList by traversing through the LinkedList.
Interacting with the LinkedList
Now that you’ve set up your custom LinkedList and respective functions on them, the next step is initializing the LinkedList and testing your functions.
exampleList := LinkedList{
headNode: nil,
length: 0,
}
The exampleList variable is an initialization of the LinkedList struct. The length is zero and the head node is nil since the LinkedList is empty.
func main() {
exampleList.addElement(4)
exampleList.addElement("Golang")
exampleList.addElement(false)
sampleArray := [4]int{5, 6, 3, 7}
exampleList.addElement(sampleArray)
exampleList.replaceElement(4, "200")
exampleList.DeleteElement(false)
exampleList.PrintList()
}
In the code example, the LinkedList is populated with an integer, a boolean, an array, and a string. Then, the boolean is deleted, and the integer is replaced with a string. On printing the LinkedList using the PrintList function, here’s the output.
Conclusion
LinkedLists are one of the most used data structures with many applications like queues and memory management. If you need a data structure to store unrelated data of different types, you could use a LinkedList.
In this article, you learned how to use the list package of the standard library to create and use LinkedLists. You also learned how to implement the LinkedList data structure with a custom linked list and operations for the LinkedList.
