### Sorted DoublyLinkedList - insert and delete specific Node in java

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 >

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.

1) Stacks, Queues in Data Structures in java

2) Single LinkedList implementations in Data Structures in java:-

3) Doubly LinkedList implementations in Data Structures in java:-

5) Some of the tricky and interesting Single LinkedList implementations in Data Structures in java

6) Binary tree tutorial in java >