In this Data structures tutorial we will learn what is Doubly LinkedList in java with example, diagrams and program. We will learn how to implement your own Doubly LinkedList in java. We will learn how to insert and delete at first of Doubly LinkedList in java. We will also learn complexity of insert and delete operations at first of Doubly LinkedList in java.
What is Doubly LinkedList in java?
A Doubly linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference to the next and previous node in the sequence.
What is complexity of insert and delete at first of Doubly LinkedList in java?
Complexity of insertion and deletion at first of Doubly LinkedList is O(1) in java.
Important methods used in below doubly LinkedList program/example are as follows>
insertFirst(int data)- Insert New Node at first of Doubly LinkedList in java.
deleteFirst() -Deletes first Node of Doubly LinkedList in java.
displayFrwd() - displays doubly linkedList in forward direction in java.
displayBckwrd() - displays doubly linkedList in forward direction in java.
Logic explanation to insert and delete at first of Doubly LinkedList with diagram in java >
Let’s see how we are going to insert node at first in Doubly LinkedList in java :-
Here we have made newNode’s next pointing to old first. & first point to new node.
Let’s see how we can delete first node from Doubly LinkedList.
Here we make first point to first.next and there is no live reference to node with data=11(i.e. deleted node), so this node becomes eligible for garbage collection by JVM as well.
Full Program/Example of insert and delete at first of doubly LinkedList in java >
/**
*Exception to indicate that 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 + " ");
}
}
/**
* Doubly LinkedList class
*/
class LinkedList {
private Node first; // ref to first link on LinkedList
private Node last; // ref to last link on LinkedList
/**
* Doubly LinkedList constructor
*/
public LinkedList(){
first = null;
}
/**
* Insert New Node at first position of Doubly LinkedList
*/
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 of Doubly linkedList.
*/
public Node deleteFirst() {
if(first==null){ //means LinkedList in empty, throw exception.
throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
}
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;
}
/*
* Display Doubly 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 Doubly 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 */
/**
* DoublyLinkedListInsertDeleteAtFirstExample - Main class - To test Doubly LinkedList.
*/
public class DoublyLinkedListInsertDeleteAtFirstExample {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList(); // creation of Linked List
linkedList.insertFirst(11);
linkedList.insertFirst(21);
linkedList.insertFirst(59);
linkedList.insertFirst(14);
linkedList.insertFirst(39);
linkedList.displayFrwd(); // display DoublyLinkedList
linkedList.displayBckwrd();
System.out.print("Deleted Nodes: ");
Node deletedNode = linkedList.deleteFirst(); //delete Node
deletedNode.displayNode(); //display deleted Node.
deletedNode = linkedList.deleteFirst(); //delete Node.
deletedNode.displayNode(); //display deleted Node.
System.out.println();// sysout used to format output
linkedList.displayFrwd(); // display DoublyLinkedList
linkedList.displayBckwrd();
}
}
/*OUTPUT
Displaying in forward direction [first--->last] : 39 14 59 21 11
Displaying in backward direction [last-->first] : 11 21 59 14 39
Deleted Nodes: 39 14
Displaying in forward direction [first--->last] : 59 21 11
Displaying in backward direction [last-->first] : 11 21 59
*/
|
Complexity of insert and delete at first in doubly LinkedList in java >
Complexity of insertion and deletion at first in doubly LinkedList is O(1).
As we have to insert at first> best case, average case and worst case are same in java.
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
