# Doubly Linked List Complete Implementation

In this arti­cle we will see what is dou­bly linked list, how it is dif­fer­ent from other linked list and how to imple­ment it.

Ear­lier we have seen what is Singly Linked List and Cir­cu­lar Linked List and How to imple­ment it. In a way you say that it’s an exten­sion of singly linked list. I would sug­gest that if you do not about Linked list, first read “Singly Linked List”

Let’s see the dif­fer­ence between singly and dou­bly linked list.

 Singly Linked List Dou­bly Linked List Easy Imple­ment Not easy Less mem­ory More Mem­ory Can tra­verse only in for­ward direction Tra­verse in both direc­tion, back and froth

So as we can see the in dou­bly linked list each node has two ref­er­ences, next and prev which makes it pos­si­ble to tra­verse in both directions.

Let’s see how the Node struc­ture will look like

```class Node{
int data;
Node next;
Node previous;
public Node(int data){
this.data = data;
next = null;
previous = null;
}
}
```

Oper­a­tions:

NOTE: we are two ref­er­ences here, head and tail. Head points the start of the linked list and tail points to the last node of the linked list.

Add at the Start : Add a node the begin­ning of the linked list. Its O(1). If size is 0 then make the new node as head and tail else put the at the start, change the head and do not change the tail.

Add at the End : Add a node at the end of the linked list. its O(1) since we have tail ref­er­ence. If size is 0 then make the new node as head and tail else put node at the end of the list using tail ref­er­ence and make the new node as tail.

Delete at the Start : Delete a node from begin­ning of the linked list and make the head points to the 2nd node in the list. Its O(1).

Get Size: returns the size of the linked list.

Get Ele­ment at Index : Return the ele­ment at spe­cific index, if index is greater than the size then return –1. its O(n) in worst case.

Print: Prints the entire linked list. O(n).

Com­plete Code:

Out­put:

```Adding Node 2 at the start
Adding Node 1 at the start
Adding Node 3 at the End
Doubly Linked List:  1 2 3
Doubly Linked List:  1 2 4 3
deleting node 1 from start
Doubly Linked List:  2 4 3
Element at index 2: 4
Adding Node 1 at the start
Doubly Linked List:  1 2 4 3
deleting node 3 from end
Doubly Linked List:  1 2 4
Size of the Linked List: 3
```

#### You may also like...

• ❤ Çell_O_hõliç.. ツ

Thank you for this pre­cious resource. But I have two ques­tions.
1. Can you tell me why you declare the type of these method “Node” and you are return­ing n in these meth­ods addAt­Start, addA­tEnd, addAfter?
2. Don’t we declare these meth­ods types void?

• tuto­ri­al­hori­zon

Yes you can, it’s just a way u imple­ment it. In the code we are just pass­ing the inte­ger and we are cre­at­ing a node inside the func­tion ‚Some­times you might need the ref­er­ence of that node to be used so instead of tra­vers­ing all the nodes, it’s good to have a ref­er­ence back from the function.

• ❤ Çell_O_hõliç.. ツ

Could you please tell me what is the actual role of ‘return n’ in these methods?

• ❤ Çell_O_hõliç.. ツ

Just wow for your logic! I just dirty my hands and at the end I real­ize what you did in your code that’s awe­some! I will say “just wow”!

• Wxu

Thank for the tuto­r­ial. But I think return a Node type is a bug here. The “Node” type should not be exposed to out­side, oth­er­wise imagine: