Hello, young coders! Today, we’re going to dive into the world of data structures, specifically Doubly Linked Lists in Java, using our favorite programming language, Java. Don’t worry if you’re new to this; I’ll explain everything in simple, easy-to-understand terms. Let’s get started!
Table of Contents
What is a Doubly Linked Lists?
A Doubly Linked List is a type of data structure that consists of nodes. Each node has three parts: the data and two links that point to the previous and next node in the sequence. This means you can traverse the list in both directions: forwards and backwards. Cool, right?
class Node {
int data;
Node prev;
Node next;
}
Why use a Doubly Linked Lists?
Doubly Linked Lists are super useful because they allow us to traverse in both directions. This can be really handy when we need to look at the elements before and after a certain point in the list.
Creating a Doubly Linked List
Let’s create a simple Doubly Linked List. We’ll start by creating the Node class, which will represent each element in our list.
public class Node {
int data;
Node prev;
Node next;
// Node class constructor
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
Now, let’s create our DoublyLinkedList class. This class will contain a head and a tail node to keep track of the start and end of the list.
public class DoublyLinkedList {
Node head;
Node tail;
// DoublyLinkedList class constructor
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
}
Adding Elements to the List
We can add elements to our list with the addNode method. This method will create a new node with the given data and add it to the end of the list.
public void addNode(int data) {
Node newNode = new Node(data);
// If the list is empty, make the new node the head and tail
if (head == null) {
head = tail = newNode;
head.prev = null;
tail.next = null;
} else {
// Add the new node at the end of the list and update the tail
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
tail.next = null;
}
}
Displaying the List
We can display our list with the display method. This method will print out the data in each node, starting from the head and moving to the tail.
public void display() {
Node current = head;
if (head == null) {
System.out.println("The list is empty");
return;
}
System.out.println("Nodes of the doubly linked list: ");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
Node Structure
In a Doubly Linked List, each node contains three fields: data, prev, and next.
class Node {
int data; // This holds the data (could be any type)
Node prev; // This points to the previous node in the list
Node next; // This points to the next node in the list
}
The data field holds the information. The prev and next fields are pointers to the previous and next node in the list, respectively.
Traversing the List
One of the main advantages of a Doubly Linked List is that it can be traversed in both directions. You can start at the head and move towards the tail (forward direction), or start at the tail and move towards the head (backward direction).
Here’s how you can traverse the list in the forward direction:
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
And here’s how you can traverse the list in the backward direction:
Node current = tail;
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
Inserting Nodes
You can insert nodes at the beginning, at the end, or at a specific position in the list. Here’s how you can insert a node at the end of the list:
public void addNode(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
head.prev = null;
tail.next = null;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
tail.next = null;
}
}
Deleting Nodes
Deleting nodes is also straightforward. You can delete nodes from the beginning, from the end, or from a specific position in the list. Here’s how you can delete a node from the end of the list:
public void deleteNode() {
if (tail == null) {
System.out.println("The list is empty");
} else {
tail = tail.prev;
if (tail != null) {
tail.next = null;
} else {
head = null;
}
}
}Inserting at the Beginning
You can insert a new node at the beginning of the list. Here’s how:
public void insertAtStart(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
head.prev = null;
tail.next = null;
} else {
head.prev = newNode;
newNode.next = head;
head = newNode;
head.prev = null;
}
}
Inserting at a Specific Position
You can also insert a new node at a specific position in the list. Here’s how:
public void insertAtPosition(int data, int position) {
Node newNode = new Node(data);
Node current = head;
int i = 1;
if (position == 1) {
insertAtStart(data);
return;
}
while (i < position - 1 && current != null) {
current = current.next;
i++;
}
if (current != null) {
newNode.next = current.next;
newNode.prev = current;
current.next = newNode;
if (newNode.next != null) {
newNode.next.prev = newNode;
}
} else {
System.out.println("The position does not exist.");
}
}
Deleting from the Beginning
You can delete a node from the beginning of the list. Here’s how:
public void deleteFromStart() {
if (head == null) {
System.out.println("The list is empty");
} else {
head = head.next;
if (head != null) {
head.prev = null;
} else {
tail = null;
}
}
}
Deleting from a Specific Position
You can also delete a node from a specific position in the list. Here’s how:
public void deleteFromPosition(int position) {
Node current = head;
int i = 1;
if (position == 1) {
deleteFromStart();
return;
}
while (i < position && current != null) {
current = current.next;
i++;
}
if (current != null) {
current.prev.next = current.next;
if (current.next != null) {
current.next.prev = current.prev;
}
} else {
System.out.println("The position does not exist.");
}
}
I hope this gives you a more detailed understanding of Doubly Linked Lists in Java. Remember, the best way to learn is by doing. So, try to implement these concepts in your own code. Happy coding! 🚀
