Java Data Structures and Algorithms. Doubly Linked List

Introduction

• This series is going to be dedicated to learning and understanding data structures and algorithms in Java. All the information I am using is coming from the book, Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia and the California State Polytechnic University course, which is free and can be found HERE, shout out professor Tang. Please do not buy the book it is expensive and can be found online for MUCH cheaper.

YouTube version:

• YouTube version of this code can be found HERE

GitHub code

• GitHub for the code can be found HERE

What is a doubly linked List?

• In a singly linked list, each node maintains a reference to the node that is immediately after it. A doubly linked list does that as well. However, it has an additional reference to node previous to it. Hence the name doubly because a node holds two references, one to the node ahead of it and one to the node behind it.

Header and Trailer sentinel nodes.

• In order to avoid some special cases when operating near the boundaries of a doubly linked list. It helps to add special sentinel nodes at both ends of the list. These sentinel nodes do not store any elements from the primary linked list and the do not count towards the size of the list.

Why use sentinel nodes ?

• While we certainly could implement a doubly linked list without any sentinel nodes(like a singly linked list), the extra memory we use on the sentinel nodes greatly simplifies the logic of our operations on the list. The header and the trailer never change, only the nodes between them do. This means that we can treat all insertions in a uniform manner and all deletions in a uniform manner.

Creating the Node

• This Node has 3 instance variables:

1) element : is a reference to the element stored at this node
2) previous : reference to the previous node
3) next : reference to the next node

• With the node class we are going to use generics to give our class a little bit of flexibility. Once we have the 3 instance variables all we have to do is create a POJO(Plain Old Java Object), so to finish things, just create the constructor and the getters and the setters.

  public class DoublyLinkedList <E>{
    private static class Node<E>{
        private E element;
        private Node<E> previous;
        private Node<E> next;

        public Node(E element, Node<E> previous, Node<E> next) {
            this.element = element;
            this.previous = previous;
            this.next = next;
        }
        //GETTERS
        public E getElement() {
            return this.element;
        }
        public Node<E> getPrevious(){
            return this.previous;
        }
        public Node<E> getNext(){
            return this.next;
        }
        //SETTERS
        public void setNext(Node<E> next) {
            this.next = next;
        }
        public void setPrevious(Node<E> previous) {
            this.previous = previous;
        }

    }
   }

Instance variables

• Once we have created the Node class, the next thing to do is to implement the instance variables. This class will hold 3 instance variables. 1) header : holds a reference to the header sentinel node 2) trailer : holds a reference to the trailer sentinel node 3) size: holds an integer value indicating how many nodes are in the list

 public class DoublyLinkedList <E>{
// The rest of the node class is above.

        private Node<E> header;
    private Node<E> trailer;
    private int size =0;


}

Doubly linked list constructor

• The constructor of a doubly linked list is important because we use it to set up the header and trailer sentinel nodes. just a friendly reminder, but these two sentinel nodes help simplify our code and make our operations more efficient. First we create the header and everything is null. Then we set the trailer will is previous reference set to the header. Lastly we set the header's next reference to the trailer. So upon constructing our doubly linked list, we will create something like this:
• With the header and trailer being the sentinel nodes

public DoublyLinkedList(){
        header = new Node<>(null,null,null);
        trailer = new Node<>(null,header,null);
        header.setNext(trailer);
    }

Doubly Linked List methods

• The doubly linked list that we are going to implement today has 8 methods(technically 10 but we will talk about the other two later) and they are:

1) size() : returns the number of elements in the list

2) isEmpty() : returns true if the list is empty and false otherwise

3) first() : returns(but does not remove) the first element in the list

4) last() : returns(but does not remove) the last element in the list.

5) addFirst(e) : adds a new element to the front of the list.

6) addLast(e) : adds a new element to the end of the list.

7) removeFirst() : removes and returns the first element of the list.

8) removeLast() : removes and returns the last element of the list.

• The use of our sentinel nodes will impact the implementation in several ways. First we will create and link the sentinels upon constructing an empty list. We should also keep in mind that the first element of a nonempty list is stored in the node just after the header and not the header itself. Also, the last element is stored in the node just before the trailer.
• We will also be creating a two private methods to deal with general deletions and insertions to the list:

1) addBetween() : handles general cases of insertions and will be called by addFirst() and addLast()

2) remove() : handles general cases of removals and will be called by removeFirst() and removeLast()

• Before we start implementing the rest of the class, I want to make it incredibly clear that the sentinel nodes are not the head or the tail. They represent end points that hold no values of their own. They act as easy markers and simplify our code.

Implementing the retrieval methods

• The first four methods that we are going to implement are pretty straight forward, we are implementing, size(), isEmpty(), first() and last(). They are the methods that do not operate on the list, instead they only retrieve values for us.

 public class DoublyLinkedList <E>{
// The rest of the class is above.

        public int size() {
        return this.size;
    }
    public boolean isEmpty() {
        return size == 0;
    }

public E first() {
        if (isEmpty()) {
            return null;
        }else {
            return header.getNext().getElement();
        }
    }
    public E last() {
        if(isEmpty()) {
            return null;
        }else {
            return this.trailer.getPrevious().getElement();
        }
    }

}

Implementing the update methods

• The next four methods are for removing and adding nodes to the list. They are, addFirst(), addLast(), removeLast(), removeFirst() and those are the public methods. However, there are also two more private methods, called addBetween() and remove() that are to be called by the other four methods. IN these two private methods we implement the logic for adding/removing from the list.

public void addFirst(E e) {
        addBetween(e,header,header.getNext());
    }
    public void addLast(E e) {
        addBetween(e,trailer.getPrevious(),trailer);
    }
public E removeFirst() {
        if(isEmpty()) {
            return null;
        }else {
            return remove(header.getNext());
        }
    }
    public E removeLast() {
        if(isEmpty()) {
            return null;
        }else {
            return remove(trailer.getPrevious());
        }
    }

• most of the logic goes inside the remove() and the addBetween() methods.

private void addBetween(E e,Node<E> predecessor, Node<E> successor) {
        Node<E> newest = new Node<>(e,predecessor,successor);
        predecessor.setNext(newest);
        successor.setPrevious(newest);
        size++;
    }

• With the method above all we are really doing is creating a Node and then setting up its next and previous reference values.

private E remove(Node<E> node) {
        Node<E> predecessor = node.getPrevious();
        Node<E> successor = node.getNext();

        predecessor.setNext(successor);
        successor.setPrevious(predecessor);

        size--;
        return node.getElement();
    }

• The remove logic is a little more complicated and I only say that because of the nature of Java. When we are removing a node, what we are actually doing is simply making sure that no other nodes reference it. In Java, when an object has no other object that reference it, it gets removed and its memory is returned back to the memory pool. So the removal of a Node looks something like this:

Conclusion

• Thank you for taking the time out of your day to read this blog post of mine. If you have any questions or concerns please comment below or reach out to me on Twitter.