How to Implement Doubly Linked List in Java
In this article, we'll have a look at a data structure known as a doubly linked list. If you're unfamiliar with linked lists, I highly recommend that you check out this tutorial on linked lists before proceeding.
A doubly linked list (often abbreviated as DLL) is very much like a regular singly linked list (SLL).
Both DLL and SLL contain a pointer to the next node, as well as a data field to represent the actual value stored in the node.
However, the difference between DLL and SLL is that the doubly linked list also contains a pointer to the previous node, not just the next node.
Unlike nodes in a singly linked list, nodes in a doubly linked list are aware of both the next and the previous node.
The difference between DLL and SLL is visualized in the picture below.
We now know that a node in a doubly linked list must contain three variables:
- A variable containing the actual data.
- A variable storing the pointer to the nextnode.
- A variable storing the pointer to the previousnode.
With this information in hand, we can now create the ListNode class.
package DoublyLinkedList; /** * This class represents a node in a Doubly Linked List. * The next-variable is a pointer to the next node, * and the prev-variable is a pointer to the previous node. * <p> * * @author Anders Engen Olsen * @see DoublyLinkedList */ class ListNode<AnyType> { // The actual data AnyType data; // Reference to the next node ListNode<AnyType> next; // Reference to the prev node ListNode<AnyType> prev; /** * Constructor. * Note that the next and prev variables are set to null, thus this is the "root-node" * * @param data node data */ ListNode(AnyType data) { this(null, data, null); } /** * Constructor. * * @param data node data * @param next reference to next node * @param prev reference to the previous node */ ListNode(ListNode<AnyType> prev, AnyType data, ListNode<AnyType> next) { this.data = data; this.next = next; this.prev = prev; } } Okay, we've now made a ListNode, which has a pointer to both the previous and the next node. But why? What are the advantages of a doubly linked list?
- With a doubly linked list, we can iterate both forwards and backward through the list.
- The delete operation is much more efficient.
- Insertion before a node is also much more efficient.
Now, as always, there are also some drawbacks:
- Nodes in a DLL have pointers to both the previous and the next node. This requires more memory space.
- For every operation, we'll have to update both the previous and the next pointer. More work, basically.
Let's get started with the actual linked list. The methods we'll support in our implementation is as follows:
addFront:Inserting an element at the front of the list.addEnd:Inserting an element at the end of the list.remove:Removing given element from the list.addBefore:Inserting before given element.addAfter:Inserting after given element.isEmpty: Checking whether the list is empty.size:Returning number of elements in the list.
Note that our example won't allow for duplicates!
Below is a skeleton of our DoublyLinkedList class.
package DoublyLinkedList; public class DoublyLinkedList<AnyType> { // Front / head node private ListNode<AnyType> front; // Helper, keeping track of size. private int size; /** * Constructing empty list. */ public DoublyLinkedList() { front = null; size = modificationCount = 0; } public void addFront(AnyType x) { } public void addEnd(AnyType x) { } public void addBefore(AnyType x, AnyType y) { } public void addAfter(AnyType x, AnyType y) { } public void remove(AnyType x) { } public boolean isEmpty() { } public int size() { } } We'll now go through each of the methods, one at a time.
Tip:Check out our review of the best online Java courses!
Starting with the simplest one, size() , simply return the size variable. While you're at it, you can also implementisEmpty .Return true if size is 0; otherwise, it is false.
public boolean isEmpty() { return size == 0; } public int size() { return size; } Let's move on to the method addFront .There are two separate scenarios we'll have to deal with:
- Empty list: Simply initiate the front variable as a new
ListNode. - Non-empty list: Store the current front node in a temp variable. The new front.next will point to the previous front.
/** * Adding a node to the front of the list. * * @param x Value to add */ public void addFront(AnyType x) { if (isEmpty()) front = new ListNode<AnyType>(x); else { ListNode<AnyType> temp = front; front = new ListNode<AnyType>(null, x, temp); front.next.prev = front; } size++; } Adding a node to the end of the list is somewhat similar. The two scenarios are the same:
- Empty list: Simply initiate the front variable as a new
ListNode. - Non-empty list: Traverse the list until the end. Make the last-node.next point the new node. Remember to update the previous pointer for the inserted node!
/** * Inserting a node at the end of the list. * * @param x Value to add. */ public void addEnd(AnyType x) { if (isEmpty()) front = new ListNode<AnyType>(x); else { ListNode<AnyType> temp = front; // Traverse till end of list while (temp.next != null) { temp = temp.next; } temp.next = new ListNode<AnyType>(temp, x, null); } size++; } Adding before a node is a little bit trickier. First, we loop through the list. If we reach null,the value is not found, and an exception is thrown.
Otherwise, we create a new node:
- The new node's previous will be current.previous. The new node's next is current. In other words, we're inserting between the two.
- If the previous node of current is not null, we have to update its next pointer.
- If current.previous is null, we're at the front. Simply update front to the new node.
- Lastly, we'll have to update current.previous to point to the new node.
/** * Adding node before another node * * @param x Value to look for, adding before x if found * @param y Value to add. */ public void addBefore(AnyType x, AnyType y) { // List is empty, can't add if (isEmpty()) throw new NoSuchElementException("Element " + x.toString() + " not found"); ListNode<AnyType> current = front; // Looping through until found while (current != null && !current.data.equals(x)) current = current.next; // If null, not found if (current == null) throw new NoSuchElementException("Element " + x.toString() + " not found"); ListNode<AnyType> newNode = new ListNode<AnyType>(current.prev, y, current); if (current.prev != null) current.prev.next = newNode; else front = newNode; current.prev = newNode; size++; } Adding a node after another is very similar to adding before.
- Create a new node. Make new node's previous pointer point to current. The next pointer for the new node will be current.next.
- If current.next is not equaled to null, we make current.next.prev point to the new node.
- Lastly, we update the current.next to point to the new node.
/** * Adding node after another node * * @param x Value to look for, adding after x if found * @param y Value to add. */ public void addAfter(AnyType x, AnyType y) { if (isEmpty()) throw new NoSuchElementException("Element " + x.toString() + " not found"); ListNode<AnyType> current = front; // Looping through until found while (current != null && !current.data.equals(x)) current = current.next; // If null, not found if (current == null) throw new NoSuchElementException("Element " + x.toString() + " not found"); // Not null, value found ListNode<AnyType> newNode = new ListNode<AnyType>(current, y, current.next); if (current.next != null) current.next.prev = newNode; current.next = newNode; size++; } The last operation we'll implement is remove .
- Check if it is the front node. If so, just make the front point to front.next.
- If current.next is not equaled to null (i.e. not the last node), make current.next.prev point to current.prev.
- Make current.prev.next point to current.next
/** * Removing a Node from the list. * * @param x Value to remove */ public void remove(AnyType x) { if (isEmpty()) throw new NoSuchElementException("Element " + x.toString() + " not found"); // Removing front element if (front.data.equals(x)) { front = front.next; return; } ListNode<AnyType> current = front; // Looping through until found while (current != null && !current.data.equals(x)) current = current.next; // If null, not found if (current == null) throw new NoSuchElementException("Element " + x.toString() + " not found"); // It has a next pointer, so not the last node. if (current.next != null) current.next.prev = current.prev; current.prev.next = current.next; size--; } The entire complete class can be found beneath, including JUnit tests!
package DoublyLinkedList; /** * This class represents a node in a Doubly Linked List. * The next-variable is a pointer to the next node, * and the prev-variable is a pointer to the previous node. * <p> * * @author Anders Engen Olsen * @see DoublyLinkedList */ public class ListNode<AnyType> { // The actual data AnyType data; // Reference to the next node ListNode<AnyType> next; // Reference to the prev node ListNode<AnyType> prev; /** * Constructor. * Note that the next and prev variables are set to null, thus this is the "root-node" * * @param data node data */ ListNode(AnyType data) { this(null, data, null); } /** * Constructor. * * @param data node data * @param next reference to next node * @param prev reference to the previous node */ ListNode(ListNode<AnyType> prev, AnyType data, ListNode<AnyType> next) { this.data = data; this.next = next; this.prev = prev; } } package DoublyLinkedList; import java.util.NoSuchElementException; public class DoublyLinkedList<AnyType> { // Front / head node private ListNode<AnyType> front; // Helper, keeping track of size. private int size; /** * Constructing empty list. */ public DoublyLinkedList() { front = null; } /** * Adding a node to the front of the list. * * @param x Value to add */ public void addFront(AnyType x) { if (isEmpty()) front = new ListNode<AnyType>(x); else { ListNode<AnyType> temp = front; front = new ListNode<AnyType>(null, x, temp); front.next.prev = front; } size++; } /** * Inserting a node at the end of the list. * * @param x Value to add. */ public void addEnd(AnyType x) { if (isEmpty()) front = new ListNode<AnyType>(x); else { ListNode<AnyType> temp = front; // Traverse till end of list while (temp.next != null) { temp = temp.next; } temp.next = new ListNode<AnyType>(temp, x, null); } size++; } /** * Adding node before another node * * @param x Value to look for, adding before x if found * @param y Value to add. */ public void addBefore(AnyType x, AnyType y) { // List is empty, can't add if (isEmpty()) throw new NoSuchElementException("Element " + x.toString() + " not found"); ListNode<AnyType> current = front; // Looping through until found while (current != null && !current.data.equals(x)) current = current.next; // If null, not found if (current == null) throw new NoSuchElementException("Element " + x.toString() + " not found"); ListNode<AnyType> newNode = new ListNode<AnyType>(current.prev, y, current); if (current.prev != null) current.prev.next = newNode; else front = newNode; current.prev = newNode; size++; } /** * Adding node after another node * * @param x Value to look for, adding after x if found * @param y Value to add. */ public void addAfter(AnyType x, AnyType y) { if (isEmpty()) throw new NoSuchElementException("Element " + x.toString() + " not found"); ListNode<AnyType> current = front; // Looping through until found while (current != null && !current.data.equals(x)) current = current.next; // If null, not found if (current == null) throw new NoSuchElementException("Element " + x.toString() + " not found"); // Not null, value found ListNode<AnyType> newNode = new ListNode<AnyType>(current, y, current.next); if (current.next != null) current.next.prev = newNode; current.next = newNode; size++; } /** * Removing a Node from the list. * * @param x Value to remove */ public void remove(AnyType x) { if (isEmpty()) throw new NoSuchElementException("Element " + x.toString() + " not found"); // Removing front element if (front.data.equals(x)) { front = front.next; return; } ListNode<AnyType> current = front; // Looping through until found while (current != null && !current.data.equals(x)) current = current.next; // If null, not found if (current == null) throw new NoSuchElementException("Element " + x.toString() + " not found"); // It has a next pointer, so not the last node. if (current.next != null) current.next.prev = current.prev; current.prev.next = current.next; size--; } /** * @return true if list is empty. */ public boolean isEmpty() { return size == 0; } /** * @return size of list */ public int size() { return size; } @Override public String toString() { ListNode<AnyType> temp = front; StringBuilder builder = new StringBuilder("["); while (temp != null) { builder.append(temp.data).append(","); temp = temp.next; } builder.deleteCharAt(builder.length() - 1); builder.append("]"); return builder.toString(); } } import DoublyLinkedList.DoublyLinkedList; import org.junit.Before; import org.junit.Test; import java.util.NoSuchElementException; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue; public class DoublyLinkedListTest { private DoublyLinkedList<Integer> list; @Before public void setUp() { list = new DoublyLinkedList<Integer>(); } @Test public void testIsEmptyReturnsTrue() { assertTrue(list.isEmpty()); } @Test public void testIsEmptySizeIsZero() { assertEquals(0, list.size()); } @Test(expected = NoSuchElementException.class) public void testRemoveNotPresentThrowsException() { list.addFront(1); list.remove(2); } @Test(expected = NoSuchElementException.class) public void testAddBeforeNotFoundThrowsException() { list.addFront(1); list.addBefore(0, 2); } @Test(expected = NoSuchElementException.class) public void testAddAfterNotFoundThrowsException() { list.addFront(1); list.addAfter(0, 2); } /** * Output should be: [4,3,2,1,0] */ @Test public void testInsertAtFront() { for (int i = 0; i < 5; i++) { list.addFront(i); } assertEquals("[4,3,2,1,0]", list.toString()); } /** * Output should be: [0,1,2,3,4] */ @Test public void testInsertAtEnd() { for (int i = 0; i < 5; i++) { list.addEnd(i); } assertEquals("[0,1,2,3,4]", list.toString()); } /** * Output should be: [10,4,3,30,2,1,20,0] */ @Test public void testAddBefore() { for (int i = 0; i < 5; i++) { list.addFront(i); } list.addBefore(4, 10); list.addBefore(0, 20); list.addBefore(2, 30); assertEquals("[10,4,3,30,2,1,20,0]", list.toString()); } /** * Output should be: [0,20,1,2,30,3,4,10] */ @Test public void testAddAfter() { for (int i = 0; i < 5; i++) { list.addEnd(i); } list.addAfter(4, 10); list.addAfter(0, 20); list.addAfter(2, 30); assertEquals("[0,20,1,2,30,3,4,10]", list.toString()); } /** * Output should be: [10,11,12,13,14] */ @Test public void testRemove() { for (int i = 0; i < 15; i++) { list.addEnd(i); } for (int i = 0; i < 10; i++) { list.remove(i); } assertEquals("[10,11,12,13,14]", list.toString()); } } Topics:
java, linked list in java, linked list, linked lists, dll, sll, tutorial, node
How to Implement Doubly Linked List in Java
Source: https://dzone.com/articles/doubly-linked-list-in-java