Outline

• linked lists
• nodes
• linked list implementation
• invariants
• doubly-linked lists

Linked list nodes

• each node has two data fields: an element value, and a reference to the next node
  
• the element value has generic type T (or E -- it must match the type name in the class declaration)
• note that the reference to the next node is a pointer to the next node, and not the next node itself
• a private class is local to the enclosing (parent) class
• private data fields in the private class are accessible to the code in the parent class

Linked list implementation

• the linked list class only really needs one class variable: a reference to the start of the list, conventionally known as the head of the list
• the book also has a size class variable, which can be useful for error checking
• my implementation also keeps a reference to the last node in the linked list

Linked list performance

• in-class exercise: what is the run-time performance of add(E)?
• in-class exercise: what is the run-time performance of add(int, E)?
• in-class exercise: what is the run-time performance of remove(), which removes the head of the linked list?
• in-class exercise: what is the run-time performance of remove(int), which removes an arbitrary element?

Invariants

• There are some relations that must hold between the different class variables
• for example, size must always be the number of nodes in the linked list
• in a linked list of length 1, head == tail
• in a linked list of length 0, both head and tail should be null
• tail should be the node holding the last element of the list: a list traversal beginning at the head of the list should visit the tail node last of all
• these relations must always hold: they never change, that is, they are invariant (invariant is something that never changes)

Methods and Invariants

• every constructor must establish the invariants of the class
• every other method may expect that the invariants are true when the method is called, and
• every method must guarantee that the invariants are still true at the end of the method

Using Invariants

• invariants are useful for reasoning about the program
• some invariants can be checked by the program itself
• if an invariant is ever detected to not be true, the program should provide enough information to track down the bug (and should either crash, or re-establish the invariant)
• in ICS 211, if your classes have any invariants, your code should check them at the beginning and at the end of each public method
• this may help you improve your understanding of your code, and may also help you find bugs
• see also the linked list invariants
• if checking is slow, you may have to remove the invariant checking (e.g., add a return statement at the beginning of the check method) when doing performance testing

Circular Linked Lists

• by convention, the next field of the last node in a linked list has the value null
• a different convention suggests storing the value of head in this field
• then, tail is sufficient, and
• it is not necessary to have the head field:
• head is the same as tail.next, which is a constant-time operation
• a complete traversal of a circular list can begin from any node, not necessarily the head or tail node
• it is easy to (mistakenly) cause list traversals to loop forever

Doubly-Linked Lists

• the linked lists so far have the limitation that it is only possible for code to follow references in one direction in the list, that is, forward
• node removal requires a reference to the node before the node to be removed
• if each node also keeps a reference to the node before it, both these problems can be solved

• the node class is straightforward:

    private class DLinkedNode<E> {
      private E item;
      private DLinkedNode<E> prev;
      private DLinkedNode<E> next;
    
      private DLinkedNode(E value) {
        item = value;
        next = null;
        prev = null;
      }
    
      private DLinkedNode(E value, DLinkedNode<E> prev, DLinkedNode<E> next) {
        item = value;
        this.next = next;
        this.prev = prev;
      }
    }

Doubly-Linked List add

• adding after a given node (node) means updating the previous and next node's next and prev references:

     DLinkedNode followingNode = node.next;
     node.next = new DLinkedNode (value);
     followingNode.prev = node.next;
  

• in-class exercise (alone or with a friend or two): draw the doubly-linked list after each of the lines of the above code
• the above code assumes that there is both a previous and next node
• if not, the code needs special cases
• a circular list, if coded correctly, does not need as many special cases

Doubly-Linked List remove

• removing a given node (node) means updating the node's predecessor's next field, and the node's successor's prev field:

     node.prev.next = node.next;
     node.next.prev = node.prev;
  

• here are the special cases for a linked-list that is not circular:

     if ((node == head) && (head.next == null)) {
       head = null;
     } else {
        if (node.prev != null)
           node.prev.next = node.next;
        if (node.next != null)
           node.next.prev = node.prev;
     }