Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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 vs 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
Doubly Linked List

Dou­bly Linked List

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

Doubly Linked List - Node

Dou­bly Linked List — Node

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
Doubly Linked List:  1 2
Adding Node 3 at the End
Doubly Linked List:  1 2 3
Adding node after 2
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:

    Dou­blyLinkedList d = new Dou­blyLinkedList();
    Node x = d.addAtStart(2);
    Dou­blyLinkedList d2 = new Dou­blyLinkedList();
    d2.addAfter(10, x);

    This will add a node into d, with­out change the mem­bers of d.
    Mean­while, d2 keeps empty.

    In a word, I think the type Node must be hid­den inside DoublyLinkedList…