In this article we will see what is doubly linked list, how it is different from other linked list and how to implement it.
Earlier we have seen what is Singly Linked List and Circular Linked List and How to implement it. In a way you say that it’s an extension of singly linked list. I would suggest that if you do not about Linked list, first read “Singly Linked List”
Let’s see the difference between singly and doubly linked list.
Singly Linked List vs Doubly Linked List
Singly Linked List | Doubly Linked List |
Easy Implement | Not easy |
Less memory | More Memory |
Can traverse only in forward direction | Traverse in both direction, back and froth |
So as we can see the in doubly linked list each node has two references, next and prev which makes it possible to traverse in both directions.
Let’s see how the Node structure will look like
class Node{ int data; Node next; Node previous; public Node(int data){ this.data = data; next = null; previous = null; } }
Operations:
NOTE: we are two references 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 beginning 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 reference. If size is 0 then make the new node as head and tail else put node at the end of the list using tail reference and make the new node as tail.
Delete at the Start : Delete a node from beginning 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 Element at Index : Return the element at specific 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).
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class DoublyLinkedList { | |
int size =0; | |
Node head = null; | |
Node tail = null; | |
public Node addAtStart(int data){ | |
System.out.println("Adding Node " + data + " at the start"); | |
Node n = new Node(data); | |
if(size==0){ | |
head = n; | |
tail = n; | |
}else{ | |
n.next = head; | |
head.previous = n; | |
head = n; | |
} | |
size++; | |
return n; | |
} | |
public Node addAtEnd(int data){ | |
System.out.println("Adding Node " + data + " at the End"); | |
Node n = new Node(data); | |
if(size==0){ | |
head = n; | |
tail = n; | |
}else{ | |
tail.next = n; | |
n.previous = tail; | |
tail =n; | |
} | |
size++; | |
return n; | |
} | |
public Node addAfter(int data, Node prevNode){ | |
if(prevNode==null){ | |
System.out.println("Node after which new node to be added cannot be null"); | |
return null; | |
}else if(prevNode==tail){//check if it a last node | |
return addAtEnd(data); | |
}else{ | |
System.out.println("Adding node after "+ prevNode.data); | |
//create a new node | |
Node n = new Node(data); | |
//store the next node of prevNode | |
Node nextNode = prevNode.next; | |
//make new node next points to prevNode | |
n.next = nextNode; | |
//make prevNode next points to new Node | |
prevNode.next = n; | |
//make nextNode previous points to new node | |
nextNode.previous = n; | |
//make new Node previous points to prevNode | |
n.previous = prevNode; | |
size++; | |
return n; | |
} | |
} | |
public void deleteFromStart(){ | |
if(size==0){ | |
System.out.println("\nList is Empty"); | |
}else{ | |
System.out.println("\ndeleting node " + head.data + " from start"); | |
head = head.next; | |
size—; | |
} | |
} | |
public void deleteFromEnd(){ | |
if(size==0){ | |
System.out.println("\nList is Empty"); | |
}else if(size==1){ | |
deleteFromStart(); | |
}else{ | |
//store the 2nd last node | |
int x = tail.data; | |
Node prevTail = tail.previous; | |
//detach the last node | |
tail = prevTail; | |
tail.next=null; | |
System.out.println("\ndeleting node " + x + " from end"); | |
size—; | |
} | |
} | |
public int elementAt(int index){ | |
if(index>size){ | |
return –1; | |
} | |
Node n = head; | |
while(index–1!=0){ | |
n=n.next; | |
index—; | |
} | |
return n.data; | |
} | |
//get Size | |
public int getSize(){ | |
return size; | |
} | |
public void print(){ | |
Node temp = head; | |
System.out.print("Doubly Linked List: "); | |
while(temp!=null){ | |
System.out.print(" " + temp.data); | |
temp = temp.next; | |
} | |
System.out.println(); | |
} | |
public static void main(String[] args) { | |
DoublyLinkedList d = new DoublyLinkedList(); | |
Node x = d.addAtStart(2); | |
d.addAtStart(1); | |
d.print(); | |
d.addAtEnd(3); | |
d.print(); | |
d.addAfter(4,x); | |
d.print(); | |
d.deleteFromStart(); | |
d.print(); | |
System.out.println("Element at index 2: "+d.elementAt(2)); | |
d.addAtStart(1); | |
d.print(); | |
d.deleteFromEnd(); | |
d.print(); | |
System.out.println("Size of the Linked List: " + d.getSize()); | |
} | |
} | |
class Node{ | |
int data; | |
Node next; | |
Node previous; | |
public Node(int data){ | |
this.data = data; | |
next = null; | |
previous = null; | |
} | |
} | |
Output:
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
Thank you for this precious resource. But I have two questions.
1. Can you tell me why you declare the type of these method “Node” and you are returning n in these methods addAtStart, addAtEnd, addAfter?
2. Don’t we declare these methods types void?
Yes you can, it’s just a way u implement it. In the code we are just passing the integer and we are creating a node inside the function ,Sometimes you might need the reference of that node to be used so instead of traversing all the nodes, it’s good to have a reference back from the function.
Could you please tell me what is the actual role of ‘return n’ in these methods?
Just wow for your logic! I just dirty my hands and at the end I realize what you did in your code that’s awesome! I will say “just wow”!
Thank for the tutorial. But I think return a Node type is a bug here. The “Node” type should not be exposed to outside, otherwise imagine:
DoublyLinkedList d = new DoublyLinkedList();
Node x = d.addAtStart(2);
DoublyLinkedList d2 = new DoublyLinkedList();
d2.addAfter(10, x);
This will add a node into d, without change the members of d.
Meanwhile, d2 keeps empty.
In a word, I think the type Node must be hidden inside DoublyLinkedList…
Hi, Can anyone post a solution for this please :
“Replace kth node from beginning with kth node from end in case of a doubly linked list”
Either in java or in c.