New Note

• 20.1 Introduction

  • A data structure is a collection of both data and operations for accessing and manipulating the data organized in some fashion

  • A container or container object is an object that stores other objects, referred to as data or elements

  • To define a data structure is basically to define a class

  • The class for a data structure uses data fields to store data and provides methods to have operations like search, insert, and delete

  • Creating a data structure is creating an instance from the class; apply the methods on the instance to manipulate the data structure

  • Java Collections Framework is a set of data structures that organize and manipulate data efficiently; include lists, vectors, stacks, queues, priority queues, sets, and maps

• 20.2 Collections 

  • Java Collections Framework supports two types of containers

    • A collection is a container that stores a collection of elements

    • A map (discuss in later chapters) is a container that stores key/value pairs; are efficient for quickly searching an element using a key

  • There are different kinds of collections

    • A Set stores a group of non duplicate elements

    • A List stores an ordered collection of elements

    • A Stack stores objects that are processed in a last-in, first-out fashion

    • A Queue stores objects that are processed in a first-in, first-out fashion

    • A PriorityQueue stores objects that are processed in the order of their priorities

  • All of the interfaces and classes in the Java Collections Framework are grouped in the java.util package

  • Convenience abstract classes are abstract classes that partially implements an interface, making it convenient for the user to write the code by defining a concrete class that extends the abstract class rather than implementing all the methods in that interface

  • The Collection interface is the root interface for manipulating a collection of objects

  • The AbstractCollection class provides partial implementation for the Collection interface (implements all the methods in the interface except for the add, size, and iterator methods as those are implemented in the concrete subclasses)

  • The Collection interface provides the basic operations for adding and removing elements in a collection

    • The add method adds an element to the collection

    • The addAll method adds all the elements in the specified collection to this collection

    • The remove method removes an element from the collection

    • The removeAll method removes the elements from this collection that are also present in the specified collection

    • All of these methods return boolean (returns true if the collection is changed as a result of the method execution)

    • The clear() method removes all the elements from the collection

  • The Collection interface provides various query operations

    • The size method returns the number of elements in the collection

    • The contains method checks whether the collection contains the specified element

    • The containsAll method checks whether the collection contains all the elements in the specified collection

    • The isEmpty method returns true if the collection is empty

  • The Collection interface provides the toArray() method, which returns an array of Object for the collection

  • It also provides the toArray(T[]) method, which returns an array of the T[] type

  • A method throws java.lang.UnsupportedOperationException, a subclass of RuntimeException, if some of the methods in the Collection interface can’t be implemented in the concrete subclass

  • All the concrete classes in the Java Collections Framework implement the java.lang.Cloneable and java.io.Serializable interfaces except that java.util.PriorityQueue doesn’t implement the Cloneable interface (all instances of Collection except priority queues can be cloned and all instances of Collection can be serialized)

• 20.3 Iterators

  • Iterator is a design pattern for traversing a data structure w/o exposing the details of how data is stored in that structure

  • The Collection interface extends the Iterable interface

  • The Iterable interface defines the iterator method, which returns an iterator

  • The Iterator interface provides a way for traversing elements in various collections

  • The iterator() method in the Iterable interface returns an instance of Iterator, which provides sequential access to the elements in the collection using the next() method

  • hasNext() method checks whether there are more elements in iterator

  • remove() removes the last element returned by the iterator

• 20.4 Using the forEach Method

  • forEach is a method in the Iterable interface

  • forEach’s argument is an instance of Consumer functional interface

  • Uses accept(E e) method from Consumer to perform an action on element e

  • Using lambda: forEach(e -> System.out.println(e.toUpperCase()))

  • Using anonymous class:

forEach(

   new java.util.function.Consumer<String>() {

      public void accept(String e) {

            System.out.println(e.toUpperCase()); }})

• 20.5.1 Lists (The Common Methods in the List Interface)

  • List interface extends Collection to define an ordered collection w/ duplicates allowed

  • Some Methods of List Interface

    • add(index, element) inserts an element at specified index

    • addAll(index, collection) inserts a collection of elements at specified index

    • remove(index) removes an element at specified index

    • get(index) gets element at specified index

    • set(index, element) sets a new element at specified index

    • indexOf(element) obtains index of specified element’s first occurrence

    • lastIndexOf(element) obtains index of specified element’s last occurrence

    • subList(fromIndex, toIndex) obtains a sublist

    • listIterator() or listIterator(startIndex) returns an instance of ListIterator

  • ListIterator interface extends Iterator interface to add bidirectional traversal of list

  • Some Methods of ListIterator Interface

    • add(element) inserts specified element into list immediately before the next method would be returned by next() in Iterator and after element (if any) was returned by previous() method

    • set(element) replaces last element returned by next or previous w/ specified element

    • hasPrevious() checks whether iterator has more elements when traversed in backward direction (like hasNext() in Iterator)

    • previous() returns previous element in iterator (like next() in Iterator)

    • nextIndex() returns index of next element in iterator

    • previousIndex() returns index of previous element in iterator

  • AbstractList class provides partial implementation of List interface

  • AbstractSequentialList class extends AbstractList to provide support for linked lists

• 20.5.2 Lists (The ArrayList and LinkedList Classes)

  • ArrayList and LinkedList are 2 concrete implementations of List interface

  • If need support random access w/o modifying beginning of list, use ArrayList

  • If need modify beginning of list, choose LinkedList

  • If doesn’t modify at all, use an array

  • ArrayList

    • Resizable-array implementation of List interface

    • Has a capacity that’s always at least as large as the list size

    • As elements are added, capacity grows automatically

    • Does not automatically shrink → use trimToSize() to reduce array capacity to size of list

    • Can be constructed by ArrayList(), ArrayList(Collection), or ArrayList(initialCapacity)

  • LinkedList

    • Linked list implementation of List interface

    • Can be constructed by LinkedList() or LinkedList(Collection)

    • addFirst(), addLast(), getFirst(), getLast(), removeFirst(), and removeLast() are all methods

    • get(i) is available, but is time-consuming *DON’T USE TO TRAVERSE ALL ELEMENTS IN A LIST, USE FOREACH LOOP OR METHOD

  • Lists can hold identical elements

  • Difference b/w 2 is internal implementation

    • LinkedList is good for inserting & removing elements at beginning of list

    • ArrayList is more efficient for all other operations

  • In Arrays class, asList method creates a list from arguments of the type

    • e.g. List<String> list1 = Arrays.asList("red", "green", "blue");

• 20.6 The Comparator Interface

  • Several classes (e.g. String) and wrapper classes for primitives implement Comparable interface, which defines compareTo to compare 2 elements of the same class that implements the Comparable interface

  • If elements’ classes don’t implement Comparable, can define a comparator

  • Can do this by defining class that implements java.util.Comparator<T> interface and overrides its compare method

  • Comparing elements using Comparable is called comparing using natural order

  • Comparing elements using Comparator is called comparing using comparator

  • Comparator is a functional interface, so can use w/ lambda expressions

  • List interface has a sort(comparator) method that can sort elements in a list using a specified comparator (if list.sort(null), sorts using natural order)

  • Can do list.sort(String::compareToIgnoreCase)

    • String::compareToIgnoreCase is called the method reference, which is equal to a lambda expression that the compiler automatically translates to

  • Comparator’s Static Methods

    • comparing(Function<? sup T, ? sup R> keyExtracter) creates a Comparator<T> that compares elements using the key extracted from a Function object. Function’s method apply(T) returns a key of type R for the object T

    • Comparator.comparing creates a Comparator using a property from an object

    • default thenComparing sorts using a primary criteria, second, third, and so far

    • default reversed() reverses the order for a comparator

• 20.7 Static Methods for Lists and Collections

  • These are in Collections class

  • Sort comparable elements using compareTo in Comparable interface

  • May specify a comparator to sort elements

  • To sort list in descending order instead of ascending, use Collections.reverseOrder() method to return a Comparator object that orders the elements in reverse of natural order

  • binarySearch method searches for a key in a list (list MUST be sorted in increasing order)

  • reverse method reverses elements in a list

  • shuffle(List) randomly reorders elements in a list

  • shuffle(List, Random) randomly reorders elements in a list w/ a specified Random object (useful to generate a list w/ identical sequences of elements as original list)

  • copy(det, src) copies all elements from a source list to a destination list on the same index (destination list must be as long or longer than source list)

  • nCopies(int n, Object o) makes an immutable list that has n copies of specified object

  • fill(List list, Object o) replaces all elements in the list w/ specified element

  • max and min methods find maximum and minimum elements in a collection (elements must be comparable using Comparable interface or Comparator interface)

  • disjoint(collection1, collection2) returns true if the two collections have no elements in common

  • frequency(collection, element) finds number of occurrences of the element in the collection

• 20.9 Vector and Stack Classes

  • Vector is same as ArrayList, but it contains synchronized methods for accessing and modifying the vector, which prevents data corruption when multithreading

  • If you don’t require synchronization, should use ArrayList instead

  • Vector class extends the AbstractList class

  • A vector’s methods are similar to methods in List interface

    • addElement(Object element) is similar to add(Object element) except addElement method is synchronized

  • elements() method returns an Enumeration (this interface was superseded by Iterator interface after Java 2)

  • Vector is widely used in Java legacy code

  • Stack is implemented as an extension of Vector in Java Collections Framework

  • Some Stack Methods

    • empty() is same as isEmpty()

    • peek() looks at element at top of stack w/o removing it

    • pop() removes top element from stack and returns it

    • push(Object element) adds specified element to the stack

    • search(Object element) checks whether specified element is in the stack

• 20.10.1 Queues and Priority Queues (The Queue Interface)

  • Queue interface extends Collections

  • Methods

    • offer adds an element to the queue (similar to add; preferred for queues, but add throws an exception IllegalStateException)

    • poll() is similar to remove method but returns null if queue is empty instead of exception

    • peek() is similar to element, but returns null if queue is empty instead of exception

• 20.10.2 Queues and Priority Queues (Deque and LinkedList)

  • LinkedList class implements Deque interface, which extends Queue interface, so you can use LinkedList to create a queue

  • LinkedList is good for queue operations b/c efficient for inserting and removing elements from both ends of a list (deque is short for “double-ended” queue and is usually pronounced “deck”)

  • Methods in Deque

    • addFirst(e)

    • removeFirst()

    • addLast(e)

    • removeLast()

    • getFirst()

    • getLast()

  • PriorityQueue class implements a priority queue

  • By default, a priority queue orders its elements using Comparable/natural order

  • Element w/ least value is assigned highest priority, and thus is removed for queue first

  • If several elements w/ same highest priority, the tie is broken arbitrarily

Can also specify an ordering using Comparator in constructor PriorityQueue(initialCapacity, comparator)