The linked list is one of the most important data structures in the Computer science world. Almost every developer at some point in their career would have come across this data structure in one or the other way.
What is Linked list and why is it important to be considered it as the fundamentals in Computer science?
As the term denotes linked lists are nothing but the nodes are linked to each other. In different types, the way it is linked may vary but the concept is just a few or several nodes that are linked to each other.
A node is a basic unit in data structure and represents the information contained in a single data structure. This information can be anything either a value or a chunk of data depends on its implementation. Each node will have its own address of its location in the memory for its reference. For example, it looks like
Programmatic representation of a node is,
type node struct {
value int
next *node
}
Here the node contains the value of type int and stored at some location just for the reference, which will be handled by the compiler during its run time.
Types of Linked lists?
- Singly linked list
- Doubly linked list
- Circular linked list
Few common operations that can be performed on the linked lists are,
- Push front (inserts an element at the front)
- Push back (inserts an element at the back)
- Pop front (removes the head node)
- Pop back (removes the tail node)
Singly linked list
A singly-linked list is the simplest implementation of data structure among other types. In this type, nodes are linked to each other in one-way order. Each node will have the value and the reference to the next node in the order and the list goes on. For example, it looks similar to the image mentioned below,
(address location mentioned in the above example are just sample, It really can be of anything which gets allocated internally)
Singly-linked list maintains head node and tail node. The head node is where the list starts and each node contains the value and the address of the next linked node, it goes on till the node has the nil as its next linked node that becomes the tail node denoted the end of the list.
The best real-world example of the singly linked list is the child’s brain. when they learn some rhymes or poems by heart, even we can’t recollect a song from our memory by its middle. we always remember it with the first line/ sentence, it’s impossible for us to start in the middle. The first line is exactly the head node. That is how our memory works related to the singly-linked list.
package main
import (
"fmt"
)
type node struct {
value int
next *node
}
var head *node = nil
func (list *node) pushBack(value int) *node {
if head == nil {
list.value = value
list.next = nil
head = list
return list
} else {
for list.next != nil {
if list.value == value {
return list
}
list = list.next
}
list.next = new(node)
list.next.value = value
list.next.next = nil
return list
}
}
func (list *node) pushFront(value int) *node {
if head == nil {
list.value = value
list.next = nil
head = list
return list
} else {
tmp := new(node)
tmp.next = list
tmp.value = value
head = tmp
return tmp
}
}
func (list *node) popFront() *node {
if head != nil {
tmp := new(node)
tmp = head.next
head = tmp
return list
}
return list
}
func (list *node) popBack() *node {
if head == nil {
return list
}
tmp := new(node)
tmp = list
for tmp.next.next != nil {
tmp = tmp.next
}
tmp.next = nil
return list
}
func (list *node) printElements() {
for head.next != nil {
fmt.Println("Yes")
fmt.Println(head.value)
head = head.next
}
fmt.Println(head.value)
}
func main() {
listval := new(node)
listval.pushBack(22)
listval.pushFront(1)
listval.popFront()
listval.popBack()
dup := head
for dup != nil {
fmt.Printf("%d \n", dup.value)
dup = dup.next
}
fmt.Println("Value :", head)
}
Doubly linked list
The doubly linked list is similar to the singly linked list, additionally, each node holds the address(pointer) of the previous node address along with the next address. In this structure, the head node will not have any previous node reference and similarly, the tail node won’t have the next pointer address.
The structure looks like this,
Real world application
The working of the browser is the best example of the doubly linked list. If we apply in our diagram comparing its functionalities, value is the website URL that user visits every time and browser previous and next will have the related links as your keep navigate to different links, the browser will preserve in its memory as a doubly-linked list.
Each time the user navigates to a website, current node gets updated to the website and the previous page will be linked to the previous node pointer so that the browser back gets enabled and does the job here.
package main
import (
"fmt"
)
type node struct {
value int
prev *node
next *node
}
var head *node = nil
func (list *node) pushBack(value int) *node {
if head == nil {
list.value = value
list.next = nil
list.prev = nil
head = list
return list
} else {
for list.next != nil {
if list.value == value {
return list
}
list = list.next
}
list.next = new(node)
list.next.value = value
list.next.prev = list
list.next.next = nil
return list
}
}
func (list *node) pushFront(value int) *node {
if head == nil {
list.value = value
list.next = nil
list.prev = nil
head = list
return list
} else {
tmp := new(node)
tmp.next = list
tmp.prev = nil
tmp.value = value
head = tmp
return tmp
}
}
func (list *node) popFront() *node {
if head != nil {
tmp := new(node)
tmp = head.next
tmp.prev = nil
head = tmp
return list
}
return list
}
func (list *node) popBack() *node {
if head == nil {
return list
}
tmp := new(node)
tmp = list
for tmp.next.next != nil {
tmp = tmp.next
}
tmp.next = nil
return list
}
func (list *node) printElements() {
for head.next != nil {
fmt.Println("Yes")
fmt.Println(head.value)
head = head.next
}
fmt.Println(head.value)
}
func main() {
listval := new(node)
listval.pushBack(22)
listval.pushBack(12)
listval.pushFront(1)
listval.popFront()
listval.popBack()
dup := head
for dup != nil {
fmt.Printf(" Current element val : %d \n", dup.value)
fmt.Printf("Prev element val : %d \n", dup.prev)
fmt.Printf("Next element val : %d \n", dup.next)
dup = dup.next
}
fmt.Println("Value :", head)
}
Circular linked list
Circular linked list is exactly similar to the doubly linked list whereas the head and tail node is linked to each other. The previous node of the head node is the tail node and next node of the tail is the head node. Diagrammatic representation of circular linked list is,
The music player is the best example for a circular linked list when you listen to a song it gets mapped to the current node and each song in the playlist contains the previous and next song and thus it makes the circular linked list. There is no end of the playlist, as the user hits next at the last song, the first sone gets played again.
package main
import "fmt"
type node struct {
val int
next *node
prev *node
}
type circularlinkedlist struct {
head *node
tail *node
}
// to avoid mistakes when using pointer vs struct for new node creation
func newNode(val int) *node {
n := &node{}
n.val = val
n.next = nil
n.prev = nil
return n
}
func (ll *circularlinkedlist) addAtBeg(val int) {
n := newNode(val)
n.next = ll.head
ll.head = n
if ll.tail == nil {
ll.tail = n
}
n.prev = ll.tail
ll.tail.next = n
}
func (ll *circularlinkedlist) addAtEnd(val int) {
n := newNode(val)
if ll.head == nil {
ll.head = n
ll.tail = n
return
}
if ll.head == ll.tail {
ll.head.next = n
ll.head.prev = n
n.next = ll.head
n.prev = ll.head
ll.tail = n
return
}
cur := ll.head
for ; cur.next != ll.tail; cur = cur.next {
}
cur.next.next = n
n.prev = cur.next
n.next = ll.head
ll.tail = n
}
func (ll *circularlinkedlist) delAtBeg() int {
if ll.head == nil {
return -1
}
if ll.head == ll.tail {
value := ll.head
ll.head = nil
ll.tail = nil
return value.val
}
cur := ll.head
ll.head = cur.next
if ll.head != nil {
ll.head.prev = ll.tail
ll.tail.next = ll.head
}
return cur.val
}
func (ll *circularlinkedlist) delAtEnd() int {
// no item
if ll.head == nil {
return -1
}
// only one item
if ll.head == ll.tail {
return ll.delAtBeg()
}
// more than one, go to second last
cur := ll.head
for ; cur.next != ll.tail; cur = cur.next {
}
retval := cur.next.val
cur.next = ll.head
ll.tail = cur
ll.head.prev = cur
return retval
}
func (ll *circularlinkedlist) count() int {
var ctr int = 0
for cur := ll.head; cur != ll.tail; cur = cur.next {
ctr++
}
return ctr
}
func (ll *circularlinkedlist) reverse() {
var prev, next *node
if ll.head == ll.tail {
return
}
cur := ll.head.next
ll.tail = ll.head
if ll.head.next != nil {
for cur != ll.head {
next = cur.next
cur.next = prev
cur.prev = next
prev = cur
cur = next
}
}
ll.head = prev
cur.next = ll.tail.next
ll.tail.next.next = ll.tail
ll.tail.next = ll.head
ll.head.prev = ll.tail
}
func (ll *circularlinkedlist) display() {
if ll.head != nil {
fmt.Print(ll.head.val, " ")
if ll.head.next != nil {
for cur := ll.head.next; cur != ll.head; cur = cur.next {
fmt.Print(cur.val, " ")
}
}
}
fmt.Print("\n")
}
func (ll *circularlinkedlist) displayReverse() {
if ll.head == nil {
return
}
var cur *node
for cur = ll.head; cur.next != ll.tail; cur = cur.next {
}
for ; cur != ll.tail; cur = cur.prev {
fmt.Print(cur.val, " ")
}
fmt.Print("\n")
}
func main() {
ll := circularlinkedlist{}
ll.addAtBeg(10)
ll.addAtEnd(20)
ll.reverse()
ll.display()
fmt.Print("Deleting an element at the beginning : ", ll.delAtBeg(), "\n")
fmt.Print("Deleting an element at the end : ", ll.delAtEnd(), "\n")
ll.display()
}