Java Collections Library: Lists and Sets

• The learning objective is to understand the basics of the Java Collections library.

Collections

• Storing sets of objects is a common programming need.
• What one does with collections determines the best storage method.
• The Collection framework organizes data aggregation concepts into an inheritance hierarchy.
• Collections are data structures that organize and implement behaviors over data.
• ArrayList is part of Java's Collection framework; use it instead of reinventing an expandable array.

Lists

• Lists store items in a specific order.
• ArrayList stores a list of items in a dynamically sized array and provides speedy access but can spend time resizing.
• LinkedList allows speedy insertion and removal of items but can suffer from "cache" effects.

Sets

• Sets are unordered collections of unique elements.
• Sets offer slower access than ordered sets but faster find operations.
• HashSet uses hash tables for fast finding, adding, and removing elements.
• TreeSet uses a binary tree for fast finding, adding, and removing elements.

Stacks and Queues

• Stacks and queues are designed for specific ways of accessing items.
• A stack is ordered, and elements can only be added to and removed from the top, like a stack of books.
• A queue is ordered, and elements can only be added at the end (tail) and removed from the front (head), like a line of people at a grocery store.

Maps

• Maps are not technically collections, but are an alternative way to store and access items.
• Maps store objects with an associated "key" for access, like barcodes and items.
• Keys are an easy way to represent an object.
• Values are the objects themselves.

Hierarchy Interpretation

• Stack class extends Vector class
• Vector class extends AbstractList, which is an abstract class.
• LinkedList is a class that implements the Deque interface.

Iterable and AbstractCollection

• Java's Collection framework begins with the Iterable interface.
• Collection inherits from Iterable, which is also an interface.
• AbstractCollection is at the top of the Class level, inheriting from Object.

Polymorphism

• The Liskov Substitution Principle states that functions using pointers or references to base classes should be able to use objects of derived classes without knowing it.
• A method with a List parameter will accept objects of any implementing class.
• ArrayList, LinkedList, Vector, and Stack all implement the List interface.
• Polymorphic methods are an important concept in the course.
• Stack, LinkedList, Vector, and ArrayList all implement the List interface.
• They share common operations.