CSC152 2006S, Class 43: Lists (3): Linked Lists Admin: * Homework 15: Sorted Lists. * EC for attending Lindsay's Paper+Dance thing tomorrow at 11:00. IN SPITE OF THE FACT THAT IT'S IN CONFLICT WITH CONVO * Different tecnique today: Acting out operations Overview: * List operations * Implementing lists with nodes. * Simple List Operations * V get(Postition pos) * add(V value) * removeAll() * isEmpty() * remove(Position pos) * Position predecessor(Position pos) * Position successor(Position pos) * Position first() * Position last() * boolean isFirst(Position pos) * boolean isLast(Position pos) * Fields in Node (implements Position) * The thing: V val; (1) * A hook to the next thing: Node next; (2) * Fields in NodeBasedList * Node front; public class LinkedSimpleList implements SimpleList { Node front; Node back; public Position first() { return this.front; } public Position last() { /* // Slow strategy Node tmp = this.front; while (tmp.next != null) { tmp = tmp.next; } return tmp; */ // Fast strategy return this.back; } public V get(Position pos) { return ((Node) pos).val; } public void add(V val) { // Make a new node, tmp, that contains val Node tmp = new Node(val); // Abnormal case: List is empty if (this.isEmpty()) { this.front = tmp; this.back = tmp; } // Normal case: List is not empty else { // Make tmp the next node of back this.back.next = tmp; // Make back tmp this.back = tmp; } } public void removeAll() { // Set the front and the end of the list to null this.front = null; this.end = null; } // removeAll public boolean isFirst(Position pos) { return this.front == pos; } public boolean isLast(Position pos) { return ((Node) pos).next != null; } public void remove(Position pos) { // Special case if (this.front == pos) { this.front = this.front.next; if (this.front = null) { this.back = null; } } // General case else { Node tmp = ((Node) pos).next; Node pred = this.front; while (pred.next != pos) { pred = pred.next; } if (this.back == pos) { this.back = pred; } pred.next = tmp; } } } * Some problems we noticed: * Removal is inefficient, because we have to search the whole list * Tons of special cases * Making removal more efficient * Update the Node class so that it has a prev field * Every time we set a next, we need to set a previous (unless, of course, the next node is null) * Solving the "special case problem" * All lists contain a special node, whose next element is the first element and whose prev element is the last element.