[go: up one dir, main page]
Scribd
Upload
31 views4 pages

Doubly Linked Lists

A doubly linked list is a more complex data structure than a singly linked list, but it offers several advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. This is because each node in the list contains a pointer to the previous node and a pointer to the next node. This allows for quick and easy insertion and deletion of nodes from the list, as well as efficient traversal of the list in both directions.

Uploaded by

Jeeva Sadhasivam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views4 pages

Doubly Linked Lists

A doubly linked list is a more complex data structure than a singly linked list, but it offers several advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. This is because each node in the list contains a pointer to the previous node and a pointer to the next node. This allows for quick and easy insertion and deletion of nodes from the list, as well as efficient traversal of the list in both directions.

Uploaded by

Jeeva Sadhasivam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

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
}
}

You might also like