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.