/******************************************************************************
* Name:
* NetID:
* Precept:
*
* PList - Popularity List: Linked List Version
* list where the most recently accessed or added entry
* is always on top.
*
* Dependencies: Entry, StdOut
*****************************************************************************/
public class PList {
// instance variables
private Node top; // top of the list
// inner class
private class Node {
private Entry en; // Entry holds name and number
private Node next; // next entry on the list
}
// do-nothing constructor
public PList() {
top = null;
}
// add entry to top of list
public void add(String name, String num) {
// construct the Entry, pack it in a Node
Entry newEntry = new Entry(name, num);
Node newNode = new Node();
newNode.en = newEntry;
// insert at top of list (point to old top, become new top)
newNode.next = top;
top = newNode;
}
// output the list
public void show() {
if (top == null) {
StdOut.println("empty PList");
return;
}
// not empty, output the list, t travels the list
for (Node t = top; t != null; t = t.next) {
StdOut.println(t.en);
}
}
// move entry with name to top of list, return number
// return null if not there
public String find(String name) {
// special case for empty list
if (top == null) return null;
// special case for top entry (no moving needed)
if (top.en.equals(name)) return top.en.getNum();
// find your entry, keep track of previous node
for (Node prev = top; prev.next != null; prev = prev.next) {
Node current = prev.next;
if (current.en.equals(name)) {
// remove from current position
prev.next = current.next;
// move to top
current.next = top;
top = current;
//return number
return current.en.getNum();
}
}
// if you get to here, entry not found
return null;
}
//remove and return Entry from list
public Entry cut(String name) {
// use find() to move Entry to top of list
String found = find(name);
if (found == null)
throw new RuntimeException(name + "not found");
// return Entry after you remove it from list
Entry toBeCut = top.en;
top = top.next;
return toBeCut;
}
// update num or add entry to list
public void update(String name, String num) {
// Is it already on list?
String found = find(name);
if (found != null) {
// if there, cut it
cut(name);
}
// either way, add new version
add(name, num);
return;
}
// test main
public static void main(String[] args) {
PList list = new PList();
list.add("Doug", "6092586314");
list.add("Donna", "6092581978");
list.add("Christopher", "6092585388");
list.add("Maia", "6092586484");
list.add("Chris", "6092582038");
StdOut.println("Entire list:");
list.show();
StdOut.println("===========================");
list.update("Maia", "6092588888");
list.cut("Chris");
StdOut.println("Doug " + list.find("Doug"));
StdOut.println("Maria " + list.find("Maria"));
StdOut.println("===========================");
StdOut.println("Updated list:");
list.show();
}
}