In this Data structures tutorial we will learn what is Sorted Doubly LinkedList in java with example, diagrams and program. We will learn how to implement your own Sorted Doubly LinkedList in java. We will learn how to insert and delete node of Sorted Doubly LinkedList in java. We will also learn complexity of insert and delete of nodes from Sorted Doubly LinkedList in java.
What is sorted Doubly LinkedList in java?
Doubly Sorted Linked List is a data structure in which all the nodes are arranged in sorted manner in java.
We will implement Sorted DoublyLinkedList in ascending order of its data in java.
Below we are going to implement Sorted Doubly LinkedList without taking help of api’s provided by java.
What is complexity of insert and delete of nodes from Sorted Doubly LinkedList in java?
Complexity of insertion in Sorted Doubly LinkedList is O(n).
Complexity of deletion from Sorted Doubly LinkedList is O(n).
Important methods used in below sorted doubly LinkedList program/example are as follows>
insertSorted(int data)- Insert Node in Sorted DoublyLinkedList (in between of other Nodes) in java.
deleteSpecificNode(int deleteKey) Method deletes specific Node from sorted DoublyLinkedList in java.
displayFrwd() - displays sorted doubly linkedList in forward direction in java.
displayBckwrd() - displays sorted doubly linkedList in forward direction in java.
Logic explanation to insert and delete node from sorted Doubly LinkedList with diagram in java >
Let’s see how we are going to insert node in Sorted Doubly LinkedList in java:-
Here as soon as we detect the position at which node is to be inserted(i.e. current) we make >current point to previous node- so now our new current is one node back.
>Now make newNode’s next point to current’s next &
>current’s next point to newnode.
Let’s see how we are going to delete specific node from Sorted Doubly LinkedList in java:-
Here as soon as we detect that node to be deleted we make current node’s previous(one node back) next’s point to current’s next, doing so makes node pointed by current eligible for garbage collection as well.
Full Program/example to insert and delete node from sorted Doubly LinkedList in java >
/**
*Exception to indicate that sorted Doubly LinkedList is empty.
*/
class LinkedListEmptyException extends RuntimeException{
public LinkedListEmptyException(){
super();
}
public LinkedListEmptyException(String message){
super(message);
}
}
/**
*Node class, which holds data and contains next which points to next Node.
*/
class Node {
public int data; // data in Node.
public Node next; // points to next Node in list.
public Node previous; // points to previous Node in list.
/**
* Constructor
*/
public Node(int data){
this.data = data;
}
/**
* Display Node's data
*/
public void displayNode() {
System.out.print( data + " ");
}
}
/**
* Sorted Doubly LinkedList class
*/
class LinkedList {
private Node first; // ref to first link on LinkedList
private Node last; // ref to last link on LinkedList
/**
* LinkedList constructor
*/
public LinkedList(){
first = null;
}
/**
* Insert New Node at first position
*/
public void insertFirst(int data){ // insert at front of list
Node newNode = new Node(data); // creation of new node.
if (first == null) // means LinkedList is empty.
last = newNode; // newNode <--- last
else
first.previous = newNode; // newNode <-- old first
newNode.next = first; // newNode --> old first
first = newNode; // first --> newNode
}
/**
* Delete first node.
*/
public Node deleteFirst() { // (assumes non-empty list)
Node tempNode = first;
if (first.next == null) // if only one item
last = null; // null <-- last
else
first.next.previous = null; // null <-- old next
first = first.next; // first --> old next
return tempNode;
}
/**
*Insert Node in Sorted DoublyLinkedList (in between of other Nodes).
*Note:- Sorted DoublyLinkedList is arranged in ascending order.
*/
public void insertSorted(int newKey){
Node newNode=new Node(newKey);
//Case1: when there is no element in LinkedList
if(first==null){ //means LinkedList is empty, make first point to new Node.
first=last=newNode;
System.out.println("Node with data="+newNode.data+" inserted at first.");
return;
}
//Case2: when newNode should be placed at first.
Node current=first;
if(current.data>=newNode.data){
newNode.next=first;
first.previous=newNode;
first=newNode; //first ---> newNode
System.out.println("Node with data="+newNode.data+" inserted at first Node, beacuse newNode is smallest of existing Nodes.");
return;
}
//Case3: when newNode should be at some position other than first.
while(true){
if(newNode.data>current.data){ //entering inside if means we haven't find position for inserting node.
if(current.next==null){ //means current is the last node, insert node.
last.next=newNode;
newNode.previous=last;
last=newNode;
System.out.println("Node with data="+newNode.data+" inserted successfully at last of LinkedList.");
return;
}
current=current.next; //move to next node.
}
else{ //we have find position for inserting node.
current=current.previous; //make current point to previous node.
newNode.next=current.next; //make current's next point to newNode's next.
current.next.previous=newNode; //make previous of current's next node point to newNode.
newNode.previous=current; //make newNode's previous point to current.
current.next=newNode; //make current's next point to newNode.
System.out.println("Node with data="+newNode.data+" inserted successfully in middle of LinkedList.");
return;
}
}
}
/**
* Method deletes specific Node from DoublyLinkedList.
*/
public void deleteSpecificNode(int deleteKey){
//Case1: when there is no element in LinkedList
if(first==null){ //means LinkedList in empty, throw exception.
throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
}
//Case2: when there are elements in LinkedList
Node current=first;
while(current.data!=deleteKey){
if(current.next==null){
System.out.println("Node with data="+deleteKey+" wasn't found for deletion.");
return;
}
current=current.next; //move to next node.
}
if(current==first){
System.out.println("Node with data="+current.data+" was found on first and has been deleted.");
first=first.next;
first.previous=null;
}
else if(current==last){
System.out.println("Node with data="+current.data+" was found on last has been deleted.");
last=last.previous;
last.next=null;
}
else{
current.previous.next=current.next;
current.next.previous=current.previous;
System.out.println("Node with data="+current.data+" has been deleted.");
}
}
/*
* Display LinkedList in forward direction
*/
public void displayFrwd() {
System.out.print("Displaying in forward direction [first--->last] : ");
Node tempDisplay = first; // start at the beginning of linkedList
while (tempDisplay != null){ // Executes until we don't find end of list.
tempDisplay.displayNode();
tempDisplay = tempDisplay.next; // move to next Node
}
System.out.println("");
}
/*
* Display LinkedList in backward direction
*/
public void displayBckwrd() {
System.out.print("Displaying in backward direction [last-->first] : ");
Node tempDisplay = last; // start at the end of linkedList
while (tempDisplay != null) {// Executes until we don't find start of list.
tempDisplay.displayNode();
tempDisplay = tempDisplay.previous; // move to previous Node
}
System.out.println("");
}
}
/** Copyright (c), AnkitMittal www.JavaMadeSoEasy.com */
/**
* SortedDoublyLinkedListInsertDeleteNodeExample - Main class - To test sorted Doubly LinkedList.
*/
public class SortedDoublyLinkedListInsertDeleteNodeExample {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList(); // creation of Linked List
linkedList.insertSorted(11);
linkedList.insertSorted(21);
linkedList.insertSorted(59);
linkedList.insertSorted(14);
linkedList.insertSorted(39);
linkedList.insertSorted(66);
linkedList.insertSorted(33);
linkedList.displayFrwd(); // display DoublyLinkedList
linkedList.displayBckwrd();
System.out.println();// sysout used to format output
linkedList.deleteSpecificNode(11); //delete Node
linkedList.deleteSpecificNode(21); //delete Node
linkedList.deleteSpecificNode(29); //delete Node
linkedList.deleteSpecificNode(59); //delete Node
linkedList.displayFrwd(); // display DoublyLinkedList
linkedList.displayBckwrd();
}
}
/*OUTPUT
Node with data=11 inserted at first.
Node with data=21 inserted successfully at last of LinkedList.
Node with data=59 inserted successfully at last of LinkedList.
Node with data=14 inserted successfully in middle of LinkedList.
Node with data=39 inserted successfully in middle of LinkedList.
Node with data=66 inserted successfully at last of LinkedList.
Node with data=33 inserted successfully in middle of LinkedList.
Displaying in forward direction [first--->last] : 11 14 21 33 39 59 66
Displaying in backward direction [last-->first] : 66 59 39 33 21 14 11
Node with data=11 was found on first and has been deleted.
Node with data=21 has been deleted.
Node with data=29 wasn't found for deletion.
Node with data=59 has been deleted.
Displaying in forward direction [first--->last] : 14 33 39 66
Displaying in backward direction [last-->first] : 66 39 33 14
*/
|
Complexity of insert and delete node from sorted Doubly LinkedList in java >
Insertion of node in Sorted Doubly LinkedList in java -
Best Case : O(1), when there is no node in List and insertion is to be done at first.
or, node to be inserted is smallest of existing nodes in LinkedList(in case if
we are arranging LinkedList in ascending order.)
Average Case : O(n)
Worst Case : O(n)
Deletion of specific node from Sorted Doubly LinkedList in java -
Best Case : O(1), when node to be deleted is at first of Sorted doubly linkedList.
Average Case : O(n)
Worst Case : O(n)
Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.
RELATED LINKS>
1) Stacks, Queues in Data Structures in java
2) Single LinkedList implementations in Data Structures in java:-
>
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
3) Doubly LinkedList implementations in Data Structures in java:-
4)Implement Stack, Queue using LinkedList
5) Some of the tricky and interesting Single LinkedList implementations in Data Structures in java
6) Binary tree tutorial in java >