CS 245 Lecture 18 – Dummy Nodes and Iterators
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
Write LinkedList.prepend, which is like add, but inserts the item at the beginning of the list.
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
silver bullets
Like wooden stakes best?
Good luck when werewolves attack
Don’t play favorites
Like wooden stakes best?
Good luck when werewolves attack
Don’t play favorites