# Lists and ArrayList many slides taken from Mike Lists and ArrayList many slides taken from Mike Scott, UT Austin CS 307 Fundamentals of Computer Science 1 Description of Lists Lists maintain items in a definite order Items can be added normally at the end in any valid location? access items in the list first, last, any valid location? delete items

any valid item? CS 307 Fundamentals of Computer Science 2 List Interface Design a list interface with all of the basic operations and then add optional operations you feel are appropriate: CS 307 Fundamentals of Computer Science 3 Implementing a List After designing interface next step is to

complete an implementation What should be used as the internal storage container? CS 307 Fundamentals of Computer Science 4 The Default Add Method Default add usually means add to the end of the list. public boolean add(Object item) CS 307 Fundamentals of Computer Science 5

Big O of the Default add? Normal Big O analysis fails "Most" adds are inexpensive O(1) A few adds are very expensive due to resizing O(N) What is the average case? To determine average case we'll do an amortized analysis amortized is a term from accounting. Spread the cost of something over time. CS 307 Fundamentals of Computer Science 6

Simplified Amortized Analysis Add N items to the list, always at end of list Assume internal container starts out at size 1 Assume if we resize container we double the size Item # 1 2 3 4 5 6 7 8 9 N-1 N CS 307 Fundamentals of Computer Science

Size of Container 1 1 -> 2 2 -> 4 4 4 -> 8 8 8 8 8 -> 16 Work to Resize 0 1 2 0

4 0 0 0 8 N-1 0 N - 1 -> 2N - 2 N - 1 Work to Add 1 1 1 1 1 1 1

1 1 1 1 7 Total Work to Add N items The work in resizing is the sum of a geometric sequence 1 + 2 + 4 + 8 + 16 + + (N-1)/2 + N-1 an = a 1 * r n - 1 sum terms 1 through n = (r * an - a1)/ (r - 1) a1 = 1, an = N - 1, r = 2, sum = (2 * (N - 1) - 1) / (2 - 1) = 2N - 3 CS 307 Fundamentals of Computer Science 8

Average Work Per Item Total Work is N + 2N - 3 = 3N - 3 Divide by the N items to amortize the cost: (3N - 3) / N items = 3 - 3/N steps per item The average work per item is 3 - 3/N The amortized Big O is O(1) What would the amortized Big O of adding at the end of the list be if we resized the list by 100 elements every time we needed to resize? 100+200+300++n=100(1+2++n/100)=? CS 307 Fundamentals of Computer Science 9 Adding at an Arbitrary Location in List public void add(Object item,

int position) CS 307 Fundamentals of Computer Science 10 The contains method public boolean contains(Object item) CS 307 Fundamentals of Computer Science 11 An addAll method public void addAll(ArrayList other) CS 307 Fundamentals of

Computer Science 12 Insertion In operation insertAtRank(r, o), we need to make room for the new element by shifting forward the n r elements V[r], , V[n 1]] In the worst case (r 0), this takes O(n) time V 0 1] 2 r n 0 1] 2 r

n 0 1] 2 o r V V CS 307 Fundamentals of Computer Science n 13 Deletion In operation removeAtRank(r), we need to fill the hole left by the removed element by shifting backward the

n r 1] elements V[r 1]], , V[n 1]] In the worst case (r 0), this takes O(n) time V 0 1] 2 o r n 0 1] 2 r n 0 1] 2 r

V V CS 307 Fundamentals of Computer Science n 14 From the Iterator interface Method Summary: public boolean hasNext() Returns true if the iteration has more elements. public Object next() Returns the next element in the iteration. public void remove()

Removes from the underlying collection the last element returned by the iterator (optional operation). Iterators allow a programmer to access all elements in a Collection object, one at a time, without having to worry about underlying implementation: For addAll(Collection other) we are only interested in hasNext and next CS 307 Fundamentals of Computer Science 15