3 - Lists, Stacks, Queues and Priority Queues

3.1 - Introduction

• Choosing the best datastructures and algorithms for a particular task is one of the keys to developing high performance software.
• Data Structure = A collection of data organized in some fashion. Which supports storing, accessing and manipulating the data.
  • In OOP also known as a container or container-object.
  • Java provides datastructures in the Java Collections Framework.

3.2 - Collections

• Collection Interface = Defines the common operations for lists, vectors, stacks, queues, priority queues and sets.
• The Java Collections Framework supports:
  • Collection = Storing a "collection" of elements.
  • Map = Storing key/value pairs.
• Different types of collections (these are grouped in the java.util package):
  • Set = Store a group of nonduplicate elements.
  • List = Store a ordered collection of elements.
  • Stack = Store objects that are processed in a last-in, first-out fashion.
  • Queue = Store objects that are processed in a first-in, first-out fashion.
  • PriorityQueue = Store Objects that are processed in the order of their priorities.
• Interfaces = Provide methods to be implemented in a (abstract) class.
• (Convenience) Abstract Classes = Classes that provide partial implementation, which the user can extend.
• Concrete Classes = Classes that are completely implemented.
• Basic collection methods:
  • Add(all) - Adds an element, or a collection of elements to the current collection.
  • Remove(all) - Removes an element, or a collection of elements from the current collection.
  • Contains(all) - Returns true if the element or collection of element is in the current collection.
  • Size - Returns the amont of elements in the collection.
  • RetainAll - Keeps elements in the current collection that are also in the specified collection.
  • Clear - Removes all ellement from the current collection.
  • Equals - Returns true if the current collection is the same as the specified collection.
  • Hashcode - Returns the hascode for the current collection.
  • IsEmpty - Returns true if there are no elements in the current collection.
  • ToArray - Returns an array from the elements in the current collection.
• If you do not use a method in your project you should let it throw the UnsupportedMethodException.
• All concrete classes in the Java Collections Framework, with the exception of PriorityQueue are Clonable and Serializable.

3.3 - Iterators

• Iterator = An classic design pattern for walking through a data structure without having to expose the details of how data is stored in the data structure.
• The Collection interface extends the Iterable interface. This defines the iterator method which returns an Iterator object.
• Basic Iterator methods:
  • Next - Returns the next element in the iterator.
  • HasNext - Returns true if there is at least one more element in the iterator.
  • Remove - Removes the last element returned by the iterator.
• Iterators can be used inside a while or for-each loop.

3.4 - Lists

• List = Stores elements in a sequential order. Extends Collection. Concrete classes are ArrayList or LinkedList.
• Basic List methods:
  • Add(all) - Adds an element at a certain position, or a collection of elements at the end of the current list.
  • Get - Returns the element at a certain position in the current list.
  • IndexOf - Returns the FIRST index of the location of where the specified element is stored in the current list.
  • lastIndexOf - Returns the LAST index of the location of where the specified element is stored in the current list.
  • ListIterator - Returns the iterator object of the current list, additionaly from a specified index.
  • Remove - Remove the element at the specfied location in the current list.
  • Set - Sets a specified element at a specified index in the curent list.
  • SubList - Creates a new List from the element between the specified indecies of the current list.
• The iterator of a list (ListIterator) has some extra methods:
  • Add - Adds a specified element to the list.
  • HasPrevious - Returns true if there is an element before the current element in the iterator.
  • NextIndex - Returns the index of the next element in the iterator.
  • Previous - Returns the previous element in the iterator.
  • PreviousIndex - Returns the index of the previous element in the iterator.
  • Set - Replaces the last returned element by the previous/next method with the specified element.
• Arraylist VS LinkedLists
  • LinkedList has dynamic capacity, ArrayList has fixed capacity
    • Capacity of an ArrayList is at least as large as the list size.
    • If the capacity of the array is exeeded, a new array is created and the data transfered.
    • An ArrayList can be trimmed to size using trimToSize()
  • LinkedList best for instertion/deletion at the beginning or the end.
  • Arraylist best for random access trough a list.
  • Get is available in both, but faster for the ArrayList.
    • For linkedList an foreach would be beter then a forloop.
• LinkedList methods:
  • addFirst/addLast - Adds an element to the head/tail of the list.
  • getFirst/getLast - Returns the first/last element of the list.
  • removeFirst/removeLast - Removes the first/last element in the list.

3.5 - Comparator interface (+ 13.6, pg 509)

• Comparator
  • Comparing using a comparator.
  • Used when object does not implements Comparable.
  • Compares two objects of anther class.
• Comparable
  • Comparing using natural order.
  • The comparator/comparable interface defines the compareTo() method.
  • CompareTo() determines the order of this object with the specified object.
    • Returns negative integer (<0) if less then the specified object.
    • Returns 0 if equal to the specified object.
    • Returns positive integer(>0) if greater then the specified object.
  • Comparable interface is a generic interface.
    • Implemented in standard Java object (ex. Integer, Byte, Long, Double, Date, Calendar, String etc)
  • Arrays.sort() uses the comparator interface to sort the array.

3.6 - Static methods for lists and collections

• The list in these methods needs to be specified, because they are static.
• Static methods for list:
  • Sort (w/o and w comparator) - Sorts the specifiet
  • Binary Search (w/o and w comparator) - Searches the key in the sorted list using binary search.
  • Reverse - Reverses the list.
  • ReverseOrder - Returns a comparator with reverse ordening
  • Shuffle (w/o and w a Random object) - Shuffles the list.
  • Copy - Copy the source list to the destination list
  • nCopies - Returns list with n copies of the obejct.
  • Fill - Fills the list with the object.
• Static methods for collection
  • Frequency - How often an element occurs in a collection.
  • Disjoint - Returns true if both collections have no elements in common.
  • Min (w/o and w comparator) - Min object in collection
  • Max (w/o and w comparator) - Max object in collection

3.7 - Vector and Stack Class

• Vector is the same as ArrayList, except it contains Synchronized methods for accessing/modifying the vector by more then 1 thread concurrently.
• Stack is implemented as en extention of Vector.
  • Stack has a last-in first-out structure.
• Stack methods:
  • Empty - True if the stack is empty.
  • Peek -Returns the top element of the stack
  • Pop - Returns and removes the top element of the stack
  • Push - Adds a new element on top of the stack.
  • Search - Returns the position of a specified element in the stack.

3.8 - Queue and priority Queues

• Queue has an first-in first-out structure.

• In a priority queue the element with the highes priorirty is removed first.

• Queue methods:

  • Offer - Inserts an element into the queue.

  • Poll - Retrieves and removes the head. Null when queue is empty.

  • Remove - Retrieves and removes the head of the queue. Exception when queue is empty.

  • Peek - Retrieves but does not removes the head of the queue. Null when queue is empty.

  • Element - Retrieves but does not removes the head of the queue. Exception when queue is empty.

• LinkedList extends Deque interface, which extends the Queue interface.

• Deque = Double-ended-queue. (deck) (getFirst, getLast, removeFirst, removeLast etc.)

• While constructing a Priority queue, you can specify an comparator. Otherwise the Comparable will be used.

3.9 - Evaluating an expression using stacks