For the Exam

• If your battery does not last the entire class, be sure to bring a power strip
• You will only be allowed to access desire2learn and laughton.com
• If you want to use it, download the javadoc libraries to your computer
• Have the book code and the solutions to the homework on your computer
• You may use your book, notes, and code

Topics to take special note of

• LinkedList Iterator
• Big O
• Use of Stacks, Queues, Sets, Maps, and LinkedList
• . . .

LinkedList Iterator

Look at this code snippet. Where is the iterator after line one has executed? The | is the iterator

        LinkedList<String> list = new LinkedList<>();
        list.addLast("A");
        list.addLast("Q");
        list.addLast("X");
        list.addLast("Z");
        
        ListIterator<String> iterator = list.listIterator(); //line 1
        iterator.next(); //line 2
        iterator.add("K"); //line 3
        iterator.next();
        iterator.next(); //line 4
        iterator.remove(); //line 5
        iterator.next();
        iterator = list.listIterator(); 

• |A Q X Z
• A |Q X Z
• A Q X Z |
• An exception is thrown

Big O

When:

• You need to access each element - O(n)
• You do a constant number of steps no matter how big n is - O(1)
• For n times you perform an operation that is O(n) - O(n²)

Big O

• What is the Big O efficiency of an algorithm to find the sum of all the values in an ArrayList?
• What is the Big O efficiency of an algorithm to find the sum of all the values in a LinkedList?
• What is the Big O efficiency of an algorithm to find the sum of the first 10 values in an ArrayList?
• What is the Big O efficiency of an algorithm to find the number of times 3 appears in an ArrayList of Integers?

 

Sets

How would you go about finding the union of two sets?