Implement Doubly Linked List in Java
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
In this article, we have explored the design of Doubly Linked List and implemented it in Java Programming Language using the concepts of Object Oriented Programming.
What is a doubly linked list?
A doubly linked list is a data structure that is a sequence of elements, usually named nodes. Since each node has a reference to another node, you can link the nodes together in some sort of list and traverse it as a list. In Java, implementation is pretty easy, as you can make a class Node with contains itself. A doubly linked list has references to elements before and after, hence the name "doubly", and is different from a normal linked list which only has one reference to the next node.
The implementation is as below:
This is a class for Node, which is used in the doubly linked list:
private class Node {
int data;
Node prev;
Node next;
//constructor
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
data: the information the node is storing
prev: a reference to the previous node
next: a reference to the next node
As you can see, the class and contents of Node are private, but we can put the Node class inside of the DoublyLinkedList class as an inner class, which allows the outside class to access it's contents.
Next, we will use nodes to create the doubly linked list. Notice how the class has a field Node named head. This is the beginning of the linked list. This field is set to null at the start of the class because null signifies the end of the list.
For example, an empty linked list should only contain a head and end with null:
Head -> null
A linked list with 3 elements should look like this:
Head -> Node1 -> Node2 -> Node3 -> null
DoublyLinkedList class
Fields:
Node head
Methods:
insert (returns void, adds element to linked list)
remove (returns void, removes element from linked list)
print (returns void, prints elements of linked list to console)
insert Method:
This method inserts an element into the linked list.
public void insert(int data) {
Node newNode = new Node(data);
// This line handles the special case where you
// are adding to an empty list
if (head == null) {
head = newNode;
return;
}
// To traverse a linked list, we create a new Node
// called temp (or curr) so that we don't affect
// parts of the list. We set the new Node to head,
// which points to the first element of the list
// (or null if the list is empty). Then, we set
// temp to the next Node if there is one, and
// eventually stop when we reach the end of the
// list.
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
// Now, we set this place in the new list to the
// newNode that we created and set the reference
// to the previous Node of the newNode to temp.
temp.next = newNode;
newNode.prev = temp;
}
remove Method
This method removes an element from the list.
public void remove(int data) {
Node temp = head;
// traverse the same way as in the add method
while (temp != null) {
// As we traverse, we compare the data of
// the of the current Node to the one we
// want to remove to see if we found the
// element
if (temp.data == data) {
// If the temp Node is not the first one,
// we have to make sure that it is
// connected even if we remove an element
// by setting the Node previous of it's
// next field to the Node after temp
if (temp.prev != null) {
temp.prev.next = temp.next;
} else {
// If it is the first element,
// just set head to the next Node
// to remove
head = temp.next;
}
// If the Node is not the last one, then
// set the Node next's prev field to be
// temp's prev
if (temp.next != null) {
temp.next.prev = temp.prev;
}
return;
}
// Traverse the list
temp = temp.next;
}
}
print Method
This method prints all of the data of the list from the beginning to the end
public void print() {
Node temp = head;
// Traverse similarly to the last methods while
// printing the data field of each Node
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
Output should be in the format: 1 12 23 2223
How to use the Doubly Linked List
To use the DoublyLinkedList class, you would create an instance of it. Then, you can call the appropriate functions on it for your needs. Here is example of usage:
LinkedList list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.print(); // Output: 1 2 3
list.delete(2);
list.print(); // Output: 1 3
Full Code
public class LinkedList {
Node head;
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public LinkedList() {
this.head = null;
}
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void delete(int data) {
if (head == null) {
return;
}
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data
!= data) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
public void display() {
if (head == null) {
System.out.println("Linked list is empty.");
} else {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
}
Conclusion
This is just a simple way to implement a doubly linked list in Java. There are many things you can change about this. For example, you could implement a tail reference, which references the end of the list. This way, you can traverse starting from both the end and beginning of the list. You could also choose to make the list ordered, where you would compare each element when it is being added or removed in order to make sure they go in the right place.
When writing methods for linked lists and doubly linked lists, you generally want to traverse the list and perform different operations or comparisons.
Now, you have learned a way to create a fundamental Java data structure that can help you store data in your programs!
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.