Lists and ArrayList many slides taken from Mike

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

Recently Viewed Presentations

  • Symposium New Directions in Evolutionary Computation New Directions

    Symposium New Directions in Evolutionary Computation New Directions

    We compared our EA with self-adaptive semi-autonomous parent selection to a regular EA on three test problems: counting ones, 4-bit deceptive trap, and SAT. ... Arial MS Pゴシック Times Times New Roman Blank Presentation Microsoft Office Excel Chart MathType 5.0...
  • Windows 8: The Basics Mouse/Keyboard Learn about the

    Windows 8: The Basics Mouse/Keyboard Learn about the

    Sports, update in real time so you can see the latest information in one place. Windows 8 offers the . ... view the list that appears to the left or type in the search box in the top right corner....
  • Power Delivery Vulnerability

    Power Delivery Vulnerability

    —Local Recycled Energy and the Technologies to use it. Tina Kaarsberg, PhD House Science Committee, Energy Subcommittee [email protected]
  • Can material time derivative be objective? T. Matolcsi Dep ...

    Can material time derivative be objective? T. Matolcsi Dep ...

    If are inertial coordinates, the Christoffel symbol with respect to the coordinates has the form: where is the angular velocity of the observer Material time derivative: is the point at time t of the integral curve V passing through x....
  • Part I. Strategic Management Inputs

    Part I. Strategic Management Inputs

    Integrated and coordinated commitments and actions must be to pursue a long-term mission and vision. Must involve multiple functional areas. Must have impact on long-term profitability. Goals of Strategy (e.g., what we are trying to achieve): Strategic Competitiveness. Can be...
  • Protist and Fungi - Winston-Salem/Forsyth County Schools

    Protist and Fungi - Winston-Salem/Forsyth County Schools

    Protist and Fungi You will be able to explain how protists and fungi are similar and different than other common microscopic organisms. Prokaryote (Bacteria Cell) Can Not See Nucleus Much smaller than Eukaryote cells No visible organelles Contains DNA and...
  • Microcystin toxin in fish and shellfish in James River

    Microcystin toxin in fish and shellfish in James River

    Microcystin toxin in blue crabs in James River;Analysis of 2012 and 2013 monitoring. ... Standard Calculation of Allowable Concentration of Toxicant in Fish & Shellfish . RfD (TDI) (0.00004 mg/kg/day) X Body Weight . fish consumption rate (0.0175 kg/day
  • Alpha Friends - Dublin Unified School District

    Alpha Friends - Dublin Unified School District

    Edith Eagle. Edith Eagle eats and eats. e. e. e_e. ea. _y. ie. Motion: Use their arms to soar like an eagle moving body to make the shape of an e in the air. /long e/