18 2 Arrays Previously we talked about using arrays to store sequences of data Intro to Programming II Advantages Everything is stored in sequential memory locations Fast lookup of elements Linked Lists Chris Brooks Disadvantages Hard to resize Department of Computer Science Removing or adding an element in the middle is costly University of San Francisco Department of Computer Science University of San Francisco p 1 18 3 Linked Lists Department of Computer Science University of San Francisco p 2 18 4 Linked Lists Linked lists have the opposite advantages and disadvantages The general idea Advantages Easy to insert and remove Easy to resize Each element of the list will know who the next element is Let s try this as a class Disadvantages Elements are not stored sequentially Finding the nth element is slower Department of Computer Science University of San Francisco p 3 18 5 List elements Department of Computer Science University of San Francisco p 4 18 6 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 List elements public class ListItem public Object data public ListItem next public data next A pointer to the next element in the list ListItem Object d null d Department of Computer Science University of San Francisco p 5 Department of Computer Science University of San Francisco p 6 18 7 Arranging ListItems 18 8 ListItems hook together like a chain The LinkedList class The LinkedList will be responsible for hanging onto the head of All we need to do is keep track of the beginning of the chain No need to allocate everything ahead of time the 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 7 18 9 The LinkedList class public 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 8 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 9 18 11 Adding Department of Computer Science University of San Francisco p 10 18 12 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 the new element How do we code this Department of Computer Science University of San Francisco p 11 Adding public 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 18 14 Are there any special cases we need to worry about 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 13 18 15 Exercise Department of Computer Science University of San Francisco p 14 18 16 Code the ListItem and LinkedList classes as described above Write a main method that creates a list and prompts the user for 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 in order 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 to point 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 15 18 17 Exercise Department of Computer Science University of San Francisco p 16 18 18 So how do we iterate through a list and print out all the Exercise So how do we iterate through a list and create a string representing all the list contents ListItems 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 17 Department of Computer Science University of San Francisco p 18 18 19 Adding elements 18 20 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 the front Adding elements by position The easiest way to add is by position If we want an element to be in the nth position we find the n 1th element and insert after that public void insertAt String o int index ListItem newItem new ListItem o ListItem current head for int i 0 i index i current current next newItem next current next current next newItem Department of Computer Science University of San Francisco p 19 18 21 Adding elements by position Department of Computer Science University of San Francisco p 20 18 22 Is there any way that this code could fail Adding elements by position Is there any way that this code could fail What if index is larger than the number of elements in the list Department of Computer Science University of San Francisco p 21 18 23 Adding elements by position 18 24 Is there any way that this code could fail What if index is larger than the number of elements in the list Need to also make sure current is not null for int i 0 i n current Department of Computer Science University of San Francisco p 22 null i Department of Computer Science University of San Francisco p 23 Adding by order What if I want to add based on order Say we want to keep the list alphabetized Look through until I find the right place But I need to be careful I can t back up in the list Department of Computer Science University of San Francisco p 24 18 25 Adding by order 18 26 public void insertAlpha Stri ng name ListItem newItem new ListItem name ListItem current head if newItem data co mp are To cu rr ent d at a 0 insert name while current next d ata c omp ar eTo n ew Ite m dat a 0 current current next Adding by order Wrinkles What about running off the end of the list What if the list is empty What if there s one element in the list Department of Computer Science University of San Francisco p 25 18 27 Removing an …
View Full Document
Unlocking...