teaching machines

CS 245 Lecture 20 – Linked List

April 8, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• a linked list
• a linked snake

TODO

• Grab an updated specchecker HW3.
• Stay home Thursday.
• No lab Monday just ‘cuz. You’ve worked hard.

Code

LinkedList.java

package lecture20;

public class LinkedList<T> {
  private Node<T> head;
  private Node<T> tail;
  
  public LinkedList() {
    head = new Node<T>(null, null, null);
    tail = new Node<T>(null, null, null);
    head.next = tail;
    tail.prev = head;
  }
  
  /**
   * Adds the new item at the end of this list.
   * @param newItem The item to add.
   */
  public void prepend(T newItem) {
    Node<T> newNode = new Node<T>(newItem, head.next, head);
    head.next = newNode;
    newNode.next.prev = newNode;
  }
  
  public void append(T newItem) {
    Node<T> newNode = new Node<T>(newItem, tail, tail.prev);
    tail.prev = newNode;
    newNode.prev.next = newNode;
  }
  
  /**
   * Extract and retrieve the head of this list.
   * @return
   */
  public T shift() {
    return null;
  }
  
  public T peek() {
    T value = tail.prev.value;
    return value;
  }
  
  public static class Node<T> {
    private T value;
    private Node<T> next;
    private Node<T> prev;
    
    public Node(T value, Node<T> next, Node<T> prev) {
      this.value = value;
      this.next = next;
      this.prev = prev;
    }
  }
}

Haiku