Week 02.pdf

CS 1332 - Week 02 Monday Topics I. Iterator and Iterable A. Import statements: 1. import java.lang.Iterable → implicit, not very involved, only requires one...

CS 1332 - Week 02 Monday Topics I. Iterator and Iterable A. Import statements: 1. import java.lang.Iterable → implicit, not very involved, only requires one method to be implemented 2. import java.util.Iterator → explicit, very involved, requires the creation of a class with several methods that must be implemented B. Code demo import java.lang.Iterable; import java.util.Iterator; public class LinkedList implements Iterable { private Node head; public Iterator iterator() { // for Iterable return new LLit(this); } private class LLit implements Iterator { private Node current; private LLit(LinkedList list) { current = head; // gives us starting point } public boolean hasNext() { return current != null; } public Type next() { Node tmp = null; if(hasNext()) { tmp = current; current = current.next; return tmp.data; } else { return null; } } } }  C. Iterable - requires the iterator() method to be overridden which returns the iterator D. Iterator - an object which iterates through the structure 1. Our iterator will be similar to the loops we’ve used to manually traverse through the list 2. Requires two methods to be overridden: next() and hasNext() a) hasNext() → returns if current is NOT null (if the iterator ​has​ a ​next data element to return) b) next() → returns the ​next​ data the iterator has yet to give you (the data from the current node) and moves current to the next node E. Code demo: using the iterator LinkedList courses = new LinkedList(); courses.add(“1332”); // add some more courses... // implicitly use iterator for (String course: courses) { System.out.println(course); } // explicitly use iterator Iterator courseit = courses.iterator(); while(courseit.hasNext(){ System.out.println(courseit.next()); } 1. Iterators are implicitly called when using for-each loops - there’s no stopping it and you can’t really use it to alter list values 2. You can explicitly use the iterator by instantiating an Iterator to step through the linked list and have more control over each step II. Doubly Linked Lists A. Generally always have both a head and tail pointer B. A doubly linked node is going to have next and previous pointers and data. C. For a DLL of size 0, both the head and tail point to null D. For a DLL of size 1, both the head and tail point to the single node E. For a DLL of size > 1: 1. Adding to the front: a) Create the new node b) Connect the node to the LL → set the new node’s next to the head c) Connect the LL to the node → set the head’s prev to the new node d) Point the head to the new node 2. Adding to the back: a) Create the new node  b) Connect the node to the LL → set the new node’s prev to the tail c) Connect the LL to the node → set the tail’s next to the new node d) Point the tail to the new node 3. Make sure you always change the head/tail after everything else has been connected, we do not want to lose these references! 4. Removing from the back: a) Set the tail to tail’s previous b) Set the tail’s next to null 5. Removing from the front: a) Set the head to head’s next b) Set the head’s previous to null 6. Edge case: removing from a list of length 1 → set head and tail to null III. Circular Singly Linked Lists A. The last node in the list points back to the head. B. We can no longer use current == null to check if we’ve reached the end of our list 1. We must use current == head (reference equality) to terminate our loop C. How to NOT add to the front: 1. Create a new node, point it to the head, and move the head 2. Resetting the last node to point to the new head would be O(n) because we would have to iterate through the list to find it D. Adding to the front in O(1) (the correct way): 1. Create a new, empty node 2. Connect the node to the CLL → set the new node’s next to head’s next 3. Connect the CLL to the node → set head’s next to the new node 4. Put the data from the head into the new node 5. Put the data we want to add into the head node E. Adding to the back in O(1): 1. Perform the steps to add to the front 2. Now, just move the head to head’s next and the data you just added is now at the back of the list F. Removing from the front in O(1) (when size > 1): 1. Save the data from the head somewhere to return later 2. Copy the data from head’s next into the head 3. Set head’s next pointer to head’s next’s next (essentially cutting the node at index 1 out of the list) G. Unfortunately, removing from the back cannot be optimized with a data manipulation trick → it will be O(n) to iterate to the node before the last one Wednesday Topics I. Recursion Basics A. Definition: a method repeatedly calls itself  B. Must haves: 1. Base case/terminating condition (can have multiple) 2. Recursive call to function (can have multiple) 3. A parameter that advances toward termination (can have several) C. Termination is very important to prevent infinite recursion D. Basic structure: rFunction (parameter) if (parameter meets terminating condition) return value else return rFunction(changed parameter) // self-call can be before return but not after II. Math-based recursion - classic examples: factorial, fibonacci A. Example: compound interest = A = P*(1 + (r/n))​nt B. Function: recursive IRA rIRA(p, r, t) // principle, rate, time if (t