Java Collections Framework

• Collections in Java is a framework.
• It provides an architecture to store and manipulate groups of objects.
• It can search, sort, insert, manipulate, and delete data.

Overview of the Collections Framework

• Collections group elements for later retrieval.
• The Java collections framework has a hierarchy of interface types and classes.
• Interface types are implemented by one or more classes.
• The Collection interface is implemented by all classes in the collection framework.
• The Collection interface is at the root and provides a common set of methods.
• The collections framework represents and manipulates collections using interfaces, implementation classes, and algorithms.
• Interfaces are abstract data types that allow collections to be manipulated independently.
• Implementation classes are concrete data structures that can be reused.
• Algorithms are computation methods that include searching and sorting.
• Algorithms are polymorphic, allowing the same method to be used across different implementations.

Advantages of the Collections Framework

• The API has interfaces for Collection, Set, List, and Map.
• Classes implementing these interfaces have a common set of methods.
• The framework supports abstraction, simplifying collection design.
• High-performance data structures and algorithms enhance program speed and quality.
• Programmers can use optimized implementations for algorithm and program performance.

List Interface

• Elements are stored by order.
• ArrayList and LinkedList are implementing classes.

Set Interface

• It is an unordered collection of unique elements.
• Finding, adding, and removing elements is more efficient.
• This is achieved using hash tables or binary search trees.

Stack

• Elements are stored by order.
• Additions and removals can only occur at the top.

Queue

• Items are added to the tail and removed from the head, following First-In-First-Out (FIFO) order.

Priority Queue

• It is an unordered collection that efficiently removes the highest priority element.

Map

• It maintains associations between key and value objects.
• Each key has a single associated value.
• It stores all the keys, values, and their associations.

Diamond Syntax

• This syntax enhances array lists and other generic classes.
• Usage: ArrayList names = new ArrayList<>();
• The empty brackets <> are referred to as the "diamond syntax".

Linked Lists

• A data structure collects sequences of objects efficiently adds/removes elements in the middle of sequence.
• A linked list consists of nodes, each with a reference to the next node.
• It stores an element and references neighboring nodes.
• Each node is linked to its neighbors.
• Adding and removing elements in the middle of a linked list is efficient.
• Visiting elements in sequential order is efficient
• Random access is not efficient
• Linked lists should be used when you need efficient insertion or removal and do not need random element access often.

LinkedList Class

• Generic class, specifies element type with brackets: LinkedList<Product>
• Package: java.util
• LinkedList has Collection methods.

List Iterator

• It accesses element inside a linked list.
• It encapsulates a position anywhere inside the linked list.
• An iterator is a pointer between two elements, similar to a cursor in a word processor.
• To get a list iterator of a LinkedList class, use the listIterator method.
• ListIterator<String> iterator = employeeNames.listIterator();
• ListIterator is also a generic type.
• It initially points before the first element.
• It moves the position with the next method.
• The next method returns the element being passed.
• The return type of the next method matches what the iterator's parameter is.
• Nodes store 2 links, next and previous (doubly-linked list).
• Use hasPrevious and previous to move backwards.

List Iterator Methods: Add and Remove

• The add method adds an object after the iterator and moves the iterator past the new element.
• iterator.add("Juliet") sample code from text
• The remove method removes the object returned by the last call to next or previous.
• To remove elements that meet a condition:

  while (iterator.hasNext()) {
    String name = iterator.next();
    if (condition is fulfilled for name)
      iterator.remove();
  }

• remove Function must be called only once after calling next or previous and cannot be immediately after an add.
• If remove is called improperly, throws IllegalStateException

List Iterator and Iterator Interfaces

• ListIterator interface extends Iterator interface.
• Iterator interface is not supported for the previous method.

Sets in Java

• Sets organizes values for efficiency, potentially not in the order added.
• Inserting and removing elements is more efficient than in lists.
• The Set interface has the same methods as the Collection interface.
• Duplicates are not allowed.
• HashSet uses a hash table.
• TreeSet uses a binary search tree.

Hash Table Implementation

• Elements must implement hashCode and have a properly defined equals method.

TreeSet Implementation

• You can form tree sets for any class that implements the Comparable interface. Example: String or Integer
• Use a TreeSet if you want to visit the set's elements in sorted order
• Otherwise choose a HashSet
• It is a bit more efficient - if the hash function is well chosen.
• Store the reference to a TreeSet or HashSet in a Set variable:
  • Set names = new HashSet<>(); or
  • Set names = new TreeSet<>();
• Implementation no longer matters/ only the interface is important after constructing the collection object

Working with Sets

• Adding and removing elements
  • names.add("Romeo"); names.remove("Juliet");
• Sets do not have duplicates, adding is ignored
• The contains method tests whether an element is contained in set, using equals method of element type
• The iterator interface as no previous method.
• To process each element of a set, can use an iterator or the “for each” loop
  • for (String name : names)
  • String name = iter.next();
• Cannot add an element to a set at an iterator position, set is unordered.
• An example is a spellcheck program that uses hash sets.

Maps in Java

• The map allows association elements from a key set paired with elements from a value collection
• Use maps to look up objects by keys.
• The reference to the map object is stored in a Map. Methods:
• Associates a value with a key: favoriteColors.put("Juliet", Color.RED)
• Returns the value with a key: favoriteColors.get("Juliet")
• Check if asking get on a the key that does not exist: returns null value instead
• Modify the value of an existing key. favoriteColors.put("Juliet", Color.BLUE)
• To removes by calling the key to be removed

Additional Map info

• TreeMap, HashMap, are the implementations of Map
• Maps using keys values and declaring types looks as follows: Map wordFrequency;
• A map stores associations between keys and values.
• KeySet yields all keys, each key has an associated value.
• To print all key/value pairs:

       Set keySet = m.keySet();
       for (String key : keySet){
            Color value = m.get(key);
            System.out.println(key + "->" + value);
      }

Queues in Java

• A queue adds items to the tail and removes them from the head, following a First-In-First-Out (FIFO) order.
• A queue is visualized is as people all lined up
• The Queue interface has add (adds an element to the tail), remove (removes the head) and peek (gets the head element).
• The LinkedList class inplements the Queue Interface
• LinkedList object can be initialized to a Queue variable: Queue q = new LinkedList();

Priority Queues

• A priority queue collects element, each of which has a priority.
• Priority queues retrieve elements according to which priority it is.
• Elements use a Comparable interface in order to belong to the class.
• An example is WorkOrder

When to use a queue vs linkedlist

• LinkedList: Can ensure only operations can be invoked on the object.
• ArrayList for implementing a queue: Both more inefficient operations b/c need to move.

Queue Sample Code Output?

• Queue q = new LinkedList(); q.add("A"); q.add("B"); q.add("C");
• while (q.size() > 0) { System.out.print(q.remove() + " "); - Answer: A B C

Sample code in practice, priority queues and strings

• PriorityQueue q = new PriorityQueue(); q.add("3 - Shampoo carpets"); q.add("1 - Fix broken sink"); q.add("2 - Order cleaning supplies");
• Yes, smallest string(in lexicographic ordering) is removed first, but must adhere to the "scheme" to implement priority: string starting 1,2
• If not adhered by numbers exceeding 9, it will be incorrect. Ex: String starts with "10".

Choosing a Collection

• Determine how you access the values and also the element types or key/value types
• Determine whether element or key order matters
• For collections, determine operations to be efficient.
• Hash sets and Maps, decide what to implement for hashCode methods.
• Use trees what what to supply a comparator.

Collections Class

• Collection class provides algorithms for manipulating elements.
• Algorithms are implemented as static methods.
• Method sorts the elements.
• Sort call may specify a comparator for alternate ordering.

Interface comparator

• Interface for elements sorting Collection's elements in a different order.
• The method reverseOrder() returns comparator objects in reverse order for collection

Static Collections, method and binarySearch.

• Static Collections, use method binarySearch() to locate an object in list.

• If located Index can be returned

• If not index returns negative to indicate failed results

• If not found, function will go through the array, calculating each point and signs negative if results not found