List ADT

zyBook

Java Collections Framework

List Interface

Dynamic Arrays

• Let’s draw a picture…

Socrative Quiz

Evaluate the big-\(\Theta\) running time of the following methods.

  public static double searchAll(ArrayList<Integer> numbers) {
      long locSum = 0;
      for (int num : numbers) {
          locSum += numbers.indexOf(num);
      }
      return locSum / numbers.size();
  }

  public static void removeAll(ArrayList<Integer> numbers) {
      for (int i = 0; i < numbers.size(); i++) {
          numbers.remove(0); // remove element at index 0.
      }
  }

1. searchAll: \(\Theta(n)\), removeAll: \(\Theta(n)\)
2. searchAll: \(\Theta(n^2)\), removeAll: \(\Theta(n)\)
3. searchAll: \(\Theta(n)\), removeAll: \(\Theta(n^2)\)
4. searchAll: \(\Theta(n^2)\), removeAll: \(\Theta(n^2)\)

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?
  • \(\Theta(n)\)
• Best case?
  • \(\Theta(1)\)

ArrayList add Analysis

• What is the worst-case big-\(\Theta\) 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)
      }
    }

• \(\Theta(n)\)?
• \(\Theta(n^2)\)?

• Somewhere in-between?

Let’s time this to see if that gives any insight…

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 \(n\) appends:

• \(n\)	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: \[ n + \sum_{i=0}^{\lceil \log_2 n \rceil-1} 2^{i} \]

Solving the Summation

\[ \begin{aligned} n + \sum_{i=0}^{\lceil \log_2 n \rceil-1} 2^{i} &=n + 2^{\lceil \log_2 n \rceil-1+1} - 1\\ &=n + 2^{\lceil \log_2 n \rceil} - 1 \\ &\leq n + 2^{ \log_2 n +1} - 1 \\ & = n + 2n - 1\\ &= 3n - 1 \leq 3n \end{aligned} \]

Amortized cost of append

• Total assignments for \(n\) appends is \(\leq 3n\).
• Average cost across \(n\) appends is \(\leq \frac{3n}{n} = 3\)
• Amortized cost of append is \(\Theta(1)\)

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?

public static void respondToCollision(Area area) {

    loggingList.add("Airbag Depolyed!");
    if (area == Area.FRONT)
        deployAirbag();
}

1. LGTM
2. Spelling error in log message.
3. area == Area.FRONT should be area.equals(Area.FRONT)
4. Efficiency issues could lead to loss of life.
5. Problem with code style: Missing braces after if.

Bankers View (informal)

• Claim: Any sequence of \(n\) appends will require no more than \(3n\) 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.
  • \(\Theta(n)\)
• Amortized worst case?
  • A series of \(n\) insertions at the beginning
  • Still \(\Theta(n)\)