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 Lists (often abbreviated as DLL), is very much alike a regular Singly Linked Lists (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 contain 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.

Singly Linked List and Doubly Linked List

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 next node.
  • A variable storing the pointer to the previous node.

With this information in hand, we can now create the ListNode class.

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 backwards through the list.
  • The delete operation is much more efficient.
  • Insertion before a node is also much more efficient.

Now, as always, there’s 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 element at the front of the list.
  • addEnd: Inserting 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.

We’ll now go through each of the methods, one at a time.

Starting of with the simplest one, size(). Simply return the size variable.
While you’re at it, you can also implement isEmpty. Return true if size is 0, otherwise false.

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 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 the new node. Remember to update the previous pointer for the inserted node!

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. New node’s next is current. In other words, we’re inserting between.
  • If the previous node of current is not null, we have to update it’s 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 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 not equals to null, we make current.next.prev point to the new node.
  • Lastly, we update current.next to point to the new node.

The last operation we’ll implement is remove.

  • Check if it is the front node. If so, just make front point to front.next.
  • If current.next not equals to null (i.e. not the last node), make current.next.prev point to current.prev.
  • Make current.prev.next point to current.next

The entire complete class can be found beneath, including JUnit tests!

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *