3.
To develop a doubly linked list in Java with forward and backward traversal, along with
insertion and deletion.
//Doubly Linked List
class DoublyLinkedList {
// Node class for doubly linked list
static class Node {
int data;
Node next;
Node prev;
// Constructor to create a new node
Node(int data) {
this.data = data;
next = null;
prev = null;
}
}
Node head; // Head of the doubly linked list
// Method to insert a node at the end of the doubly linked list
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode; // If the list is empty, make the new node as head
return;
}
Node last = head;
while (last.next != null) { // Traverse to the end of the list
last = last.next;
}
last.next = newNode; // Change the next of the last node
newNode.prev = last; // Change the prev of the new node
}
// Method to insert a node at the beginning of the doubly linked list
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode; // If the list is empty, make the new node as head
return;
}
head.prev = newNode; // Change the prev of head node to new node
newNode.next = head; // Change next of new node to head
head = newNode; // Move the head to point to the new node
}
// Method to delete a node from the doubly linked list
public void deleteNode(int data) {
if (head == null) {
System.out.println("List is empty.");
return;
}
Node current = head;
while (current != null && current.data != data) { // Find the node to be deleted
current = current.next;
}
if (current == null) {
System.out.println("Node not found.");
return;
}
if (current.prev != null) { // If the node to be deleted is not the first node
current.prev.next = current.next;
} else { // If the node to be deleted is the first node
head = current.next;
}
if (current.next != null) { // If the node to be deleted is not the last node
current.next.prev = current.prev;
}
}
// Method to traverse the list in forward direction
public void traverseForward() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// Method to traverse the list in backward direction
public void traverseBackward() {
Node current = head;
if (current == null) {
System.out.println("List is empty.");
return;
}
while (current.next != null) { // Go to the last node
current = current.next;
}
while (current != null) { // Traverse backwards
System.out.print(current.data + " ");
current = current.prev;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
// Insert nodes at the end
dll.insertAtEnd(10);
dll.insertAtEnd(20);
dll.insertAtEnd(30);
dll.insertAtEnd(40);
// Insert a node at the beginning
dll.insertAtBeginning(5);
// Forward traversal
System.out.println("Forward Traversal:");
dll.traverseForward(); // Output: 5 10 20 30 40
// Backward traversal
System.out.println("Backward Traversal:");
dll.traverseBackward(); // Output: 40 30 20 10 5
// Delete a node
dll.deleteNode(20);
System.out.println("After Deleting 20:");
// Forward traversal after deletion
dll.traverseForward(); // Output: 5 10 30 40
}
}
