Original article is available on my website: https://promisefemi.vercel.app/blog/data-structures-singly-linked-list
The illusive data structures, in this series i would be explaining individual data structures and their respective implementation in the Go programming language.
Linked list are a very simple data structure and they are often compared to arrays, but there are distinct differences not just in how they are implemented but in how they work under the hood.
The values of arrays are stored next to each other in memory, making it very easy to find a specific value by reaching out directly to the index.
This is a visual representation of an array - 200,201, 202 … represents space in memory
Image source: https://www.geeksforgeeks.org
A linked list on the other hand are arranged in nodes where each node points to the next node in memory, the values in memory may not be close to each other..
Image source: https://www.geeksforgeeks.org
Each node from the head (the first node) points to the next node and that node points to the next and so on.
This is the point where most people begin to ask why they should use a linked list instead of just using an array, saving themselves the stress. But linked list are particularly useful for storing ordered data and other forms of linked list such as the doubly linked list are useful for things like undo/redo, music playlists to name a few
Alright enough talk, show me the code
Implementing a Singly Linked list
Implementing a singly linked list is very simple ( trust me 😉)
First we need to create the structure of the linked list
package main
type linkedList struct {
// value can be whatever datatype fits your particular scenario
value string
next *linkedList
}
in the example above we created a new struct type with a value and next field, the value field is the value of the current node and the next field points to the next node on the linked list. Let us initialize a new linkedList
func main(){
list := new(linkedList)
}
That’s it ( well not particularly ), that is all you need for the structure of a linked list. Now let’s talk about inserting a new node into a linked list .
Inserting a new node
To insert a new node into the linked list, we have to move through the linked list until we find the last node, then we just add the new node to the last position. if that confuses you let me explain in code.
func (node *linkedList) insert(text string){
// first we create a temporary value for our new node
tempNode := &linkedList{value: text, next: nil}
// remember that the next pointer in the last node is always nil until it points to another node
if node == nil{
// if this is a head node and it is nill, make the current tempNode the head
node = tempNode
}else{
currentNode := node
// go through every node until we get to the last node,
for currentNode.next != nil{
// check if it is the last node, if not move to the next
currentNode = currentNode.next
}
// when we get to the last node, place the new node we are creating
currentNode.next = tempNode
}
}
Now when we go back to our main() we would call the insert method to add new nodes to our linked list
func main(){
list := new(linkedList)
list.insert("Apple")
list.insert("Oranges")
list.insert("Strawberries")
}
At this point you are probably like “ Yeah we’ve been doing all this things but how do we even know it’s adding anything “, Don’t worry i got you.
Displaying values
Let’s add a method that loops through each of the nodes to print out their values.
func (node *linkedList) print(){
// start from the first node
currentNode := node
// loop through each node, making sure it is not nil
for currentNode != nil{
//print the value out
fmt.Printf("%s -> ", currentNode.value)
//move to the next node
currentNode = currentNode.next
}
}
All together now
package main
type linkedList struct {
// value can be whatever datatype fits your particular scenario
value string
next *linkedList
}
func (node *linkedList) insert(text string){
// first we create a temporary value for our new node
tempNode := &linkedList{value: text, next: nil}
// remember that the next pointer in the last node is always nil until it points to another node
if node == nil{
// if this is a head node and it is nill, make the current tempNode the head
node = tempNode
}else{
currentNode := node
// go through every node until we get to the last node,
for currentNode.next != nil{
// check if it is the last node, if not move to the next
currentNode = currentNode.next
}
// when we get to the last node, place the new node we are creating
currentNode.next = tempNode
}
}
func (node *linkedList) print(){
// start from the first node
currentNode := node
// loop through each node, making sure it is not nil
for currentNode != nil{
//print the value out
fmt.Printf("%s -> ", currentNode.value)
//move to the next node
currentNode = currentNode.next
}
}
func main(){
list := new(linkedList)
list.insert("Apple")
list.insert("Oranges")
list.insert("Strawberries")
list.print()
}
With all of that intact, let’s make it more interesting by allowing our users to select between adding new nodes to the linked list and printing the entire linked list
package main
import (
"fmt"
"log"
"os"
)
type linkedList struct {
// value can be whatever datatype fits your particular scenario
value string
next *linkedList
}
func (node *linkedList) insert(text string) {
// first we create a temporary value for our new node
tempNode := &linkedList{value: text, next: nil}
// remember that the next pointer in the last node is always nil until it points to another node
if node == nil {
// if this is a head node and it is nill, make the current tempNode the head
node = tempNode
} else {
currentNode := node
// go through every node until we get to the last node,
for currentNode.next != nil {
// check if it is the last node, if not move to the next
currentNode = currentNode.next
}
// when we get to the last node, place the new node we are creating
currentNode.next = tempNode
}
}
func (node *linkedList) print() {
// start from the first node
currentNode := node
// loop through each node, making sure it is not nil
for currentNode != nil {
//print the value out
fmt.Printf("%s -> ", currentNode.value)
//move to the next node
currentNode = currentNode.next
}
fmt.Println("")
}
func main() {
list := new(linkedList)
for {
var selected string
fmt.Println("(1) enter a new item")
fmt.Println("(2) print list")
_, err := fmt.Scanln(&selected)
if err != nil {
log.Fatalln(err)
}
switch selected {
case "1":
var item string
_, err := fmt.Scanln(&item)
if err != nil {
log.Fatalln(err)
}
list.insert(item)
case "2":
list.print()
default:
os.Exit(0)
}
}
}
Hurray!!, That’s it (no for real that’s it) we have a linked list that would be proud enough to carry its shoulders up, but i will be leaving you with the task of removing a node from the linked list by simply passing a value to a method ( call it homework ).
The code in this article is available here
Thank’s for reading, hope to see you again next time, and please share.
Top comments (0)