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.