Java Collections Framework Overview

Overview of Data Structures and Collections

Importance of Data Structures

  • Choosing the best data structures and algorithms is crucial for developing high-performance software.

Definition of Data Structures

  • A data structure is defined as:

    • A collection of data organized in some fashion.

    • It supports operations for accessing and manipulating the data.

  • In an object-oriented context:

    • A data structure is also known as a container or container object.

    • It is an object that stores other objects, referred to as data or elements.

    • Defining a data structure equates to defining a class.

    • A class for a data structure utilizes data fields to store data and provides methods for operations such as search, insertion, and deletion.

Creating Data Structures

  • Creating a data structure involves:

    • Creating an instance from the class.

    • Methods can be applied to the instance for manipulating the data structure (e.g., insertion or deletion).

  • Example:

    • The ArrayList class serves as a data structure for storing elements in a list.

    • The Java Collections Framework offers various data structures for efficient data organization and manipulation (e.g., lists, stacks, queues, priority queues).

Java Collections Framework

Overview

  • The Collection Interface defines common operations for various data structures:

    • Lists, Vectors, Stacks, Queues, Priority Queues, and Sets are all derived from this interface.

  • The framework supports two types of containers:

    • Collection for storing a collection of elements.

    • Map for storing key/value pairs (discussed later).

Types of Collections

  • Sets: Stores a group of non-duplicate elements.

  • Lists: Stores an ordered collection of elements.

  • Stacks: Processes objects in a last-in, first-out manner (LIFO).

  • Queues: Processes objects in a first-in, first-out manner (FIFO).

  • PriorityQueues: Processes objects based on their priority.

  • All these collections share common features defined in interfaces, with implementations provided in concrete classes.

Java Collection Framework Hierarchy

  • Graphical representation of hierarchy:

    • Collection

    • Set

      • NavigableSet

      • SortedSet

      • TreeSet

      • AbstractSet

      • HashSet

      • LinkedHashSet

    • List

      • Vector

      • Stack

      • AbstractList

      • ArrayList

      • LinkedList

      • AbstractSequentialList

    • Queue

      • PriorityQueue

Package Structure

  • All interfaces and classes in the Java Collections Framework are contained within the java.util package.

  • The framework design illustrates the use of:

    • Interfaces: Define the framework.

    • Abstract Classes: Provide partial implementation.

    • Concrete Classes: Fully implement interfaces with specific data structures.

Abstract Classes and User Convenience

  • Abstract classes offer partial implementations for interfaces, allowing users to extend abstract classes rather than implementing all interface methods.

Collection Interface

Role and Functions

  • The Collection Interface is the root interface for manipulating collections of objects.

  • The AbstractCollection class partially implements the collection interface, implementing all methods except for:

    • add, size, and iterator, which are defined in appropriate concrete subclasses.

Query Operations

  • Commonly used methods in the Collection Interface include:

    • size(): returns the number of elements in the collection.

    • contains(o): checks if the collection contains the specified element.

    • containsAll(c): checks if the collection contains all elements in another specified collection.

    • isEmpty(): returns true if the collection is empty.

    • toArray(): returns an array representation of the collection.

Unsupported Operations

  • Some methods may not be implementable in a concrete subclass, causing an UnsupportedOperationException, a subclass of RuntimeException.

  • Implementation example for unsupported method:

  public void someMethod() { 
      throw new UnsupportedOperationException("Method not supported"); 
  }

Java Collection - Queue

Queue Interface

  • The java.util.Queue interface is a subtype of java.util.Collection.

  • Represents an ordered list of objects (similar to a List) but intended for sequential processing:

    • Elements are inserted at the end and removed from the beginning (FIFO}, akin to a bank queue.

Queue Implementations

  • All methods from the Collection interface are available in the Queue interface.

  • Concrete implementations include:

    • java.util.LinkedList: A standard queue implementation.

    • java.util.PriorityQueue: Stores elements in natural order or using a specified comparator.

Creating and Manipulating Queues

Queue Instance Creation

  • Example of creating Queue instances:

  Queue queueA = new LinkedList();
  Queue queueB = new PriorityQueue();

  • Adding elements to a Queue uses the add() method inherited from the Collection interface:

  Queue queueA = new LinkedList();
  queueA.add("element 1");
  queueA.add("element 2");
  queueA.add("element 3");

  • The internal storage order depends on the Queue implementation.

Accessing Elements

  • Access the head of the queue without removal using the element() method:

  Object firstElement = queueA.element();

  • Iterating through all elements instead of processing them individually can be performed via:

    • Iterator method:

  Iterator iterator = queueA.iterator();
  while (iterator.hasNext()) {
      String element = (String) iterator.next();
  }

  • Enhanced for-loop:

  for (Object object : queueA) {
      String element = (String) object;
  }

  • To remove an element from the queue:

  Object firstElement = queueA.remove();