Slide 1Storing a sequence of recordsStoring a sequence of recordsA new data structure: Linked ListsInserting and DeletingReference in JavaLinked ListstoString for the ListItem classTraversing a ListImplementing a LinkedIntList ClassAdding ElementsFinding and Removing Items in a ListInterfaceImplementing IntList InterfaceDoubly Linked ListsDoubly Linked Lists and SentinelsCSE 131 Computer Science 1Module 9: Linked ListsUsing references to link objectsBasic operations on linked listsImplementing a linked list of integers2Storing a sequence of recordsOftentimes, we need to store a sequence of data records. E.g.:»The list of students: ID, names, grades, etc.»All the emails, sorted by arrival time»Finishing times of marathon runners»Bank transactions3Storing a sequence of recordsNeed to support these operations»get the i-th record»delete the i-th record, »insert a record to the i-th placeUsing an array to store such data records.»Pros and cons?»Fast random access (get the i-th record)»Slow insert/delete»Need to know the maximum size beforehand •Overflow risk vs. waste of storage4A new data structure:Linked ListsList of integers: [ 2 3 5 2 16 4 ]Key differences to array?»Array: random access (directly goes to i-th record)»List: sequential access (follows the references)2 3 5 2 16 45Inserting and DeletingInserting a recordRemoving a record2 3 5 2 16 4 16 2 3 5 4 7 26Reference in JavaA must read: http://stackoverflow.com/questions/40480/is-java-pass-by-referenceStudy all the examples there!7Linked ListsList of integers: [ 2 3 5 2 16 4 ]public class ListItem{ public int number; public ListItem next; public ListItem(int value, ListItem p){number = value; next = p;}}Building lists with the constructor»ListItem p = new ListItem(3,null);»ListItem q = new ListItem(7,p);»ListItem r = new ListItem(2,new ListItem(5,null));»What happens when q=p;? when ListItem d = r.next; ?2 3 5 2 16 4 p3 7 qr2 58toString for the ListItem classpublic class ListItem{ public int number; public ListItem next; public ListItem(int value, ListItem p){number = value; next = p;} public String toString() { if (next == null) return number + “ “; else return number + “ “ + next.toString(); }}9Traversing a ListPass over list by advancing object referenceTask: get the sum of all ListItem values reachable from a ListItem p2 3 5 2 16 4 p// recursive traversalint sum(ListItem p) {if (p == null) return 0;else return p.number + sum(p.next);}// iterative traversalint sum(ListItem p) {int result = 0;while (p != null) {result += p.number;p = p.next;}return result;}10Implementing a LinkedIntList ClassList of integer values with the following operations»addFirst(int x) – add the value x at the front of the list•insert new ListItem before current head»addLast(int x) – add the value x at the end of the list•add new ListItem after last item»indexOf(int x) – return the index of first item with value x•scan the list for first match»remove(int x) – delete the first item with value x•scan to the first item and re-direct previous item’s next pointer»size() – return the number of elements in the list•uses a stored valueTwo instance variables»ListItem head – reference to first ListItem (or null)»int size – number of items in the list11Adding Elements// Create new list item and insert before current first elementvoid addFirst(int x) {head = new ListItem(x, head);size++;}// Create new list item and insert it at the end of the listvoid addLast(int x) {if (head == null) { addFirst(x);} else {// scan to end of list, then insert itemListItem p;for (p = head; p.next != null; p = p.next) {}p.next = new ListItem(x,null);size++;}12Finding and Removing Items in a List // Return index of first item with value x (or -1 if none)int indexOf(int x) {int i = 0;for (ListItem p = head; p != null; p = p.next) {if (p.number == x) return i;i++;}return -1;}// Remove first item with given value void remove(int x) {if (head == null) return;if (head.number == x) { head = head.next; size--; return; }for (ListItem p = head; p.next != null; p = p.next) {if (p.next.number == x) {p.next = p.next.next; size--; return;}} }13InterfaceInterface: a more abstract concept than class»Only defines the method signatures»Doesn’t have: data values, method definition Example: an interface for a list of integerspublic interface IntList {void addFirst(int item); // add item at the headint indexOf(int item); // find location of itemint size(); // # of items in list}Cannot create an object of an interface IntList a = new IntList(); // compilation errorTo use an interface, must first create a class that implements the interface14Implementing IntList InterfaceUsing a fixed array of storage locationspublic class ArrayIntList implements IntList { void addFirst(int item){..}// add by shifting itemsint indexOf(int item){..} int size(){..} // return stored size value... // instance variables, constructor and maybe more}Using a linked set of “nodes”public class LinkedIntList implements IntList { void addFirst(int item){..} // add by adjusting linksint indexOf(int item){..} // follow links and countint size(){..} // ditto...}Using interfaceArrayIntList x = new ArrayIntList();IntList y = new LinkedIntList(); // not new IntList()15Doubly Linked ListsLists with forward and reverse links »public class ListItem{ public int number; public ListItem next;public ListItem prev;}»makes it easy to traverse a list in reverse (by following p.prev)»makes it easier to delete arbitrary elements (e.g. delete the previous item)2 3 5 2 16 4 headsize=6tail16Doubly Linked Lists and SentinelsLists are sometimes implemented with sentinel nodes at the beginning and end »makes implementation more symmetric»reduces number of special cases in methods»list object includes references to both head and tail nodes»explore it in your studio tomorrow 2 3 5 2 16 4 - -