List ADT

Java Collections Framework

List Interface

Question...

• What will be printed by each of the following code snippets?

• OpenDSA AList

  List<Integer> numbers = new AList<>(); for (int i = 0; i < 10000; i++) { numbers.append(i); } System.out.println(numbers.length());

• java.util.ArrayList

  List<Integer> numbers = new ArrayList<>(); for (int i = 0; i < 10000; i++) { numbers.add(i); } System.out.println(numbers.size());

Dynamic Arrays

• Let's draw a picture...

ArrayList append/add Analysis

• How should we measure the input size?
• Worst case?
• Best case?

ArrayList add Analysis

• How should we measure the input size?
  • Number of elements currently stored.
• Worst case?
• Best case?

ArrayList add Analysis

• What is the worst-case big- running time of this method? public static void addNumbers(int n) { ArrayList<Integer> nums = new ArrayList<>(); for (int i = 0; i < n; i++) { nums.add(i); // Best case Theta(1), worst case Theta(n) } }
• ?
• ?
• Somewhere in-between?

Let's time this to see if that gives any insight...

Reminder... Geometric Series

• is a common case...

Cost of Append in Dynamic Array

• Select array assignments as the basic operation.

• We want an amortized analysis... Average cost of the operation over a sequence of operations.

• This table shows the total and average cost after appends:

• 	assignment cost	resize cost	total	average
  1	1	0	1	1
  2	1	1	3	1.5
  3	1	2	6	2
  4	1	0	7	1.75
  5	1	4	12	2.4
  6	1	0	13	2.167
  7	1	0	14	2
  8	1	0	15	1.875
  9	1	8	24	2.667
  ...	...	...	...	...

  • Total assignments equal to:

Solving the Summation

Amortized cost of append

• Total assignments for appends is .
• Average cost across appends is
• Amortized cost of append is

Socrative Quiz...

You are performing a code review on the following Java method. This is part of the software that manages an automobile's safety features. loggingList is an ArrayList that stores log messages that will eventually be saved to persistent storage. Which of the following is the most appropriate evaluation of this code?

A) LGTM
B) Spelling error in log message.
C) area == Area.FRONT should be area.equals(Area.FRONT)
D) Efficiency issues could lead to loss of life.
E) Problem with code style: Missing braces after if.

Bankers View (informal)

• Claim: Any sequence of appends will require no more than assignments.
• We imagine that on every non-expanding append we deposit 3 coins
  • One is used to pay for the required assignment
  • Two are set aside for a rainy day
• When an expansion is required we pay for it with coins we saved earlier. Will there be enough?
• We have two coins for every append since the last expand
  • After the previous expand, half the space was empty
  • Each time we appended, we deposited two coins
  • Half the entries have two coins: enough for one coin per entry
  • These will "pay" for moving all entries to the new array

What about insert (not append)?

• Worst case? (When does the worst case happen?)
  • Insertion at the beginning with resize.
• Amortized worst case?
  • A series of insertions at the beginning
  • Still