0.3 by Qwen

Chapter 4: Array Implementations of Collection ADTs

General Approach to Implementing ADTs with Arrays

Definition

• A standardized three-step process for creating and using an Abstract Data Type (ADT): specification, implementation (via interface and class), and usage in client programs.

Causes

• Need to separate design from implementation to support abstraction, encapsulation, and code reuse.

Goals / Objectives

• Enable modular, maintainable, and reusable code
• Hide implementation details from users of the ADT

Importance

• Forms the foundation for implementing collection ADTs like list, stack, and queue
• Supports separation of concerns and information hiding

Procedures

• Step 1: Write the ADT specification in natural language—describe data characteristics and operations without implementation details
• Step 2a: Translate the specification into a Java interface containing method declarations
• Step 2b: Write a Java class that:
  • Implements the interface
  • Defines data representation (e.g., array + size tracker)
  • Implements all operations (core and utility methods)
• Step 3: Use the ADT in a client program or application

Advantages & Disadvantages

• Advantages:
  • Promotes code reuse and maintainability
  • Allows implementation changes without affecting client code
• Disadvantages:
  • Not specified in notes

Impact / Effect

• Client programs depend only on the interface, not the implementation
• Bugs or improvements are localized to the implementing class

Examples

• Used as the framework for implementing List, Stack, and Queue ADTs in this chapter

---

List ADT – Array Implementation

Definition

• A linear collection ADT that stores entries in sequence and allows operations like add, remove, replace, and access by position, implemented using an array.

Causes

• Need for an ordered, index-based collection that supports flexible insertion and retrieval

Goals / Objectives

• Provide a reusable, encapsulated list structure
• Support operations at arbitrary positions (not just ends)

Importance

• Lists are fundamental in many applications (e.g., to-do lists, playlists)
• Array implementation offers fast random access

Procedures

• Data fields:
  • T[] array: stores list entries (generic type)
  • int numberOfEntries: tracks current size
• Key methods:
  • add(newEntry): appends to end
  • add(position, newEntry): inserts at given position using makeRoom() to shift elements right
  • remove(position): removes entry and shifts left using removeGap(), returns null on invalid input
  • getEntry(position), replace(position, newEntry), contains(entry), etc.
• Dynamic expansion:
  • When array is full, doubleArray() creates a new larger array and copies contents
  • isArrayFull() checks capacity; isFull() always returns false to support expansion

Advantages & Disadvantages

• Advantages:
  • Fast retrieval by index (O(1))
  • Efficient appending at end (O(1) amortized with expansion)
• Disadvantages:
  • Insertion/removal in middle requires shifting elements (O(n))
  • Array expansion requires copying all elements (O(n))

Impact / Effect

• Enables flexible list usage but with performance trade-offs for mid-list operations
• Dynamic expansion avoids hard size limits but adds occasional overhead

Examples

• Sample code: ListInterface.java, ArrayList.java
• Client applications: Registration.java (Chapter4\client)
• Real-world analogy: to-do list (Fig. 4-1)

---

Stack ADT – Array Implementation

Definition

• A LIFO (Last-In-First-Out) collection ADT where elements are added and removed only from the top, implemented using an array.

Causes

• Need for a restricted-access collection that supports undo, parsing, or backtracking behavior

Goals / Objectives

• Provide efficient push and pop operations
• Maintain LIFO discipline through encapsulation

Importance

• Used in algorithms requiring reversal or nested processing (e.g., expression evaluation, recursion simulation)

Procedures

• Data fields:
  • T[] array: stores stack entries
  • int topIndex: index of top entry; initialized to -1 for empty stack
• Key methods:
  • push(newEntry): increment topIndex, assign to array[topIndex]
  • pop(): retrieve array[topIndex], set array[topIndex] = null, decrement topIndex
  • peek(): return top without removal
  • isEmpty(): check if topIndex == -1
• Design choice: top grows upward from index 0 to avoid shifting

Advantages & Disadvantages

• Advantages:
  • All core operations are O(1)
  • Simple and memory-efficient
• Disadvantages:
  • Fixed initial size (unless expanded, though not detailed in notes)
  • No access to non-top elements

Impact / Effect

• Enables efficient reversal and depth-first processing
• Ideal for temporary storage with strict access rules

Examples

• Converting decimal to binary: push remainders, then pop to build string
• Sample code: StackInterface.java, ArrayStack.java, StringReversal.java

---

Queue ADT – Array Implementation (Three Variants)

Definition

• A FIFO (First-In-First-Out) collection ADT where elements are added at the back and removed from the front, implemented using arrays in three ways: fixed front, dynamic front, and circular.

Causes

• Need for ordered processing (e.g., task scheduling, request handling)

Goals / Objectives

• Support efficient enqueue and dequeue operations
• Minimize wasted space and shifting overhead

Importance

• Essential for modeling real-world queues (e.g., print jobs, customer service lines)

Procedures

Variant 1: Linear Array with Fixed Front

• Data fields: frontIndex = 0 (fixed), backIndex = -1 (empty)
• enqueue(): increment backIndex, assign value
• dequeue(): return array[0], shift all elements left, decrement backIndex

Variant 2: Linear Array with Dynamic Front

• Data fields: frontIndex and backIndex both dynamic
• enqueue(): increment backIndex, assign
• dequeue(): return array[frontIndex], increment frontIndex
• isEmpty(): backIndex < frontIndex

Variant 3: Circular Array

• Data fields: same as Variant 2, but indices wrap using modulo
• enqueue(): backIndex = (backIndex + 1) % length, assign
• dequeue(): return array[frontIndex], frontIndex = (frontIndex + 1) % length
• Empty/full detection solutions:
  1. Use a counter for number of entries
  2. Leave one array slot unused; full when (backIndex + 1) % length == frontIndex is false but next would be true

Advantages & Disadvantages

• Advantages:
  • Circular array avoids “rightward drift” and wasted space
  • Dynamic front avoids shifting on dequeue
• Disadvantages:
  • Fixed front: inefficient dequeue (O(n) due to shifting)
  • Dynamic front: wasted space after repeated enqueues/dequeues
  • Circular array: complex empty/full detection

Impact / Effect

• Choice of implementation affects performance and memory usage
• Circular array is most space-efficient for long-running queues

Examples

• Figures 24-6 to 24-10 illustrate queue states during operations
• Sample code: QueueInterface.java, ArrayQueue.java, CircularArrayQueue.java
• Client: SharePortfolioDriver.java

---

Iterators for Array-Based Collections

Definition

• An iterator is an object that enables sequential traversal of a collection’s elements, abstracting the internal structure.

Causes

• Need to access all elements of a collection without exposing internal representation

Goals / Objectives

• Provide uniform traversal mechanism across different collection types
• Allow safe, controlled access during iteration

Importance

• Supports the Iterator design pattern
• Enables use with Java’s enhanced for-loops and standard libraries

Procedures

• Implemented as an inner class within the collection class (e.g., ArrayQueueIterator)
• Uses a cursor (e.g., nextIndex) to track current position
• Implements java.util.Iterator<T> interface with:
  • hasNext(): checks if more elements exist
  • next(): returns current element and advances cursor
  • remove(): removes last-returned element (optional)
• Collection class provides getIterator() method that returns a new iterator instance

Advantages & Disadvantages

• Advantages:
  • Encapsulates traversal logic
  • Gives client read (and possibly modify) access without exposing array
• Disadvantages:
  • Not specified in notes

Impact / Effect

• Decouples collection structure from traversal logic
• Enables consistent iteration across lists, queues, stacks, etc.

Examples

• ArrayQueue includes inner class ArrayQueueIterator
• QueueInterface declares getIterator() method
• Used in SharePortfolio to compute total shares or capital value

---

Generic Types in Collection ADTs

Definition

• A Java feature allowing classes and interfaces to operate on objects of various types while providing compile-time type safety.

Causes

• Need to create reusable collection classes that work with any reference type

Goals / Objectives

• Avoid casting and runtime errors
• Enable type-specific operations at compile time

Importance

• Critical for building flexible, type-safe data structures

Procedures

• Declare interface/class with type parameter: public interface ListInterface<T>
• Use T as placeholder for element type in method signatures and fields
• Instantiate with concrete type: ListInterface<String> taskList = new ArrayList<String>();
• Note: T must be a reference type (not primitive)

Advantages & Disadvantages

• Advantages:
  • Type safety without explicit casting
  • Code reuse across data types
• Disadvantages:
  • Not specified in notes

Impact / Effect

• Enables one implementation (e.g., ArrayList) to work with String, Integer, custom objects, etc.

Examples

• ListInterface<T>, StackInterface<Integer>, ArrayQueue<T>
• T[] array used in all array-based collection classes