{small lecturenumber - hepage :} Arrays{small lecturenumber - hepage :} Linked Lists{small lecturenumber - hepage :} Linked Lists{small lecturenumber - hepage :} List elements{small lecturenumber - hepage :} List elements{small lecturenumber - hepage :} Arranging ListItems{small lecturenumber - hepage :} The LinkedList class{small lecturenumber - hepage :} The LinkedList class{small lecturenumber - hepage :} Adding{small lecturenumber - hepage :} Adding{small lecturenumber - hepage :} Adding{small lecturenumber - hepage :} Adding{small lecturenumber - hepage :} Adding{small lecturenumber - hepage :} Exercise{small lecturenumber - hepage :} Adding elements{small lecturenumber - hepage :} Exercise{small lecturenumber - hepage :} Exercise{small lecturenumber - hepage :} Adding elements{small lecturenumber - hepage :} Adding elements by position{small lecturenumber - hepage :} Adding elements by position{small lecturenumber - hepage :} Adding elements by position{small lecturenumber - hepage :} Adding elements by position{small lecturenumber - hepage :} Adding by order{small lecturenumber - hepage :} Adding by order{small lecturenumber - hepage :} Adding by order{small lecturenumber - hepage :} Removing an element{small lecturenumber - hepage :} Removing an element{small lecturenumber - hepage :} ExerciseIntro to Programming IILinked ListsChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p.1/??18-2: Arrays•Previously we talked about using arrays to store sequences ofdata.•Advantages:◦Everything is stored in sequential memory locations.◦Fast lookup of elements.•Disadvantages:◦Hard to resize◦Removing or adding an element in the middle is costly.Department of Computer Science — University of San Francisco – p.2/??18-3: Linked Lists•Linked lists have the opposite advantages and disadvantages•Advantages:◦Easy to insert and remove◦Easy to resize•Disadvantages:◦Elements are not stored sequentially◦Finding the nth element is slower.Department of Computer Science — University of San Francisco – p.3/??18-4: Linked Lists•The general idea:•Each element of the list will “know” who the next element is.•Let’s try this as a class.Department of Computer Science — University of San Francisco – p.4/??18-5: List elements•So how do we do this in Java?•Our Element class needs to have two components:◦The data that we want to store in the list.◦A pointer to the next element in the list.Department of Computer Science — University of San Francisco – p.5/??18-6: List elementspublic class ListItem {public Object data;public ListItem next;public ListItem(Object d) {data = d;next = null;}}Department of Computer Science — University of San Francisco – p.6/??18-7: Arranging ListItems•ListItems hook together like a chain.•All we need to do is keep track of the beginning of the chain.•No need to allocate everything ahead of time.Department of Computer Science — University of San Francisco – p.7/??18-8: The LinkedList class•The LinkedList will be responsible for hanging onto the ’head’ ofthe list and providing methods for working with the list.◦Insert()◦InsertAt(index)◦get(index)◦remove(index)◦find(object)Department of Computer Science — University of San Francisco – p.8/??18-9: The LinkedList classpublic class LinkedList {public ListItem head = null;public void insert(Object o) { ... }public void insertAt(Object o, int index) { ... }public Object get(int index) { ... }public Object remove(int index) { ... }public int find(Object o) { ... }}Department of Computer Science — University of San Francisco – p.9/??18-10: Adding•So how do we add something to the front of a linked list?◦Have the new thing point to the currently-first ListItem◦Point ’head’ to our new thing.public void insert(Object o) {ListItem l = new ListItem(o);l.next = head;head = l;}Department of Computer Science — University of San Francisco – p.10/??18-11: Adding•What about adding something into the middle of a list?•If we want an item to go between current elements 5 and 6,then we need our new item to point to 6, and 5 to point to thenew element.•How do we code this?Department of Computer Science — University of San Francisco – p.11/??18-12: Addingpublic void insertAt(Object o, int index) {// first find the place to insert it.ListItem pointer = head;ListItem l = new ListItem(o);for (int i = 0; i < index -1; i++) {pointer = pointer.next;}l.next = pointer;pointer = l;}Department of Computer Science — University of San Francisco – p.12/??18-13: Adding•Are there any special cases we need to worry about?Department of Computer Science — University of San Francisco – p.13/??18-14: Adding•Are there any special cases we need to worry about?◦What if the list is empty?◦What if it only has one element?◦What if we’re adding at the end?Department of Computer Science — University of San Francisco – p.14/??18-15: Exercise•Code the ListItem and LinkedList classes as described above.•Write a main method that creates a list and prompts the userfor strings, which are always added to the front of the list.•Add a method to the LinkedList class called toString().•This should walk the list and print out each of the strings inorder.Department of Computer Science — University of San Francisco – p.15/??18-16: Adding elements•To add an element at the front, we point the new element’s“next” pointer to whatever head is pointing to, then point head topoint to the new element.public void insert(String o) {ListItem l = new ListItem(o);l.next = head;head = l;}Department of Computer Science — University of San Francisco – p.16/??18-17: Exercise•So how do we iterate through a list and print out all theListItems?Department of Computer Science — University of San Francisco – p.17/??18-18: Exercise•So how do we iterate through a list and create a stringrepresenting all the list contents? ListItems?public String toString() {String result = ‘‘’’;ListItem current = head;while (current != null) {result += current.data;current = current.next;}}Department of Computer Science — University of San Francisco – p.18/??18-19: Adding elements•What if we want to add an element in the middle of the list?•First, we find where to put it, then we insert as if this was thefront.Department of Computer Science — University of
View Full Document
Unlocking...