teaching machines

CS 245 Lecture 18 – Dummy Nodes and Iterators

November 5, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

Agenda

• what ?s
• the importance of linked list
• the tradeoff: simplicity vs. performance
• switching linked list to use dummy nodes
• program this: prepend
• supporting fast iteration
• exams back

Program This

Code

LinkedList.java

package lecture18;

import java.util.NoSuchElementException;

public class LinkedList<T> {
  private Node<T> head;
  private Node<T> tail;
  private int nItems;

  public LinkedList() {
    head = new Node<T>(null, null, null);
    tail = new Node<T>(null, null, null);
    head.next = tail;
    tail.previous = head;
    nItems = 0;
  }

  public void add(T itemToAdd) {
    Node<T> nodeToAdd = new Node<T>(itemToAdd, tail, tail.previous);
    nodeToAdd.previous.next = nodeToAdd;
    tail.previous = nodeToAdd;
    ++nItems;
  }
  
  public void prepend(T itemToAdd) {
    Node<T> nodeToAdd = new Node<T>(itemToAdd, head.next, head);
    nodeToAdd.previous.next = nodeToAdd;
    head.next = nodeToAdd;
    ++nItems;
  }
  
  public boolean isEmpty() {
     return nItems == 0;
  }

  public int size() {
    return nItems;
  }
  
  public T getLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    
    return tail.previous.item;
  }
  
  public T removeFirst() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    
    Node<T> nodeToChopOff = head.next;
    head.next = nodeToChopOff.next;
    nodeToChopOff.next.previous = head;
    
    --nItems;
    
    return nodeToChopOff.item;
  }
  
  public T removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    
    Node<T> nodeToChopOff = tail.previous;
    tail.previous = nodeToChopOff.previous;
    nodeToChopOff.previous.next = tail;
    
    --nItems;
    
    return nodeToChopOff.item;
  }
  
  public T getFirst() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    
    return head.next.item;
  }
  
  public T get(int i) {
    int iCurrent = 0;
    for (Node<T> current = head.next; current != tail; current = current.next) {
      if (iCurrent == i) {
        return current.item;
      }
      ++iCurrent;
    }
    
    throw new IndexOutOfBoundsException();
  }

  private static class Node<T> {
    private T item;
    private Node<T> next;
    private Node<T> previous;

    public Node(T item,
                Node<T> next,
                Node<T> previous) {
      this.item = item;
      this.next = next;
      this.previous = previous;
    }
  }
}

Main.java

package lecture18;

public class Main {
  public static void main(String[] args) {
    LinkedList<String> names = new LinkedList<String>();
    
//    System.out.println(names.size());
    names.add("Stephen");
//    System.out.println(names.size());

    names.add("Justin");
    names.add("Alan");
    names.prepend("Mike");
    
    System.out.println(names.get(0));
    System.out.println(names.get(1));
    System.out.println(names.get(2));
    System.out.println(names.get(3));
//    System.out.println(names.get(4));
    
    System.out.println(names.size());
//    System.out.println(names.get(4));

    System.out.println();
    
    names.removeFirst();
    names.removeLast();
    for (int i = 0; i < names.size(); ++i) {
      System.out.println(names.get(i));
    }
  }
}

JavaLinkedListFun.java

package lecture18;

import java.util.LinkedList;
import java.util.ListIterator;

public class JavaLinkedListFun {
  public static void main(String[] args) {
    LinkedList<String> tourStops = new LinkedList<String>();
    
    tourStops.add("New Orleans");
    tourStops.add("Salt Lake City");
    tourStops.add("Kabul");
    tourStops.add("Yellowknife");
    
    ListIterator<String> i = tourStops.listIterator();
    while (i.hasNext()) {
      String stop = i.next();
      System.out.println(stop);
      
      if (stop.equals("Salt Lake City")) {
        i.add("Chicago");
      }
    }
    
    System.out.println(tourStops.getFirst());
    System.out.println(tourStops.getLast());
    
    tourStops.removeLast();
    
    System.out.println(tourStops);
    
//    for (String stop : tourStops) {
//      System.out.println(stop);
//    }
  }
}

Haiku