Doubly Linked List Operation

The doubly linked list data structure is a linked list made up of nodes with
two pointers pointing to the next and previous element.

I will assume that readers are comfortable with the basic singly linked list. If
not, I recommend reading about the singly linked list before proceeding.
Let’s get started shall we?

What is a Doubly Linked List?

As I described in the introduction, the doubly linked list is a linked list made
up of nodes that have two pointers. These pointers point to the next and
previous node.
The doubly linked list is like a

 Old school disc-man.

 Train.

 Minimalist photo gallery slider.

What do all of these examples have in common?

You can only directly access the next or previous node from any given
point/node.
Here is a visual representation of the doubly linked list.
Doubly Linked List Implementation
The only difference between a singly and doubly inked list is in our Node
class or object. Instead of having just a single pointer, we have two
pointers.

If you already know how to implement a singly linked list, implementing a

doubly linked list is as simple as adding an extra pointer to your node.
Okay, this is the end of the tutorial. Kidding!

Before proceeding, I highly recommend, once again, to make sure that you
fully understand how a singly linked list works.
I will assume that you have a decent working knowledge of the singly
linked list.

Doubly Linked List Node

Here is a graphic representation of what each doubly linked list node looks
like.

In contrast to the singly linked list, our doubly linked list node will have two
pointers LITERALLY pointing to the next and previous node.
For all linked list implementations, we must have either a head and/or
a tail. I will mention this just in case. The head and tail node are the first
and last node of a linked list respectively.
So our Node container (in whatever language you program in), will have
the following attributes.
 Data.

 Next node.

 Previous node.

Basic Operations
The basic operations that every linked list should support include the
following.

 insert(T data): Insert data to the front/back of the linked list.

 insertAfter(T data, int index): Insert data after item at a
particular index.
 remove(T data): Search from the start of the list for the passed in data
and remove it from the list, if found.
 remove(int index): Remove data at a specific index.
The size() method is nice to have, but not an absolute must.

Insertion Operation
When inserting a node to the doubly linked list, we now have to worry about
two pointers, instead of one. As long you understand the fundamentals of
how nodes are linked together, this shouldn’t be too difficult.

If we have a linked list that has both a tail and a head, we gain the
advantage of being able to insert to the front and back of the list in O(1)
constant time!
For each insertion operation, we need to consider the three cases. These
three cases also need to be considered when removing data from the
doubly linked list.
1. Front insertion (inserting a head node).

2. Back insertion (inserting a tail node).

3. Middle insertion (inserting a non head/tail node).

 Front Insertion
This is almost as identical as what we did in the singly linked list
implementation.

1. Create new node (B).

2. Check if list is empty (if head equals null, size equals 0, etc.).
1. If list is empty, set B as the new head and end operation.
2. Otherwise, perform the following operations.

1. Set its next node of B to point at current head (A).

2. Set the prev node pointer of A to point at B. This only needs to be done if
elements already exist inside of the list.
3. Assign the newly created node (B) as the new head.
4. Set prev node of B to null.

The ultimately goal is to achieve the link shown in the diagram below. The
steps described above are one way to ensure that this happens. If you
figure out an alternative method to establishing the link, then by all means,
feel free to implement it your way.

Note also that in some languages such as Java, by not assigning a value,
the default value is null.
Front Insertion Pseudo Code
Here is the first pseudo code example. I have tried to write out all the logic
inside of a single method so that we don’t have to jump back and forth from
multiple method calls (at least until we understand the basics).

begin insertAtFront(data):
if head is null:
head = new Node(data);
// Tail and head cannot point at the same node
tail = null;
else:
if tail is null:
tail = new Node(data);
// Update references
// Head --> Tail
// Head <-- Tail
head.setNext(tail)
tail.setPrev(head)
else:
Node<T> prevHead = head;
Node<T> newHead = new Node(data);

// Update references
// newHead.next --> prevHead
// prevHead.prev <-- newHead
newHead.setNext(prevHead)
prevHead.setPrev(newHead)
head = newHead
end if else;
end if else;
increment size
end insertAtFront;
Copy
 Back Insertion
The back insertion mirrors the front insertion.

1. Create new node (C).

2. Check if list is empty.

o If head is empty

1. set C as the new head. Existence of head node indicates that there are
elements in the list (well, at least for this implementation).
o Otherwise, check if tail is null.
 If tail is null
1. Set next node pointer of current head (B) to point to new node (C).
2. Set prev node pointer of new node (C) to point at current head (B).
 Otherwise,

1. Set the prev node of C to point at current tail (B).

2. Set the next node of B to point at new node (C).
o Assign the newly created node (C) as the new tail.
o Set next node of C to null.
Once again, this is one method of performing the back insertion operation.
If you find another way that works for you, great! The whole point of this
example is to get you thinking and to translate our linked list theory into
actual code.
Back Insertion Pseudo Code
Let’s take a look at what all of this logic will look like in pseudo code. Note
that the logic almost mirrors that of the front insertion. The only difference
between the two is how we handle the reference updates when inserting a
head and tail node.

Comparing the two examples will help you wrap your mind around the
difference and solidify your working knowledge of the doubly linked list.

begin insertAtBack(T dataToInsert):

// First element.
if head is null:
nodeToInsert = new Node(dataToInsert)
head = nodeToInsert
// Tail and head cannot point at the same node
tail = null
else:
// Second element to add to list
if tail is null:
tail = new Node(dataToInsert)
// Update references
// Head --> Tail
// Head <-- Tail
head.setNext(this.tail)
tail.setPrev(this.head)
else:
prevTail = tail
newTail = new Node(dataToInsert)

// Update references
// prevTail --> newTail
// prevTail <-- newTail
newTail.setPrev(prevTail)
prevTail.setNext(newTail)
tail = newTail
end if else;
end if else;
increment size
end insertAtBack;
Copy
 Middle Insertion
In the middle insertion, we need to perform the following operations. While
walking through the middle insertion operation, please refer to the diagram
below.

First of all, we need to create the new node (C).

Then, we need to iterate through the linked list and find the place where we
need to insert our node. Be sure to handle possible errors such as user
inserted index being out of range.

Afterwards, we need to update the pointers for the following nodes.

1. Newly added node (C).
o Set next node pointer of C to point at B.
o Set prev node pointer of C to point at A.
2. Previous Node (A).
o Set next node pointer of A to point at C.
3. Next Node (B).
o Set prev node pointer of B to point at C.
Middle Insertion Pseudo Code
Here is the pseudo code for the middle insertion, which is pretty much
inserting data based on index. In this implementation, for the sake of
simplicity, we will begin iterating from the start of the linked list (the head)
until we reach the desired index at which to insert the data.

As a challenge, I recommend you to implement a version that inspects

whether it is faster to iterate from the head or tail and choose the most
optimal path. I have included this version in the source code, but try it on
your own before looking at the solutions.

begin insertAfter(data, index):

if index is less than size - 1:
// Handle error here
end if;
// Get node at a specific index
currentNode = head;
counter = 0;

// Iterate from the front of the list

while currentNode is not null and counter != index:
currentNode = currentNode.getNext()
end while;
// Add node
call insertNode(data, currentNode, currentNode.getNext());
end insertAfter;
Copy
Below is the pseudo code for the insertNode method.
begin insertNode(dataToInsert, currentNode, nextNode):
newNode = new Node(dataToInsert)
// If next node is null, current node is the tail node
if nextNode is null:
tail = newNode
tail.setPrev(currentNode)
currentNode.setNext(newNode)
else:
// update references of existing node
currentNode.setNext(newNode)
nextNode.setPrev(newNode)
// update references of new node
newNode.setPrev(currentNode)
newNode.setNext(nextNode)
end if else;
increment size
 end insertNode;
Copy

Remove Operation
In contrast to the singly linked list, because our nodes have two pointers,
we have slightly more work to do. If you fully understand the insertion
operation in the doubly linked list, the remove operation is very similar.

Therefore, I am going to spend a little less time explaining the same

concepts that we went through in the previous section. Try to figure it out
on your own. If you ever get stuck, for each operation, I have included
some pseudo code to get you back on track.

There are three main cases when removing a node to the doubly linked list.
Cases where the node that we are deleting is the

1. Head.
2. Tail.
3. Neither the head or tail. In another word, the node to remove is somewhere
in the middle of the list.

Case One: Removing Head

How do we know if the node to remove is the head in a doubly linked list?
The answer is simple: head nodes do not have a previous node pointer.
In another word, prev node has a value of null.
If you find it difficult to visualize, try reviewing the previous section. Once
you have conceptualized the doubly linked list, the diagram below will make
a lot of sense. When we remove the head node, two things are happening.

1. Set head to null.
2. Set next node after the head (A) as the new head.
3. Update A‘s prev pointer value to null.
Removing Head Pseudo Code
begin removeFromFront():
if head is not null: {
nextNode = head.getNext()
// Set prev node of next to null if it exists
if nextNode is not null:
nextNode.setPrev(null)
end if;
// Remove current head
head = null;
head = nextNode;
decrement size
end if;
end removeFromFront;
Copy
 Case Two: Removing Tail
Removing a tail node mirrors the head removal operation.

1. Set tail to null.
2. Set previous node (B) as the new tail.
3. Update B‘s next node pointer value to null.
In the case that we are removing the last element, we also need to make a
check if this is the last element. In our implementation, the tail cannot equal
the head. Therefore, if the head node does not equal null but
the tail is null, then we are removing the last element.
In this case, all we need to to is remove the head node but setting its
reference to null.

Removing Tail Pseudo Code

begin removeFromBack():
if head is not null:
if tail is not null:
// Two or more elements exist
newTail = tail.getPrev()
tail = null
newTail.setNext(null)
tail = newTail
else:
// Tail is null but head is not null
// means that this is the last element
head = null
end if else;

decrement size
end if;
end removeFromBack;
Copy
 Case Three: Removing from the middle of the list.
This is probably the most complex case out of the three, because we now
have to work with three nodes:

1. Previous node.

2. Next node.

3. Node to remove.

Removing a node from the linked list is not as complicated as inserting an

item into the middle of the list. If you got that, this should be a cakewalk.

We need to update the following pointers.

 Next node pointer of A. This should be updated to point to C.

 Prev node pointer of C. This should be updated to point to A.
Lastly, we destroy B by setting it to null.

Pseudo Code
Now that we have reviewed all the cases, let’s take a look at the pseudo
code for the entire remove operation.
Remove operation
begin remove(T dataToRemove):
currentNode = head
while current node is not null:
currentData = currentNode.data
if currentData equals dataToRemove:
call removeNode(currentNode)
end if;
currentNode = currentNode.next
end while;
end remove;
Copy

removeNode operation
begin removeNode(nodeToRemove):
prevNode = nodeToRemove.prev
nextNode = nodeToRemove.next
// Head node does not have a previous node
if prevNode is null:
head = null
head = nextNode
head.prev = null
else if nextNode is null:
// Tail does not have a next node
tail = null
tail = prevNode
tail.next = null
else:
// Is somewhere in the middle of the linked list
// Set current node to null
nodeToRemove = null
// connect the previous and next nodes together
prevNode.next = nextNode
nextNode.prev = prevNode
end if else statement;
decrement size
end removeNode;
Copy

Conclusion and Challenge

Now that you understand how the insertion and remove operation works in
the doubly linked list, adding extra features such as  add/removing items by
index, smart traversal, etc. should be easier.
 It is important that you have a solid conceptual understand of these basic
data structures before attempting to move onto some of the more complex
data structures.

I recommend playing around with the doubly linked list by adding the
aforementioned features such as insertion/removal by index. In the source
code, I have added these features for your reference.

Here is a list of possible features that you can add to your doubly linked list
to get more practice.

 Batch inserting a list (adding a list to the linked list, as opposed to single
elements).

 An empty function that empties the entire list.

 A copy constructor (or constructor that converts a different collection into a

list).

 Update your insertAfter(data,
index) and removeAt(index) methods to calculate the fastest way of
traversing to the node at that index. E.g. If we are removing the second last
node in a list of five items, it will start looking from the tail.