A Linked List is one of the most fundamental Abstract Data Structure that is made of nodes, where each node holds a value, and an address to either the node in front of it, or both the nodes before and after it. Linked Lists behave like lists and arrays, but unlike them, they provide dynamic memory allocation, and can thus be of infinite length, as long as there is enough memory.
In this read, I will teach you to build a Singly Linked List in Golang. As Golang is on the few languages that allow dynamic memory allocation using pointers, Implementing this will clear a lot of your concepts regarding pointers and memory allocation, and also, perhaps teach you some Golang syntax you didn’t know. Let’s get started!
STEP 1:
Importing necessary packages:
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)The Packages and their uses are:
bufioBuffered IO helps us to take input from a user and also provides additional functions.fmtis the standard Golang Package to print statements to a terminal.osprovides a Golang interface to Operating System functionalities.strconvhelps us for string conversion to different types, i.e. from string to integer when the string is a number.stringsis the Golang function for strings that allows us to perform different operations on strings such as split, join, trim and many more.
STEP 2:
Making a Node Struct:
type node struct {
data int
next *node
}Struct node has two datatypes, an integer datatype called data, and a pointer to a struct of the same name or type, called next. This is how Linked Lists work, as each linked list holds a pointer that holds the address of the node after it, and each node can be accessed by the first node. Nodes hold a pointer instead of the struct itself to save memory, for linked list manipulation, and to have a faster time for the compiler to traverse the list.
STEP 3:
Making an input function:
func Input(prompt string) int {
reader := bufio.NewReader(os.Stdin)
fmt.Print(prompt)
i, _ := reader.ReadString('\n')
input := strings.TrimSpace(i)
num, err := strconv.Atoi(input)
if err != nil {
return -1
}
return num
}In this function we take a string as an argument, which is the prompt asked to user to input values, and our output is always an integer, as the Linked List we are creating holds only integer as a datatype.
reader is an object that allows us to read values input by the user on the terminal. We then use the reader.ReaderString('\n') function that reads only a single line, and returns a value, and error, which is ignored by assigning it to _ .
The value is then passed to the strings.TrimSpace function which removes any space from our string.
Then we use the strconv.Atoi() function, passing the input which returns a value, and and error. This function converts a string to an integer, and if the string is not a number, returns a error.
We then return the number or -1 if the user inputs something different than a number.
STEP 4:
Creating a function that returns a node:
func CreateNode(data int) *node {
return &node{
data: data,
next: nil,
}
}
In this function, we pass an integer as an argument and we get a pointer to the node struct in return. &node is used to return pointer, and not the actual struct. We set the next to nil, as the assignment for that will be handled while adding, or deleting a node from the List.
STEP 5:
Creating the Add functions, that add nodes at the end, and the start:
func AddAtEnd(data int, head *node) *node {
if head.data == -1 {
head.data = data
} else {
new := CreateNode(data)
temp := head
for temp.next != nil {
temp = temp.next
}
temp.next = new
}
return head
}
func AddAtStart(data int, head *node) *node {
if head.data == -1 {
head.data = data
} else {
new := CreateNode(data)
new.next = head
head = new
}
return head
}Each function takes an integer, and the pointer to the first node as arguments, and returns a pointer to a node. For both the functions, We check if the head is empty using the condition that the data of head is -1 or not. If it is -1, We assign the data to the head. This assumes that this List only stores positive numbers, and is a bad practice.
For the AddAtEnd,We create a new node, and assign the head to a temp(temporary) node, and then traverse to the end of the List, till the next pointer of the temp is nil, and then assign temp.next to new. Then We return head.
You may be thinking that as we made changes to the temp, how are the same changes reflected in head, and we must understand that all these variables are just pointers, not the actual data, and so when we use temp variable to traverse, it actually changes the address of the pointer, and the actual nodes are not changed. So now head can be used to access the newly added node.
For the AddAtStart, we create a new node, and assign new.next to head, and then we assign new to head, what this does is assign the variable head to the pointer of new, which is actually the ‘head’ of the List right now. It’s a naming change more than a structural change.
We return head at the end of both functions.
STEP 6:
Implementing the functions that delete a node, from the start and end:
func RemoveAtEnd(head *node) *node {
if head.data == -1 {
fmt.Println("No Node in the List.")
} else if head.next == nil {
head.data = -1
} else {
temp := head
for temp.next.next != nil {
temp = temp.next
}
fmt.Printf("Data Removed is: %v \n", temp.next.data)
temp.next = nil
}
return head
}
func RemoveAtStart(head *node) *node {
if head.data == -1 {
fmt.Println("No Node in the List.")
} else if head.next == nil {
head.data = -1
} else {
temp := head
head = head.next
fmt.Printf("Data Removed is %v \n", temp.data)
}
return head
}For removing the node at end, We traverse the til the second-last node of the List using the condition for temp.next.next != nil, This works as the for the second-last node of the List, the next node is the last node, and the next.next is nil. We then print the data, and set temp.next to nil, which means that we break the link between the second-last and the last node.
For removing the node at the start, Apart from checking if there is actually a node, we also check if there is only one node, and if that is true, we simply set the value of that node to -1.
For more than one node, we assign head to a temp and assign head to the pointer of the next node. We basically break the link between the first and the second node.
STEP 7:
Implementing functions that Add nodes at an index, return the length of the list, and display the list:
func AddAtIndex(data int, index int, head *node) *node {
if head.data == -1 {
head.data = data
} else {
len := getLength(head)
if len <= index {
fmt.Println("Index is not Present in the List.")
} else {
i := 1
temp := head
for i != (index - 1) {
temp = temp.next
i++
}
new := CreateNode(data)
new.next = temp.next
temp.next = new
}
}
return head
}
func getLength(head *node) int {
len := 1
if head.data == -1 {
len = 0
} else if head.next == nil {
len = 1
} else {
temp := head
for temp.next != nil {
len++
temp = temp.next
}
}
return len
}
func DisplayList(head *node) {
if head.data == -1 {
fmt.Println("No Node in the List.")
return
}
temp := head
for temp != nil {
fmt.Printf("%v ", temp.data)
temp = temp.next
}
}getLength uses a temp variable to traverse the List, and increments by 1 everytime it changes it’s address. This is why it is assigned to 1 at the start, and not 0.
AddAtIndex performs the usual checks, and if all are passed, it traverses till the (index-1)th node, then sets the new.next to the temp.next, and at this point the index node has 2 pointer as their next node. Then it sets temp.next to new, which breaks the link between the temp and the index, and joins temp and new, essentially adding new between the two nodes.
The Display function is self-explanatory and is a nice exercise to clear your Linked-List concepts.
STEP 8:
Making the main function and implementing the menu-driven logic:
func main() {
head := &node{
data: -1,
next: nil,
}
for {
fmt.Println()
fmt.Println("1. Add a New Node at the End.")
fmt.Println("2. Add a New Node at the Start.")
fmt.Println("3. Remove a Node from the End.")
fmt.Println("4. Remove a Node from the Start.")
fmt.Println("5. Add a New Node at a particular Index.")
fmt.Println("6. Display the List.")
fmt.Println("7. Exit.")
fmt.Println()
choice := Input("\nEnter your Choice: \n")
switch choice {
case -1:
fmt.Println("Enter an integer.")
case 1:
data := Input("Enter your data: ")
if data == -1 {
fmt.Println("Enter an integer.")
break
}
head = AddAtEnd(data, head)
case 2:
data := Input("Enter your data: ")
if data == -1 {
fmt.Println("Enter an integer.")
break
}
head = AddAtStart(data, head)
case 3:
head = RemoveAtEnd(head)
case 4:
head = RemoveAtStart(head)
case 5:
index := Input("Enter your Index: ")
if index == -1 {
fmt.Println("Enter an integer.")
break
}
data := Input("Enter your data: ")
if data == -1 {
fmt.Println("Enter an integer.")
break
}
head = AddAtIndex(data, index, head)
case 6:
fmt.Println("The List is: ")
DisplayList(head)
fmt.Println()
case 7:
fmt.Println("Exiting...")
return
default:
fmt.Println("Enter an integer between 1 and 7.")
}
}
}Most of the code in this block is self-explanatory, and is a exercise for you to understand the basics of this Language. One noteworthy piece of code will be the declaration of the head struct, which is done by assigning a pointer to the variable, with the data set to -1, which, as I explained earlier, is a bad practice.
OUTPUT:
CONCLUSION:
I hope this read taught you about the basics of Linked Lists, pointers, and the syntax of Golang, in general. Follow me for more of these articles, and ask any questions you have in the comments.
GitHub Link for this code:
https://github.com/TheJashShah/Data-Structures/blob/main/Linked-Lists/sll.go
