The linked list data structure is used to store sequential data using nodes. A node contains a value and the memory address of the next node.

Memory for a new node is allocated dynamically i.e. nodes are stored in the next available memory location. Unlike arrays where contiguous blocks of memory are allocated during declaration.

The first element in a linked list is marked by its head pointer.

Here is an implementation of Linked List in Go

type Node struct{
// Integer value
value int

// Pointer to the next node
next *Node
}

// Pointer to the head node
}


## Accessing a Value#

In arrays, we can access an element using its index. For linked lists we have to iterate over all the previous elements to reach the element specified by the index, so to access the 7th element in a linked list we have to iterate over the first 6 elements.

This operation has linear time complexity ($O(n)$) in the worst-case scenario (accessing the last element).

package main

import "fmt"

type Node struct{
value int
next *Node
}

}

func main(){

// Accessing the node at a specific location
index := 3

// Iterator variable to store the current node
var temp *Node

// Until the value of the index is 0
// increment the temp to the next node
for ;index>0;index--{
temp = temp.next
}

// Display the value at the index
fmt.Println("Value at index", index, "is:", temp.value)
}


## Inserting an Element#

Before we insert an element in a linked list, we have to allocate memory for the new node.

### Inserting an Element (at the beginning)#

The first element in a linked list is decided by the value of the head pointer. So we can reassign the head to point to a new node containing the value to be inserted.

Since we are only modifying the head of the linked list, this is a constant time complexity ($O(1)$) operation.

package main

import "fmt"

type Node struct{
value int
next *Node
}

}

// Create a new node with the input value
newNode := &(Node{value: input, next:nil})

// as the next node

// Point the head to newNode
}

func main(){

fmt.Println("After inserting a new element at the start of the Linked List")
}

// Output
// 2nd node of the linked list: {7 0xc00009e250}
// 3rd node of the linked list: {8 0xc00009e260}
// After inserting a new element at the start of the Linked List
// 2nd node of the linked list: {2 0xc00009e240}
// 3rd node of the linked list: {7 0xc00009e250}


### Inserting an Element (at the end)#

To insert an element at the end of a linked list we first have to find the last element. For that, we have to iterate over the complete list, which will take $O(n)$ time.

package main

import "fmt"

type Node struct{
value int
next *Node
}

}

// Assigning a temp pointer to the head of the linked list

// Until we reach the node with no next value
for ;temp.next!=nil;{

// Increment temp to the next node in the linked list
temp=temp.next
}

temp.next = &Node{value: input, next:nil}
}

func main(){

fmt.Println("After inserting a new element at the end of the Linked List")

}

// Output
// 2nd node: {7 <nil>}
// After inserting a new element at the end of the Linked List
// 2nd node: {7 0xc0000142a0}
// 3rd node: {90 <nil>}
// 4th node: {91 <nil>}


If we modify the LinkedList data structure to add a tail pointer (to store the address of the last node), the time taken to complete this operation will be reduced to $O(1)$.

### Inserting an Element (at a specific location)#

To insert an element at a specific location in a linked list, we can use the same approach as insertAtEnd but we have to stop the loop just before we reach the specified location.

package main

import "fmt"

type Node struct{
value int
next *Node
}

}

func (ll *LinkedList) insertAtIndex(input int, index int){
// Creating a new node with the input value
newNode := &(Node{value:input, next:nil})

if index==0{
// Same as inserting a new node at the beginning

} else {

// While temp is not at the end
// AND i is smaller than the index
// Increment the temp to the next node
for i:=1;i<index && temp.next!=nil;i++{
temp = temp.next
}

// Insert newNode in between temp and temp.next
// temp -> newNode -> temp.next
newNode.next = temp.next
temp.next = newNode
}
}

func main(){

fmt.Println("After inserting a new element at 0th index")

fmt.Println("After inserting a new element at 1st index")
}

// Output
// 2nd node: {7 <nil>}
// After inserting a new element at 0th index
// After inserting a new element at 1st index
// 2nd node: {91 0xc000014270}
// 3rd node: {2 0xc000014280}
// 4th node: {7 <nil>}


The worst-case time complexity of this operation is $O(n)$.

## Deleting an Element#

We can remove an element from the linked list if we just reassign the pointers storing its location.

### Deleting an Element (from the beginning)#

To delete an element from the beginning we can just change the address stored in the head pointer to the next node.

The time taken to complete this operation is independent of the size of the linked list, thus the time complexity will be $O(1)$.

package main

import "fmt"

type Node struct {
value int
next *Node
}

}

}

func main(){

fmt.Println("After deleting element from the start")
}

// Output
// Second node: {3 <nil>}
// After deleting element from the start


### Deleting an Element (from the end)#

To delete an element from the end of a linked list we have to iterate over all the preceding elements. This will result in the worst-case time complexity of $O(n)$.

package main

import "fmt"

type Node struct {
value int
next *Node
}

}

if temp.next == nil {

// If the linked list contains only one element
// Set the value of the head to nil

} else {

// Iterate over the linked list until you reach
// the second last element
for ;temp.next.next!=nil;{
temp = temp.next
}

// Set the next value of the second last element to nil
temp.next = nil
}
}

func main(){

fmt.Println("After deleting element from the end")
}

// Output
// Second node: &{3 <nil>}
// After deleting element from the end
// Second node: <nil>


### Deleting an Element (from a specific location)#

Similar to insertAtIndex we will iterate over the linked list and stop just before the specified location to change the references for its next pointer.

In the worst-case scenario for this operation, we have to remove the last element, resulting in $O(n)$ time complexity.

package main

import "fmt"

type Node struct {
value int
next *Node
}

}

if index == 0{

// If we have to remove the first node (head)
// then change its reference to the next node

} else {

// Exit the loop at the second last element or
// at index-1
for i:=1;i<index && temp.next.next!=nil;i++{
temp = temp.next
}

// Change the reference of the next pointer
// to skip the node located at index
temp.next = temp.next.next
}
}

func main(){

removalIndex := 2
fmt.Println("After deleting element from index:", removalIndex)

removalIndex = 0
fmt.Println("After deleting element from index:", removalIndex)
}

// Output
// Second node: &{3 0xc00009e250}
// Third node: &{5 0xc00009e260}
// Fourth node: &{9 <nil>}
// After deleting element from index: 2
// Second node: &{3 0xc00009e260}
// Third node: &{9 <nil>}
// Fourth node: <nil>
// After deleting element from index: 0
// Second node: &{9 <nil>}


We have to iterate over all the elements in a linked list to display them in the output.

package main

import "fmt"

type Node struct {
value int
next *Node
}

}

// Since we have to reach the last element itself
// we will stop the loop only when the temp is nil
for ;temp!=nil;{
fmt.Printf("%d->", temp.value)
temp = temp.next
}

fmt.Println()
}

func main(){

}

// Output
// 2->3->5->9->


# Variations of a Linked List#

We can add a prev pointer in the linked list node to store the address of the previous node. Although it increases the memory space allocated for each node, the time complexity of iterating in reverse (from any particular node) will be improved.

type Node struct{
prev *Node
value int
next *Node
}

}


In a circular linked list, a node is referenced two or more times. Iterating over a circular linked list results in an infinite loop.

package main

import "fmt"

type Node struct {
value int
next *Node
}

}

// Loop will end upon reaching the last element
// or hitting the limit of elements
for ;limit>0 && temp!=nil;limit--{
fmt.Printf("%d->", temp.value)
temp = temp.next
}

fmt.Println()
}

func main(){

newNode := Node{value:99, next:nil}

newNode.next = &(Node{value: 9, next:nil})

}

// Output
// 2->3->99->6->99->6->99->6->99->6->


Thank you for taking the time to read this blog post! If you found this content valuable and would like to stay updated with my latest posts consider subscribing to my RSS Feed.

# Resources#

How Does a Linked List Work? A Beginner’s Guide to Linked Lists