Doubly Linked-Lists

The Problem With SLList

• The AddLast procedure that we have for an SLList is much too slow.
  • The entire list must be traversed before an element is inserted at the end.
• We could try to create a reference last that points to the last element in a DLList

public class DLList {
    private static class IntNode {
        int item;
        IntNode next;
        public IntNode(int x, IntNode n) {
            item = x;
            next = n;
        }
    }

    private IntNode sentinel;
    private IntNode last;
    private int size;  

    ...

    public void addLast(int x){
        last.next = new IntNode(x, null);
        last = last.next;
        size+=1;
    }

}

• However, such a design is inflexible, because if we wanted to implement a removeLast, we would have no reference to the second to last object in our list.
  • If we were the create a reference to the second to last object, then we also need a reference to the third to last, fourth, to last, and so on, because when last is removed, all those references need to be updated too.
• A more flexible method of improving this system is to add a previous pointer to each IntNode

public class IntNode {
    public IntNode prev;
    public int item;
    public IntNode next;
}

• This now obeys the structure of a doubly linked list, where each node has a 2 references.
• The problem with this is that sometimes the last node might be referencing the sentinel node if we have an empty linked list.
  • There are two methods to address this issue.
  • Add a second sentinel node to the back of the list.
  • Have a circular sentinel node.

public class DLList {
    private static class IntNode {
        public int item;
        public IntNode next;
        public IntNode prev;
    
        public IntNode(int i, IntNode p, IntNode n) {
            item = i;
            next = n;
            prev = p;
        }
    }

    private IntNode sentinel;
    private int size;

    public DLList(int x) {
        sentinel = new IntNode(1337, null, null);
        IntNode newNode = new IntNode(x, sentinel, sentinel);
        sentinel.prev = newNode;
        sentinel.next = newNode;
        size = 1;
    }

    public DLList() {
        sentinel = new IntNode(1337, null, null);
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
        size = 0;
    }

    public void addFirst(int x) {
        IntNode temp = sentinel.next;
        IntNode newNode = new IntNode(x, sentinel, sentinel.next);
        temp.prev = newNode;
        sentinel.next= newNode;
        size+=1;
    }

    public int getFirst() {
        return sentinel.next.item;
    }

    public int get(int i) {
        if (i >= size) {
            throw new IndexOutOfBoundsException("Index " + i + " is out of bounds for DLList with size " + size + ".");
        }
        IntNode dummy = sentinel.next;
        while (i > 0) {
            dummy = dummy.next;
            i--;
        }
        return dummy.item;
    }

    public void addLast(int x) {
        IntNode temp = sentinel.prev;
        IntNode newNode = new IntNode(x, sentinel.prev, sentinel);
        temp.next = newNode;
        sentinel.prev = newNode;
        size+=1;
    }

    public int getLast() {
        return sentinel.prev.item;
    }

    public void removeLast() {
        if (size == 0) {
            throw new IllegalStateException("List is empty");
        }
        sentinel.prev.prev.next = sentinel;
        sentinel.prev=sentinel.prev.prev;
        size-=1;
    } 

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "["+toStringHelper()+"]";
    }

    private String toStringHelper() {
        IntNode dummy = sentinel.next;
        StringBuilder res = new StringBuilder();
        while (dummy != sentinel) { 
            res.append(dummy.item);
            dummy = dummy.next;
            if (dummy != sentinel) {
                res.append(", ");
            }
        }
        return res.toString();
    }
}

DLList L = new DLList(1);
L.addFirst(2);
L.addLast(3);
L;

[2, 1, 3]

Generic DLLists

• Right now, the DLList can only hold integer values, and nothing else.
  • Java has a generics system, which allows us to create a placeholder type for a class that is filled in when an object is instantiated.

public class DLList<T> {
    public class Node {
        public T item;
        public Node next;
        public Node prev;
    
        public Node(T i, Node p, Node n) {
            item = i;
            next = n;
            prev = p;
        }
    }

    private Node sentinel;
    private int size;

    public DLList(T x) {
        sentinel = new Node(null, null, null);
        Node newNode = new Node(x, sentinel, sentinel);
        sentinel.prev = newNode;
        sentinel.next = newNode;
        size = 1;
    }

    public DLList() {
        sentinel = new Node(null, null, null);
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
        size = 0;
    }

    public void addFirst(T x) {
        Node temp = sentinel.next;
        Node newNode = new Node(x, sentinel, sentinel.next);
        temp.prev = newNode;
        sentinel.next= newNode;
        size+=1;
    }

    public T getFirst() {
        return sentinel.next.item;
    }

    public T get(int i) {
        if (i >= size) {
            throw new IndexOutOfBoundsException("Index " + i + " is out of bounds for DLList with size " + size + ".");
        }
        Node dummy = sentinel.next;
        while (i > 0) {
            dummy = dummy.next;
            i--;
        }
        return dummy.item;
    }

    public void addLast(T x) {
        Node temp = sentinel.prev;
        Node newNode = new Node(x, sentinel.prev, sentinel);
        temp.next = newNode;
        sentinel.prev = newNode;
        size+=1;
    }

    public T getLast() {
        return sentinel.prev.item;
    }

    public void removeLast() {
        if (size == 0) {
            throw new IllegalStateException("List is empty");
        }
        sentinel.prev.prev.next = sentinel;
        sentinel.prev=sentinel.prev.prev;
        size-=1;
    } 

    public void removeFirst() {
        if (size == 0) {
            throw new IllegalStateException("List is empty");
        }
        sentinel.next.next.prev = sentinel;
        sentinel.next=sentinel.next.next;
        size-=1;
    } 

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "["+toStringHelper()+"]";
    }

    private String toStringHelper() {
        Node dummy = sentinel.next;
        StringBuilder res = new StringBuilder();
        while (dummy != sentinel) { 
            res.append(dummy.item);
            dummy = dummy.next;
            if (dummy != sentinel) {
                res.append(", ");
            }
        }
        return res.toString();
    }
}

DLList<String> L = new DLList<>("love");
L.addFirst("I");
L.addLast("Michelle");
L;

[I, love, Michelle]

• Generics do not work with primitives, so we must use reference types of the primitives.
• Rules about generics
  • In the .java file implementing a data structure, only define the generic type once at the very top of the flie after the class name.
  • When using the data structure, specify the desired type using the diamond operator during declaration, and an empty diamond operator during instantiation.
  • When using primitives, use the reference type of the primitive to instantiate a generic over a primitive type.