Doubly linked list is a linked data structure that consists of a set of sequentially linked nodes. Each node contains two links (references to the previous and to the next node) and data. The links help to iterate the node forward and backward.
XOR-linked list allows doubly linked list to be implemented using a single link field in each node. The XOR linked list decrease the memory size compare than doubly linked list. The XOR linking has few drawbacks and it is difficult to debug using debugging tools.
Write a program to implement doubly ended linked list with all the operations.
Algorithm Explanation
 | Doubly linked list support insert, delete and iteration operations. |
| Each node contains data, link to the next node and link to the previous node. The insertion link breaks the previous and next node and link with a new node on both sides. |
| When to insert the node in a particular position, the doubly linked list require both previous and next node links. |
| Insertion and deletion may require more operations in doubly linked list and other operations are simplified in doubly linked list. |
Source Code
package com.dsacode.DataStructre.linkedlist;
class DoublyNode {
public int data;
public DoublyNode next;
public DoublyNode previous;
public DoublyNode(int d){
data = d;
}
public void displayLink() {
System.out.print(data );
}
}
public class DoublyLinkedlist {
private DoublyNode first;
private DoublyNode last;
public DoublyLinkedlist(){
first = null;
last = null;
}
public boolean isEmpty(){
return first == null;
}
public void insertFirst(int dd){
DoublyNode newNode = new DoublyNode(dd);
if (isEmpty())
last = newNode;
else
first.previous = newNode;
newNode.next = first;
first = newNode;
}
public void insertLast(int dd){
DoublyNode newNode = new DoublyNode(dd);
if (isEmpty())
first = newNode;
else {
last.next = newNode;
newNode.previous = last;
}
last = newNode;
}
public DoublyNode deleteFirst(){
DoublyNode temp = first;
if (first.next == null)
last = null;
else
first.next.previous = null;
first = first.next;
return temp;
}
public DoublyNode deleteLast(){
DoublyNode temp = last;
if (first.next == null)
first = null;
else
last.previous.next = null;
last = last.previous;
return temp;
}
public boolean insertAfter(long key, int dd) {
DoublyNode current = first;
while (current.data != key){
current = current.next;
if (current == null)
return false;
}
DoublyNode newNode = new DoublyNode(dd);
if (current == last) {
newNode.next = null;
last = newNode;
} else {
newNode.next = current.next;
current.next.previous = newNode;
}
newNode.previous = current;
current.next = newNode;
return true;
}
public DoublyNode deleteItem(long key) {
DoublyNode current = first;
while (current.data != key) {
current = current.next;
if (current == null)
return null;
}
if (current == first)
first = current.next;
else
current.previous.next = current.next;
if (current == last)
last = current.previous;
else
current.next.previous = current.previous;
return current;
}
public void display() {
System.out.print("List : ");
DoublyNode current = first;
while (current != null) {
current.displayLink();
System.out.print("->");
current = current.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
DoublyLinkedlist theList = new DoublyLinkedlist();
System.out.println("insert at front: 9, 56, 74");
theList.insertFirst(9);
theList.insertFirst(56);
theList.insertFirst(74);
theList.display();
System.out.println("insert at rear: 34, 47, 99");
theList.insertLast(34);
theList.insertLast(47);
theList.insertLast(99);
theList.display();
System.out.println();
System.out.println("Delete first item from List");
theList.deleteFirst();
System.out.println("Delete last item from List");
theList.deleteLast();
theList.display();
System.out.println();
System.out.println("Delete item '34' from List");
theList.deleteItem(34);
theList.display();
System.out.println();
System.out.println("insert 11 after 9 in List");
theList.insertAfter(9, 11);
theList.display();
}
}
Output
insert at front: 9, 56, 74 List : 74->56->9->NULL insert at rear: 34, 47, 99 List : 74->56->9->34->47->99->NULL Delete first item from List Delete last item from List List : 56->9->34->47->NULL Delete item '34' from List List : 56->9->47->NULL insert 11 after 9 in List List : 56->9->11->47->NULL
Source Explanation
| Insert function constructs the node using data, previous node, and next node details. It inserts the node in the appropriate location in the linked list. |
| Display function iterate all the elements and display. |
| Delete operation unlink between two nodes and free the allocated memory. |
Complexity
| Operations | Best Case | Average Case | worst Case |
|---|---|---|---|
| Search | – | O(n) | O(n) |
| Insertion | – | O(1) | O(1) |
| Deletion | – | O(1) | O(1) |
Real Applications
- Maintain references to active processes, threads, and other dynamic objects in operating system
- Stack, hash table, and binary tree can be implemented using a doubly linked list.
- Applications that have an MRU list (a linked list of file names)