Series 3: Linked List

Have you ever played the game Treasure Hunt ?

Guess what?It's Gopher's birthday and as part of his birthday surprise his friends have organised a game of Treasure Hunt.As part of this game Gopher has to go around the city to collect clues and small gifts which will eventually lead him to the main gift.Each clue reveals the location of the next clue and so on until the final location where Gopher will receive his main gift.(Pssst!......All his friends are hiding at the final location for a surprise birthday party!)

Fast forward a few hours and Gopher is having one of the best days of his life at the mall with all this friends and family celebrating his birthday.

Let us take this experience from Gopher's life and apply it to understand another Data Structure ,i.e, Linked List.

What is the definition of a Linked List ?

A Linked List is a linear collection of elements whose order is not given by their physical placement in memory.Every element has a built in pointer which points to the location of the next element in the collection.

What does an element contain?

Every element in a Linked List comprises of two parts, i.e, the data/gift in itself and a pointer to the next location at which the next data/gift resides.This single element is called a Node.

What does a Node look like in a Singly Linked List?

What does a Singly Linked List look like?

Lets go back a few days before Gopher's birthday to the day his friends were planning this event.One of the problems they faced is that how do they split up the clue in such a way that putting all of them together is the only way Gopher can reach the final destination.

After a lot of brainstorming, the solution they came up with is that each clue or each step will have a reference to the previous clues so that Gopher can  look at all the clues collected so far at any given point of time.

Let us reuse their solution to understand another Data Structure or variation of the current Data Structure ,i.e, a Doubly Linked List.

Every element in a Doubly Linked List comprises of three parts, i.e, the data/gift in itself , a pointer to the next location at which the next data/gift resides and a pointer to the location of the previous element.This single element is also called a Node.

What does a Doubly Linked List look like?

Building on this variation of Linked List, if the Tail node(last node) in a Doubly Linked List has it's NEXT pointer pointing to the Head node(first node) and the PREV pointer of the Head node(first node) points to the Tail node(last node) then this type of a Linked List is called a Circular Linked List.

What does a Circular Linked List look like ?

How would this look like in code ?

Step 1: Package Management & type definition

Let us create two variables -

1. One will be used to store the data in itself ,i.e, the Node
2. The other will be used to store a collections of the Nodes created above.Let us called this variable "Linked List"

//Main package to demonstrate Linked List Data Structure
package main

import "fmt"

//In order to group the nodes we use type - struct
type linkedList struct {
	head *node
	tail *node
}

//Each data element is stored in a node which is of type - struct
type node struct {
	next *node
	data interface{}
}

Step 2: Initialisation

In the previous step, we specified how we will store the information, now we need to figure out a way to create the same,i.e, a function to initialise the Linked List.

//New() : Function to initialise an instance of LinkedList struct
func New() *linkedList {
	emptyNode := &node {
		next: nil,
		data: nil,
	}
	return &linkedList {
		head: emptyNode,
		tail: emptyNode,
	}
}

Step 3: Main function definition

The actual initialisation of all the variables happens as always in the Main function as it is the starting point for any GO program .Let us go ahead and create one for this program too.

//Main Function
func main() {
	linkedlistObj := New()
	linkedlistObj.AppendNode(1).AppendNode(2).AppendNode(3).PrintAllNodes()
	linkedlistObj.PrintAllNodes()
	linkedlistObj.DeleteNodeWithValue(2)
	linkedlistObj.PrintAllNodes()
	linkedlistObj.DeleteNodeWithValue(1)
	linkedlistObj.PrintAllNodes()
}

Step 4: Add a node function definition

To aid Gopher's friends in creating the different clues of the Treasure hunt we need to make a function which will add a clue/node into the game/Linked List.We do that using the AppendNode() function.

//AppendNode() : Function to add a new Node to existing Linked List
func (ll *linkedList) AppendNode(d interface{}) *linkedList {
	nextNode := &node {
		next: nil,
		data: d,
	}
	if ll.head.data == nil {
		ll.head = nextNode
	} else {
		ll.tail.next = nextNode
	}
	ll.tail = nextNode
	return ll
}

Step 5: Delete a node function definition

Gopher's friends should also be able to remove an existing clue/Node from the game/Linked List.To do this we need to create a function called DeleteNodeWithValue, which will do the following:

1. Take the value to be deleted as an input to the function
2. Iterate through the Linked List to find the Node
3. Delete the Node which has a value that matches the value that was given as input to the function

//DeleteNodeWithValue() : Function to delete a node from an existing Linked List
func (ll *linkedList) DeleteNodeWithValue(v interface{}) *linkedList {
	var element =ll.head
	if element.data == v {
		ll.head = ll.head.next
		return ll
	}
	for {
		if v == element.next.data {
			if element.next.next != nil {
				element.next = element.next.next
				break
			}
			element.next = nil
			break
		}
		element = element.next
	}
	return ll
}

Step 6: Add a function to print all Nodes

Gopher's friends would also like to see all the clues/Nodes that were added into the game/Linked List so far.For this reason, we need to create a new function called PrintAllNodes which will iterate through the game/Linked List and print their values

//PrintAllNodes(): Function to print all nodes.
func (ll *linkedList) PrintAllNodes() {
	var element = ll.head
	for {
		fmt.Println("Elements are: ",element.data)
		if element.next == nil {
			return 
		}
		element = element.next
	}
}

Please find the complete working code for Linked List at the following location:

Let's talk performance now!

The only two complexities in terms of performance that we care about is the amount of time Gopher's friends will take to find a new clue/Node  in the Linked List(Time Complexity) and how big/long the Linked List actually is  (Space Complexity).

Time Complexity

1. Adding a Node: Adding a Node will always take place at the Tail of a Singly/Doubly Linked List. Therefore this is a Constant Time Complexity operation and is denoted as O(1).
2. Deleting a Node: Deleting a Node will be done by matching the value of a Node content with the value that has been passed as input to the function.This is a Constant Time Complexity operation and is denoted as O(1).
3. Searching for a Node: Searching for a particular Node in a Linked List requires the system to iterate through the entire Linked List to find the value.Therefore, this is a Linear Time Complexity operation and is denoted as O(N).

Space Complexity

If there are N Nodes that needs to be stored then we need a Linked List of size N. Therefore the Space Complexity for a Linked List is termed as Linear Space Complexity and is denoted as O(N).

In the next post we will see some real world examples where the concept of Linked List is used.