# What is a Doubly-LinkedList?

A** Doubly-LinkedList** is a linear collection of data structured in the form of a sequence of

**, where each**

*nodes***consists of the following parts: the links to the previous and next nodes, and some data or value. The idea of a**

*node***takes origin from a**

*Doubly-LinkedList***and has been taken to one step further.**

*LinkedList*In comparison to ** LinkedLists**, a

**has a small change that presents some advantages over original**

*Doubly-LinkedList***. Each node of a**

*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**

*Doubly-LinkedList***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

**, is its nodes. Here is a simple implementation of a node. A**

*LinkedList***contains some**

*node***, it may be some number, text or another object, and stores links to the**

*data***and**

*previous*

*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 —

**and last nodes —**

*head***and methods it provides. Whenever a**

*tail***is initialized, it is empty and**

*Doubly-LinkedList***and**

*head***nodes are null, i.e they have no value. The time complexities of the operations provided by**

*tail***are as follows:**

*Doubly-LinkedList*

Insertion — O (1)

Deletion — O (1)

Search — O (N)

Let’s discuss the operations one by one.

** Insertion** or

**a new node —**

*Adding***is implemented pretty straightforwardly. Inserting a new node is usually done only in one direction and only into the**

*add(node)***of the collection, however it is also possible to implement insertion in either direction with some more operations. When a**

*tail***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,**

*node***—**

*insert(b, z)***becomes the next of node —**

*z***and previous of node —**

*b***. Hence, the previous and next nodes of node —**

*c***are nodes —**

*z***and**

*b***respectively. Whenever a new node is inserted, the newly added node becomes the**

*c***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**

*tail***and**

*head***of the collection simultaneously. Time complexity of the algorithm is constant time —**

*tail***.**

*O(1)*** Deletion** or

**a node —**

*removing***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**

*remove(node)***. Removing the letter —**

*[a — b — c — b — e]***results in the following collection**

*a***. Importantly, if the**

*[b — c — b — e ]***of the collection is removed, the next item becomes the**

*head***of the collection; or if the**

*head***is removed, the previous node becomes the**

*tail***. Time complexity of the algorithm is constant time —**

*tail***.**

*O(1)*However, just like the ** LinkedList**, the

**is not a solution for all the problems.**

*Doubly-LinkedList***does not provide**

*Doubly-LinkedList***to**

*fast random-access***, or**

*nodes***, 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**

*elements***takes —**

*searching***time to execute, where**

*O(N)***— the number of nodes in the collection.**

*N*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 yourselfSample implementation of Doubly-LinkedListTest cases