Doubly linked list is a variation of linked list. Each node has references to the previous and next node. You can define both head and tail nodes, thus allowing the traversal in a bi-directional fashion. Java API LinkedList is implemented as doubly linked list.
Deque is a double-ended queue. You can add and remove items at either end. Deque is more versatile than either stack or queue. Doubly linked list is perfect data structure to implement deque.
Table of Content
- Map of linked list implementations
- Define classes
- Add element
- Delete element
- Search by key
- Print elements
Map of linked list implementations
Part 1 – Linked list implementation 
Part 2 – Doubly linked list implementation
Part 3 – Ciucular linked list implementation
Define classes
The Node class has three variables: data stores the value, next is the reference to the next node, and prev is the reference to the previous node. DoublyLinkList class has variables of head, tail and length. The head always points to the first node. The tail always points to the last node. The length keeps track of number of nodes in the list.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class DllNode<T> { protected T data; protected DllNode<T> next = null; protected DllNode<T> prev = null; //Constructor, Time O(1), Space O(1) public DllNode(T value) { this.data = value; } //Override, Time O(1), Space O(1) public String toString() { return String.valueOf(data); } } public class DoublyLinkList<T> { protected DllNode<T> head = null; protected DllNode<T> tail = null; private int length = 0; //other methods } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class DllNode { //Constructor, Time O(1), Space O(1) constructor(value) { this.data = value; this.next = null; this.prev = null; } //Override, Time O(1), Space O(1) toString() { return this.data; } } class DoublyLinkList { constructor () { this.head = null; this.tail = null; this.length = 0; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class DllNode: #Constructor, Time O(1), Space O(1) def __init__(self, value) : self.data = value self.next = None self.pre = None #Override, Time O(1), Space O(1) def __str__(self): return str(self.data) class DoublyLinkList : # Constructor, Time O(1), Space O(1) def __init__(self) : self.head = None self.tail = None self.length = 0 |
Add element
InsertFirst: To add an element, create a new node with the value first. When add a node at the front, the next pointer points to head first. Then move the head to the new node.
Java
|
1 2 3 4 5 6 7 8 9 10 11 |
//Add at the head, Time O(1), Space O(1) public void insertFirst(T data) { DllNode<T> newNode = new DllNode<T>(data); newNode.next = head; if(head != null) head.prev = newNode; head = newNode; if (tail == null) tail = newNode; length++; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 |
//Add at the head, Time O(1), Space O(1) insertFirst(data) { var newNode = new DllNode(data); newNode.next = this.head; if (this.head != null) this.head.prev = newNode; this.head = newNode; if (this.tail == null) this.tail = newNode; this.length++; } |
Python
|
1 2 3 4 5 6 7 8 9 10 |
#Add at the head, Time O(1), Space O(1) def insert_first(self, value) : newNode = DllNode(value) if self.head == None: # edge case self.tail = newNode else: self.head.pre = newNode newNode.next = self.head self.head = newNode self.length += 1 |
Doodle
InsertLast: when adding a node at the end, the new node’s prev pointer points to the tail first. Then move the tail to the new node.
Java
|
1 2 3 4 5 6 7 8 9 10 11 |
//Add at the tail, Time O(1), Space O(1) public void insertLast(T data) { DllNode<T> newNode = new DllNode<>(data); newNode.prev = tail; if (tail != null) tail.next = newNode; tail = newNode; if(head == null) head = newNode; length++; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 |
//Add at the tail, Time O(1), Space O(1) insertLast(data) { var newNode = new DllNode(data); newNode.prev = this.tail; if (this.tail != null) this.tail.next = newNode; this.tail = newNode; if (this.head == null) this.head = newNode; this.length++; } |
Python
|
1 2 3 4 5 6 7 8 9 10 |
#Add at the tail, Time O(1), Space O(1) def insert_last(self, value) : newNode = DllNode(value) if self.head == None: self.head = newNode else: self.tail.next = newNode newNode.pre = self.tail self.tail = newNode self.length += 1 |
Doodle
Delete element
DeleteFirst: To delete element at the front, you have to check three cases: the list is empty, the list has one node, in which head and front point to the same node; or list has more than one node.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//delete the first node, Time O(1), Space O(1) public void deleteFirst() { if (head == null) return; if (head != tail) { head = head.next; head.prev = null; length--; } else { head = tail = null; length = 0; } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//delete the first node, Time O(1), Space O(1) deleteFirst() { if (this.head == null) return; if (this.head != this.tail) { this.head = this.head.next; this.head.prev = null; this.length--; } else { this.head = this.tail = null; this.length = 0; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
#delete the first node, Time O(1), Space O(1) def delete_first(self) : if self.head == None: return if self.head != self.tail : self.head = self.head.next self.head.pre = None self.length -= 1 else : self.head = self.tail = None self.length = 0 |
Doodle
DeleteLast: The same as deleting an element at front, to delete an element at the end, you have to consider three situations, and move the head and tail pointers accordingly.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//delete the last node, Time O(1), Space O(1) public void deleteLast() { if (tail == null) return; if (head != tail) { tail = tail.prev; tail.next = null; length--; } else { head = tail = null; length = 0; } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//delete the last node, Time O(1), Space O(1) deleteLast() { if (this.tail == null) return; if (this.head != this.tail) { this.tail = this.tail.prev; this.tail.next = null; this.length--; } else { this.head = this.tail = null; this.length = 0; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
#delete the last node, Time O(1), Space O(1) def delete_last(self) : if self.tail == None: return if self.head != self.tail: self.tail = self.tail.pre self.tail.next = None self.length -= 1 else : self.head = self.tail = None self.length = 0 |
Doodle
Delete by key: To delete an element by the key, it is easier to define a method to delete node first. To delete a node, you have to set the next and prev from both side. To delete the key, starting from the head, compare each node’s value with the key. If the data is not equal to the key, move to the next node. Repeat until you find the node with the value the same as the key. Backup the node’s next to next variable. Delete the node and assign the next to the current node.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
//Delete all nodes with key, Time O(n), Space O(1), n is number of nodes in list public DllNode<T> delete(T key) { if (head == null) return null; DllNode<T> p = head; DllNode<T> next; while (p != null) { if (p.data == key) { next = p.next; deleteNode(p); p = next; } else p = p.next; } return head; } //Remove a node, Time O(1), Space O(1) private void deleteNode(DllNode<T> node) { if (node == null) return; if (node.prev != null) node.prev.next = node.next; else head = node.next; //edge case if (node.next != null) node.next.prev = node.prev; else tail = node.prev; //edge case length--; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
//Delete all nodes with key, Time O(n), Space O(1), n is number of nodes in list delete(key) { if (this.head == null) return null; var p = this.head; var next = null; while (p != null) { if (p.data == key) { next = p.next; this.deleteNode(p); p = next; } else p = p.next; } return this.head; } //Remove a node, Time O(1), Space O(1) deleteNode(node) { if (node == null) return; if (node.prev != null) node.prev.next = node.next; else this.head = node.next; //edge case if (node.next != null) node.next.prev = node.prev; else this.tail = node.prev; //edge case this.length--; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#Delete all nodes with key, Time O(n), Space O(1), n is number of nodes in list def delete(self, key) : if self.head == None: #edge case, empty list return curr = self.head while curr.data != key: curr = curr.next if curr == None: return if curr == self.head: # edge case, the node is head self.head = curr.next else: curr.pre.next = curr.next if curr == self.tail: # edge case, the node is tail self.tail = curr.pre else: curr.next.pre = curr.pre self.length -= 1 |
Doodle
Search by key
In doubly linked list, to search by key is the same as search in linked list. Assign the current node reference to head. Compare the data with the key. If they are not equal, move the reference to the next node. Repeat until you find the node with value the same as the key. Return this node. If no node is found when the reference reaches the end, return null.
Java
|
1 2 3 4 5 6 7 8 9 10 |
//Search by key, Time O(n), Space O(1) public DllNode<T> search(T key) { DllNode<T> p = head; while (p != null) { if (p.data == key) return p; p = p.next; } return null; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Search by key, Time O(n), Space O(1) search(key) { var p = this.head; while (p != null) { if (p.data == key) return p; p = p.next; } return null; } |
Python
|
1 2 3 4 5 6 7 8 |
#Search by key, Time O(n), Space O(1) def search(self, key) : curr = self.head while curr != None : if curr.data == key: return curr curr = curr.next return None |
Doodle
Print elements
To print doubly linked list, you shall print forward and backward. First starting from the head, print the value of each node, then move to its next node. Repeat until you reach the end. Next starting from the tail, print each node, and move to its prev node. Repeat until you reach the head.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//Print from head to tail, Time O(n), Space O(1) public void print() { if (length == 0) { System.out.println("The list is empty"); return; } System.out.print("doubly linked List (first-->last): "); DllNode<T> p = head; while(p != null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); System.out.print("doubly linked List (last-->first): "); p = tail; while (p != null) { System.out.print(p.data + " "); p = p.prev; } System.out.println(); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
//Print from head to tail, Time O(n), Space O(1) print() { if (this.length == 0) { console.log ("The list is empty"); return; } console.log("doubly linked List (first-->last): "); var p = this.head; var s = ''; while(p != null) { s += p.data + ' '; p = p.next; } console.log(s); console.log("doubly linked List (last-->first): "); p = this.tail; s = ''; while (p != null) { s += p.data + ' '; p = p.prev; } console.log(s); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#Print from head to tail, Time O(n), Space O(1) def print(self) : if self.length ==0: print ("The list is empty") return print("doubly linked List (first-->last): ") curr = self.head while curr != None : print(str(curr.data), end = ' ') curr = curr.next; print() print("doubly linked List (last-->first): ") curr = self.tail; while curr != None : print(str(curr.data), end = ' ') curr = curr.pre; print() |
Doodle
Free download
Download Java, JavaScript and Python code
Data structures and Java collections
Why Java LinkedList class is a doubly linked list?
Doubly linked lists have advantages over linked lists. A node in a doubly linked list has references to the previous and next nodes. There are pointers at head and tail. So many operations such as insert-last and delete-last take O(1) time. It trades space for time. That’s why Java LinkedList class is a a doubly linked list.