What is a Doubly-LinkedList?

A Doubly-LinkedList is a linear collection of data structured in the form of a sequence of nodes, where each node consists of the following parts: the links to the previous and next nodes, and some data or value. The idea of a Doubly-LinkedList takes origin from a LinkedList and has been taken to one step further.

In comparison to LinkedLists, a Doubly-LinkedList has a small change that presents some advantages over original LinkedList. Each node of a Doubly-LinkedList contains an extra-link to the previous node. Having an extra link to the previous node enables to execute some operations more efficiently. For example, it is possible to traverse the list in either direction from head-to-tail, and vice-versa. Additionally, adding a new node gets easier, especially when dealing with adding a new node into the middle of the list. All that is needed to do is just to change the links of the nodes.

However, storing an extra link poses some drawbacks as well. The primary drawback is related to memory-usage, since it is needed to keep an extra link to the previous node. Besides, while adding it is essential to change and correctly initialize the link to previous node, since each node has to keep the right link to the previous node.

The basic component of a Doubly-LinkedList, as it is of LinkedList, is its nodes. Here is a simple implementation of a node. A node contains some data, it may be some number, text or another object, and stores links to the previous and next nodes.

public class Node {
public int value;
public Node next;
public Node previous;

public Node(int value){
this.value = value;
this.next = this.previous = null;
}

}

The Doubly-LinkedList basically consists of the following structure. It always stores the links to the first — head and last nodes — tail and methods it provides. Whenever a Doubly-LinkedList is initialized, it is empty and head and tail nodes are null, i.e they have no value. The time complexities of the operations provided by Doubly-LinkedList are as follows:

Insertion — O (1)

Deletion — O (1)

Search — O (N)

Let’s discuss the operations one by one.

Insertion or Adding a new node — add(node) is implemented pretty straightforwardly. Inserting a new node is usually done only in one direction and only into the tail of the collection, however it is also possible to implement insertion in either direction with some more operations. When a node is inserted into the middle, it is important to correctly re-initialize the links, so that they keep the correct links to the nodes. For example, insert(b, z)z becomes the next of node — b and previous of node — c. Hence, the previous and next nodes of node — z are nodes — b and c respectively. Whenever a new node is inserted, the newly added node becomes the tail and the tail keeps the link to the previous node. The next node after tail is always null, i.e it has no value or it does not exist. Importantly, when the first node is added, the node is the head and tail of the collection simultaneously. Time complexity of the algorithm is constant time — O(1).

Deletion or removing a node — remove(node) is implemented in a simple way as well. In order to delete, it is necessary to keep or get the link of the node that is previous to deleting node. Hence, we just change the link of the previous node so that it refers to the next node. As illustrated, may a collection of letters is given [a — b — c — b — e]. Removing the letter — a results in the following collection [b — c — b — e ]. Importantly, if the head of the collection is removed, the next item becomes the head of the collection; or if the tail is removed, the previous node becomes the tail. Time complexity of the algorithm is constant time — O(1).

However, just like the LinkedList, the Doubly-LinkedList is not a solution for all the problems. Doubly-LinkedList does not provide fast random-access to nodes, or elements, of the collection as well. Hence, it is impossible to get an access to the given node, or element, for constant time. To get an access to the desired node or element, it is necessary to iterate over the collection and find it. Ultimately, the operation of searching takes — O(N) time to execute, where N — the number of nodes in the collection.

The next post awaiting us will be about ArrayList, or simply Dynamic Array — The most popular and widely-used data structure.

If you are curious to dive deeper and play around with the LinkedList, I recommend to implement the discussed operations by yourself and test.

The following are the links for:

Raw code to implement Doubly-LinkedList by yourself
Sample implementation of Doubly-LinkedList
Test cases

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store