Final Exam Cheat Sheet PDF

Preview

Summary

Download Final Exam Cheat Sheet PDF

Description

Collections: • An abstraction hides details to make a concept easier to manage • All objects are abstractions in that they provide well-defined operations (the interface) • They hide (encapsulate) the object's data and the implementation of the operations • An object is a great mechanism for implementing a collection A data type is a group of values and the operations defined on those values implemented. • A data structure is the set of programming constructs and techniques used to implement a collection declaration of a NumberValue object named num that will use Integer for its type. NumberValue num = new NumberValue(); Stack LIFO: Array: bottom of array stack is 0, top integer indicates where the top of the stac kis and how many elements it has Array Push method: o public void push(T element) { o if(count == stack.length) { o T[] newStack = new T[stack.length*2]; o for(int i = 0; i < stack.length; i++) o newStack[i] = stack[i]; o stack = newStack; o } o o stack[count++] = element; o } Linked Push method o o public void push(T element) { o LinearNode newNode = new LinearNode(element); o newNode.setNext(top); o top = newNode; o count++; o } Linked Peak: public T peek() throws EmptyCollectionException { if (isEmpty() ) throw new EmptyCollectionException("stack"); T result = top.getElement(); return result; } o The API's stack class is derived from Vector, which has many non-stack abilities

• An abstract data type (ADT) is a data type that isn't pre-defined in the programming language An abstract data type is a data type whose values and operations are not inherently part of the programming language. It is abstract in that its implementation details should be hidden from the user. A user interacts with the abstract data type through its interface, without knowing the details of how the abstract data type is implemented. } To insert a node at the front of the list, first point the new node to the front node, then reassign the front reference

A collection is an object that is used to gather and organize other objects. Since it is an object, it has instance data and member methods. The instance data and member methods together define what the collection is and how the collection works. As an object, a collection is an abstraction, in that users interact with it through its interface, its public methods, without having to know anything about its instance data or how the methods work. By using the collection’s interface, users do not have to know the internals of how the collection is – indexed lists: numeric position in list, index updated every time list changes (java api likes this one). NEVEER a gap between elements Find operation used used privately by remove, contains, and addAfter. RELIES on equal method. List interface (implemented by ArrayList and LinkedList classes) Array list implementation – shifting cant be avoided to O(n) can be used Linked List is the obvious choice. LinearNode is reused here as with queue and stack. Head and tail references are maintained and an interger called count

Queue FIFO:

-

Common list operations

Array:

Java provides an interface named Queue. The LinkedList class is one of the classes that implements this interface. Though the interface is named Queue, the methods in the interface do not use the names of the queue operations as described in the text. The Queue interface has several methods that are similar to the queue operations but that have slightly different behaviors. Circular array enqueue

public void enqueue(T element) { if(count == queue.length) expandCapacity();

o

Algorithms: The symbol omega (Ω) refers to a lower-bound function. Theta (Θ) refers to a function that establishes both an upper and a lower bound. Big-Oh notation, O( ), refers to an upper bound on a growth function. Loops, nested loops, and calls to methods all contribute to the complexity of an algorithm

queue[rear] = element; rear = (rear+1)%queue.length; count++; } Linked Enqueue public void enqueue(T element) { LinearNode newNode = new LinearNode(element);

if(count == 0)

-

front = newNode; Maze TraversaL: o • An object representing a position in the maze is pushed onto the stack when trying a path o • If a dead end is encountered, the position is popped and another path is tried

Linked List sentinel node: When adding and removing nodes from a linked list, the first node of the list is treated as a special case. This is because the list reference variable points to this node and will have to be adjusted if a node is added to or removed from the head. With the use of a dummy node, the reference to the top of the list will never change (it will always refer to the dummy node), so the operations of

else rear.setNext(newNode);

rear = newNode; count++; } Size method linked list queue no count variable public int size() { int count; if (head == null) count = 0; else { count = 1; LinearNode temp = head; // for traversal while(temp.getNext() != null) { count++;

Consider the following loop: count = 1; while (count < n) { count *= 2; // some sequence of O(1) steps } The loop is executed log2n times, so the loop is O(log n) The infix expression (3 * 4 – (2 + 5)) * 4 / 2 is equivalent to the postfix expression 34*25+–4*2/ linked list: Person current = first; while (current != null) { System.out.println(current); current = current.next; } Iterators: An Iterable class is one that implements the Iterable interface. The Iterable interface has a single method, iterator, that returns an Iterator object. The returned object can be used to iterate over objects of the class that implements the Iterable interface.

adding and removing nodes can be simplified. don’t motify pointer unless inserting nodes or removing code. pointer should not be used to traverse list. Person current = first; while (current != null) { System.out.println(current); current = current.next;

temp = temp.getNext(); // go to next node } // end while } // end else return count; } // end method size Lists: – ordered lists: ordered by inherent characteristic. “add” operation is particular to this. unordered list: addToFront, addToRear, addAfter

Suppose myList is an ArrayList of Book objects Iterator it = roster.iterator(); while (it.hasNext() ) { it.next(); it.remove(); }



if(n == 0) • The first line obtains the iterator, then the loop uses hasNext and next to access and print each book Iterator: -

no ADD method

An inner class is a class that is declared inside of another class. A list iterator class is only for the use of the class that implements the list, and as such is private to the list class. The list class should be iterable, but the list iterator class is not. The list iterator implements the Iterator interface, but it is a concrete class and not itself an interface A user-defined iterator needs to know the size of the collection when the iterator is created. The iterator uses this to detect if the collection is modified via a reference to the collection. If modifications are detected, the iterator throws a ConcurrentModificationException. The for-each loop can also be used instead of hasNext and next methods. It does not explicitly declare an iterator, but Java translates the for-each code into code that uses an iterator before the code executes. for (type var : array) { statements using var; } is equivalent to: for (int i=0; i 0 recursive method that computes the sum of the first n integers: public int sum(int n) { Comparable

Comparator – no commit of class to particular comparing technique

1) Comparable provides a single sorting sequence. In other words, we can sort the collection on the basis of a single element such as id, name, and price.

The Comparator provides multiple sorting sequences. In other words, we can sort the collection on the basis of multiple elements such as id, name, and price etc.

2) Comparable affects the original class, i.e., the actual class is modified.

Comparator doesn't affect the original class, i.e., the actual class is not modified.

3) Comparable provides compareTo() method to sort elements.

Comparator provides compare() method to sort elements.

Radix sort: In a radix sort, the radix is the number of queues, which is the number of possible values of each digit or character in a sort key.

K ( n )=n∗ K ( n−2 ) if n iseven ∧ greater than2 K ( n )= K ( n− 1 ) if n is odd ∧ greater than 2 method that computes the product of all of the even integers less than or equal to n. public int productOfEvens(int n) { if(n...