How to Deal With Doubly Linked List in Simple Ways

Implementing doubly linked list in go

Published in

The Startup

7 min readAug 14, 2020

Introduction:

Before going into doubly linked list implementation, you must have basic knowledge about Linked List. If you haven’t read about Linked List or Singly Linked List yet, click here to read.

And if you are already aware about Singly Linked List, then you are at the right place to proceed further.

“used gray steel chain” by Markus Spiske on Unsplash

Doubly linked list is a collection of nodes. Node consists of three parts:

Pointer to Previous Node
Data
Pointer to Next Node

Pictorial representation of Doubly Linked List

A Node and Doubly Linked list can be represented using below structure in Go:

Node and Doubly linked list structure

You will see the terms of Head and Tail throughout this story. So basically Head is the pointer that points to the first node of the list. What about Tail?
You guessed it right! Tail is the pointer that points to the last node of the list.

Now, I hope you have gone through the basics of the doubly linked list. So, without wasting time let’s jump into some of the operations that can be performed on Doubly linked list.

Note: In this tutorial, while performing operations using index/position, zero is considered as the first position

1. Inserting a node

1.1 Insert a node at the start of the list

Inserting a node at the beginning of the list is as easy as performing the below steps:

Create a node
Assign value to the node
Set the new node’s pointer to next node with existing Head pointer and pointer to prev node as NULL
Change the value of Head so that it will point to new node

Following code will simply demonstrate:

Inserting a node at the start of the list

1.2 Insert a node at the end of the list

In singly linked list, we have to traverse the complete list to add a node at the end of list. But, as doubly linked list introduces a new Tail pointer, no need to traverse the entire doubly linked list to add a node.

Following are the steps to add a node at the end of list:

Create a node
Assign value to the node
Set the new node’s pointer to prev node with existing Tail pointer and pointer to next node as NULL
Change the value of Tail so that it will point to new node

Below code can be used to insert a node at the end of list:

Inserting a node at the end of the list

1.3 Insert a node at a particular position

We’ve seen the process of inserting a node at the beginning and end of list. What about inserting a node elsewhere? like inserting node at a particular position. For this we need to follow below steps:

Create a node
Assign value to the node
Now get the existing node from provided position and set it’s pointer to prev node with new node
Set new node’s pointer to next node with existing node(that we got in step 3)
Now get the node from provided position-1 location and set it’s pointer to next node with new node
Set pointer to prev node of new node with the position-1 location node(that we got in step 5)

Below code will explain the things more clearly:

Inserting a node at a particular position

2. Printing linked list nodes

As we have already seen, doubly linked list can be traversed in two ways i.e. forward traversal and backward traversal.

Forward traversing can be done using Head pointer that points to the first node then visiting next nodes using pointer to the next node & so on until we reach the pointer to next node as NULL.

Let’s understand it using below code:

Printing linked list nodes in forward direction

Whereas, backward traversing can be done using Tail pointer that points to the previous node then visiting previous nodes using pointer to prev node & so on until we reach pointer to prev node as NULL.

You can see the below code to understand:

Printing linked list nodes in backward direction

3. Searching a node

Search operation can also be performed using two ways: searching a node using Head pointer (forward traversal) or searching a node using Tail pointer(backward traversal). But in below code we are using the forward traversal.

Searching a node using value

As we’ve seen getting a node’s position by it’s value, What about getting a node from a particular position?

Following code will help you to get that.

Get a node from a particular position

4. Deleting a node

4.1 Delete first node from list

Deleting a node from the beginning of list is much easier, just follow couple of steps and you are done.

Change the existing Head pointer with Head’s pointer to next node
Set the Head’s pointer to previous node as NULL

That’s it 😃

Let’s see the code:

Deleting first node from list

4.2 Delete last node from list

Deleting a last node of list is similar and as easy as deleting the first node. Difference is that, here we are changing the Tail value instead of Head.

Change the existing Tail pointer with Tail’s pointer to previous node
Set the Tail’s pointer to next node as NULL

Below code implements the above given steps:

Deleting last node from list

4.3 Delete a node from particular position

Deleting a node at a given position needs some extra steps over deleting at first and last node. Because, as you can see in below image, here we are changing the links of previous and next node. Let’s see the required steps:

If position points to first node we are using the Delete first node flow and if it points to last node we are using Delete last node flow.
Otherwise, get the existing node from given position
Change the next node’s pointer to prev node with the node’s pointer to prev node
Change the previous node’s pointer to next node with the node’s pointer to next node

Confused? below picture will clear the things.

Let’s see the code to delete a node using it’s position:

Deleting a node from particular position

You can find the complete code here.

Let’s see the advantages and disadvantages of doubly linked list over singly linked list

Advantages:
1. We can traverse a Doubly linked list in both ways i.e. in forward and backward direction
2. Insert and delete operations are more easy if previous pointer is known

Disadvantages:
1. Requires extra memory space for pointer to previous node as compared to singly linked list
2. Extra operation of maintaining pointer to previous node needs to be performed while insertion and deletion

Some of the applications of Doubly Linked List:

Music player with previous and next buttons

Music player’s previous and next buttons

2. Web browser’s cache with backward and forward buttons

Web browser’s backward and forward buttons

3. Undo and redo functionality

Undo and redo buttons

4. Text Editor

Text editor’s insertion point

As you can see in above image, the insertion point is after character “l”. so when we need to add character after it like “-” it means we are adding a node into doubly linked list. It’s pointer to previous node points to character “l” and pointer to next node points to character “c”. And the final linked list becomes “Wel-come”. As you move the insertion point forward or backward, it means you are traversing the list.

Conclusion:

In this story, we’ve seen some basics of doubly linked list like:

Doubly linked lists can be traversed in forward and backward direction
An extra pointer to previous node is used in doubly linked list over singly linked list which helps in backward traversal
Doubly linked list operations like insertion, deletion, searching & traversal
We’ve seen the advantages & disadvantages doubly linked list over singly linked list
Some applications of real world examples like Media player’s Next & Previous operations, Web browser’s cache with backward and forward operations where doubly linked lists are used.

That’s it from my side. Any suggestions & corrections are highly welcomed.

Stay happy 😊 & keep reading.