In this tutorial, we will learn how to insert an item in Doubly LinkedList in java at various positions. We will write a Java Program to add an element at the end, beginning or at the specified position in Doubly Linked List.
Java Program to add item at various positions in Doubly LinkedList
The explanation of the program in provided at the end of the program and a brief description is mentioned in the comments.
//A Node represents the element in a Doubly linked list
//An element in Doubly linked list contains the pointer to
//previous as well as next element of the list
class Node {
// Data stored in the node
String data;
//address of previous node in list
Node prev;
//address of next node in list
Node next;
// Constructor of this class will be used to initialize a node
public Node(String data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
//contains the address of first element
Node head;
//contains the address of last element
Node tail;
// Constructor to initialize an empty list
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
// Method to add a node with given data to the end of the list
public void add(String data) {
// Create a new node with given data
Node newNode = new Node(data);
// If the list is empty
if (head == null) {
// In the case of empty list, set head and tail to
//contain the address of this Node
head = newNode;
tail = newNode;
} else {
// Add the new node after the current tail
tail.next = newNode;
// newNode prev field contains the address of current tail
newNode.prev = tail;
// Now, newNode becomes the tail, so update tail to point this node
tail = newNode;
}
}
// Method to insert a node with given data at the beginning of the list
public void insertAtBeginning(String data) {
// Create a new node with given data
Node newNode = new Node(data);
// If the list is empty
if (head == null) {
// In the case of empty list, set head and tail to
//contain the address of this Node
head = newNode;
tail = newNode;
} else {
// newNode next field contains the address of current head
newNode.next = head;
// Update the prev field of current head to point newNode
head.prev = newNode;
// Now, newNode becomes the first element, Update the head field
head = newNode;
}
}
// Method to insert a node with given data at a specified position in the list
public void insertAtPosition(int position, String data) {
// Create a new node with given data
Node newNode = new Node(data);
// Check for invalid position
if (position <= 0) {
System.out.println("Invalid position");
return;
}
// If inserting at the beginning
if (position == 1) {
insertAtBeginning(data);
return;
}
// Initialize count
int count = 1;
// Start from the head of the list
Node current = head;
// Traverse to the node before the insertion point
while (current != null && count < position - 1) {
current = current.next;
count++;
}
// Check for invalid position
if (current == null) {
System.out.println("Invalid position");
return;
}
// Connect the new node to the next node
newNode.next = current.next;
// Connect the new node to the current node
newNode.prev = current;
// Update the previous reference of the next node
if (current.next != null) {
current.next.prev = newNode;
} else {
// Update the tail if the new node is inserted at the end
tail = newNode;
}
// Update the next reference of the current node
current.next = newNode;
}
// Method to display the elements of the list
public void display() {
// Start from the head of the list
Node current = head;
// If the list is empty
if (head == null) {
System.out.println("Doubly linked list is empty");
return;
}
System.out.println("Nodes of the doubly linked list:");
// Traverse the list until the end
while (current != null) {
// Print the data of the current node
System.out.print(current.data + " <-> ");
// Move to the next node
current = current.next;
}
System.out.println("null");
}
}
public class JavaDoublyLinkedList {
public static void main(String[] args) {
// Create a new doubly linked list
DoublyLinkedList dll = new DoublyLinkedList();
// Add elements to the list
dll.add("apple");
dll.add("banana");
dll.add("orange");
// Display the original doubly linked list
System.out.println("Original doubly linked list:");
dll.display();
// Insert "grape" at the beginning
dll.insertAtBeginning("grape");
// Display the list after inserting "grape" at the beginning
System.out.println("After inserting 'grape' at the beginning:");
dll.display();
// Insert "kiwi" at position 3
dll.insertAtPosition(3, "kiwi");
// Display the list after inserting "kiwi" at position 3
System.out.println("After inserting 'kiwi' at position 3:");
dll.display();
}
}
Output:
Original doubly linked list:
Nodes of the doubly linked list:
apple <-> banana <-> orange <-> null
After inserting 'grape' at the beginning:
Nodes of the doubly linked list:
grape <-> apple <-> banana <-> orange <-> null
After inserting 'kiwi' at position 3:
Nodes of the doubly linked list:
grape <-> apple <-> kiwi <-> banana <-> orange <-> null
Explanation of the program
- Node Class:
- It represents an element of Doubly linked list. Each node contains three fields:
data: Stores the value of the node, in this case, aString.prev: Points to the previous node in the list.next: Points to the next node in the list.
- DoublyLinkedList Class:
- This class contains methods to add elements at various positions.
- It has two fields:
head(contains address of first element) andtail(contains address of last element). - The constructor of this class initializes an empty list by setting both
headandtailtonull.
- Add Method:
- The
addmethod inserts the given element at the end of doubly linked list. - It checks if the list is empty or not, if empty then new node becomes head and tail both, else add element at the end and update tail.
- The
- InsertAtBeginning Method:
- The
insertAtBeginning()method inserts the new element at the beginning of the doubly linked list - Update prev field of current head to point new node and update next field of new node to point current head. Update head to point to new node.
- The
- InsertAtPosition Method:
- The
insertAtPosition()method inserts the new element at the specified position in the doubly linked list. - If the specified position is invalid or less than or equal to 0, it prints an error message and returns.
- If the position is 1, it calls the
insertAtBeginning()method. - Otherwise, it updates the next and previous references of the new node and adjacent nodes to insert the new node at the specified position.
- The
- Display Method:
- It traverses the whole list and print all elements.
- If the list is empty, it prints a message indicating that the list is empty.
- Main Method:
- In the
mainmethod, an instance of theDoublyLinkedListclass is created. - Few elements are added to list using the
add()method. - The current list is printed.
- Items are inserted at the beginning and at a specified position using the
insertAtBeginningandinsertAtPositionmethods, respectively. - The updated list is displayed after each insert method call.
- In the
Leave a Reply