Note51

0.1 by Claude 2

14 min read

Chapter 4: Array Implementations of Collection ADTs

Abstract Data Types (ADTs) - Creation Process

Definition

  • An ADT is a data type with characteristics and operations specified without implementation details
  • At this point, the ADT is abstract - focus on what operations do, not how they do them

Causes

  • Not specified in notes

Goals / Objectives

  • Create a specification that describes characteristics and operations without implementation or usage details
  • Separate the interface (what operations do) from implementation (how they do it)

Importance

  • Not specified in notes

Procedures

Step 1: Write the ADT specification

  • Describe characteristics of the data type
  • Define the set of operations for manipulating the data
  • Should not include any implementation or usage details

Step 2: Implement the ADT

  • a. Write a Java interface
    • Include all operations from the ADT specification
    • All methods are abstract methods
  • b. Write a Java class
    • Implements the Java interface from step 2a
    • Determine how to represent the data
    • Implement all operations from the interface
    • Operations include core operations (from specification) and utility operations (private methods to support core operations)

Step 3: Use the ADT in a client program or application

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • Not specified in notes

Examples

  • Not specified in notes

Design Issues for ADT Operations

Definition

  • Special or unusual conditions that must be considered when specifying ADT operations

Causes

  • Operations may not work properly when given invalid positions
  • Operations may not be meaningful on empty collections
  • Collections could become full

Goals / Objectives

  • Decide how to handle special/unusual conditions in ADT specifications
  • Specify how operations handle error situations

Importance

  • ADT specifications should include details on how special conditions are handled by various operations

Procedures

  • Not specified in notes

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • Not specified in notes

Examples

For Lists:

  • add, remove, replace, getEntry work OK when valid position given
  • remove, replace, and getEntry not meaningful on empty lists
  • A list could become full, affecting add operation

Possible Solutions:

  • Assume invalid situations will not occur
  • Ignore invalid situations
  • Make reasonable assumptions, act in predictable way
  • Return boolean value indicating success or failure
  • Throw an exception

Collection ADTs

Definition

  • An ADT that can store a collection of objects
  • A linear collection stores its entries in a linear sequence

Causes

  • Not specified in notes

Goals / Objectives

  • Not specified in notes

Importance

  • Not specified in notes

Procedures

  • Not specified in notes

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • Collections differ in restrictions they place on how entries may be added, removed, or accessed

Examples

  • List
  • Stack
  • Queue

Lists - General Concept

Definition

  • A list provides a way to organize data
  • Items are organized in a sequence

Causes

  • Not specified in notes

Goals / Objectives

  • Not specified in notes

Importance

  • Not specified in notes

Procedures

Operations on Lists:

  • Add new entry (at end or anywhere)
  • Remove an item
  • Replace an entry
  • Get an entry at a specified position
  • Count how many entries
  • Check if list is empty or full

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • Not specified in notes

Examples

  • To-do list with tasks like “Read Chapter 4”, “Call home”, “Buy card for Sue”

Array Implementation of Lists

Definition

  • Implementation where entries in the list have positions beginning with 1 (consistent with typical everyday lists)
  • Uses an array to store list elements

Causes

  • Not specified in notes

Goals / Objectives

  • Implement all list operations using array-based storage

Importance

  • Not specified in notes

Procedures

Data Fields:

  • T[] array - array of list entries
  • int numberOfEntries - current number of entries in the list

Method add(newEntry):

  1. Assign new value at end of array
  2. Increment numberOfEntries

Method add(newPosition, newEntry):

  1. Use utility method makeRoom() to shift elements ahead
  2. Add new entry at specified position

Method remove(givenPosition):

  1. Assign entry at array location to temporary variable (to be returned)
  2. Shift entries from location to avoid gap using removeGap()
    • Exception: when removing last entry
  3. Must handle error situations:
    • Invalid position
    • Empty list
    • Invalid call returns null value

Method replace, getEntry, contains:

  • Algorithms not detailed in notes but mentioned as exercises

Advantages & Disadvantages

Advantages:

  • Retrieving an entry is fast
  • Adding an entry at the end of the list is fast

Disadvantages:

  • Adding or removing an entry between other entries requires shifting elements in the array
  • Increasing the size of the array requires copying elements

Impact / Effect

  • Not specified in notes

Examples

  • Reference to Chapter4\adt\ListInterface.java and ArrayList.java
  • Registration.java (client application)

Generic Types

Definition

  • Used in Java interfaces and classes that implement collection ADTs to specify and constrain the type of objects being stored in the collection
  • The interface/class name is followed by an identifier enclosed in angle brackets (e.g., ListInterface<T>)
  • T represents the data type within the class definition and can be any identifier (usually a single capital letter)

Causes

  • Not specified in notes

Goals / Objectives

  • Specify and constrain the type of objects in a collection
  • Enable type safety without writing separate classes for each data type

Importance

  • Not specified in notes

Procedures

Usage:

  • When using the class, supply an actual type argument to replace T
  • Example: ListInterface<String> taskList;
  • Wherever T appears in the definition, the supplied type (String) will be used

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • A generic type must be a reference type, not a primitive type

Examples

  • public interface ListInterface<T>
  • ListInterface<String> taskList; - now T is replaced with String throughout

Array Expansion (Dynamic Expansion)

Definition

  • The process of moving an array’s contents to a larger array when it becomes full
  • Also called dynamic expansion

Causes

  • An array has a fixed size
  • When array becomes full, need for larger list arises

Goals / Objectives

  • Allow the array-based collection to grow beyond its initial capacity
  • Avoid “full array” limitations

Importance

  • Without expansion, array-based collections would have hard size limits

Procedures

  1. Copy data from original array to new, larger location
  2. Manipulate references so new location keeps name of original array

Utility Methods Needed:

  • isArrayFull() - to determine if array is already full
  • doubleArray() - to expand the array

Implementation:

int[] myArray = new int[INITIAL_SIZE];
int[] oldArray = myArray;  // save reference
myArray = new int[2 * oldArray.length];  // double size
for (int index = 0; index < oldArray.length; index++)
    myArray[index] = oldArray[index];

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • The array can continue to grow as needed
  • Requires copying overhead

Examples

  • Figures 5-6 and 5-7 show the expansion process visually

Array of Object References

Definition

  • An array of objects actually contains references to those objects, not the objects themselves
  • For simplicity, figures often portray arrays as if they actually contained objects

Causes

  • Not specified in notes

Goals / Objectives

  • Not specified in notes

Importance

  • Understanding this distinction is important for proper memory management and understanding of data structures

Procedures

  • Not specified in notes

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • Not specified in notes

Examples

  • Diagrams show array elements pointing to objects (Alice, Bob, Doug, Haley) versus simplified view showing objects directly in array

Stacks - General Concept

Definition

  • A collection where new items are added to the top
  • The item most recently added is always on the top
  • The most recently added item is always the next item to be removed
  • Exhibits LIFO (Last In, First Out) behavior

Causes

  • Not specified in notes

Goals / Objectives

  • Not specified in notes

Importance

  • Not specified in notes

Procedures

Basic Operations:

  • push(newEntry) - add to top
  • pop() - remove from top
  • peek() - view top without removing
  • isEmpty() - check if empty
  • clear() - remove all entries

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • Not specified in notes

Examples

  • Stack of books
  • Stack of plates

Array Implementation of Stacks

Definition

  • Implementation using an array where:
    • Array’s first element represents the bottom of the stack
    • Last occupied location represents the stack’s top
  • This approach avoids shifting elements

Causes

  • Not specified in notes

Goals / Objectives

  • Implement stack operations efficiently using array-based storage

Importance

  • Avoiding element shifts improves performance

Procedures

Data Fields:

  • T[] array - array of stack entries
  • int topIndex - index of top entry (initialized to -1 for empty stack)

Method push(newEntry):

  1. Increment topIndex
  2. Assign new value at array location indicated by topIndex

Method pop():

  1. Assign entry at array location topIndex to temporary variable (to be returned)
  2. Optionally set array[topIndex] to null (for garbage collection)
  3. Decrement topIndex

Method isEmpty():

  • Stack is empty if topIndex equals -1

Array Expansion:

  • Change isFull() to always return false
  • The add() methods will double the size of array when it becomes full
  • Declare private method isArrayFull() called by add() methods

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • Not specified in notes

Examples

  • Reference to Chapter4\adt\StackInterface.java and ArrayStack.java
  • StringReversal.java (client application)
  • Exercise 4.1: convertNumberToBinary(int number) - converts number to binary using a stack

Queues - General Concept

Definition

  • A queue organizes entries according to order of entry
  • Exhibits FIFO (First In, First Out) behavior
  • All additions are at the back of the queue
  • Front of queue has items added first

Causes

  • Not specified in notes

Goals / Objectives

  • Not specified in notes

Importance

  • Not specified in notes

Procedures

Basic Operations:

  • enqueue(newEntry) - add to back
  • dequeue() - remove from front
  • getFront() - view front without removing
  • isEmpty() - check if empty
  • clear() - remove all entries

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • Not specified in notes

Examples

  • People waiting in line for tickets
  • Train cars
  • Ducks in a row
  • Cars at car wash

Array Implementation of Queues - Method 1: Linear Array with Fixed Front

Definition

  • The front of the queue is fixed to queue[0]
  • frontIndex is always 0
  • backIndex initialized to -1 to indicate an empty queue

Causes

  • Not specified in notes

Goals / Objectives

  • Implement queue using straightforward approach similar to how physical queues work

Importance

  • Easy to understand as similar to how people move forward in real queues

Procedures

Data Fields:

  • T[] array - array of queue entries
  • int frontIndex - always 0 (fixed)
  • int backIndex - index of back entry

Method enqueue(newEntry):

  1. Increment backIndex
  2. Assign new value at array location indicated by backIndex

Method dequeue():

  1. Assign entry at array location 0 to temporary variable (to be returned)
  2. Shift entries from array location 1 to backIndex one step towards front
  3. Decrement backIndex

Method isEmpty():

  • Queue is empty if backIndex equals -1

Advantages & Disadvantages

Advantages:

  • Easy to understand as similar to how everyone in queue moves forward a step

Disadvantages:

  • The dequeue operation is inefficient - overhead incurred as must shift entries each time an entry is removed

Impact / Effect

  • Not specified in notes

Examples

  • Not specified in notes

Array Implementation of Queues - Method 2: Linear Array with Dynamic Front

Definition

  • frontIndex is dynamic (not fixed) - it updates/moves instead of shifting elements
  • backIndex initialized to -1; frontIndex initialized to 0

Causes

  • To avoid the inefficiency of shifting entries after each dequeue operation in Method 1

Goals / Objectives

  • Eliminate the overhead of shifting elements on each dequeue

Importance

  • Improves efficiency compared to Method 1

Procedures

Data Fields:

  • T[] array - array of queue entries
  • int frontIndex - index of front entry (dynamic)
  • int backIndex - index of back entry

Method enqueue(newEntry):

  1. Increment backIndex
  2. Assign new value at array location indicated by backIndex

Method dequeue():

  1. Assign entry at array location frontIndex to temporary variable (to be returned)
  2. Increment frontIndex (instead of shifting elements)

Method isEmpty():

  • Queue is empty if backIndex < frontIndex

Advantages & Disadvantages

Advantages:

  • Do not have to shift entries after each dequeue operation

Disadvantages:

  • Rightward drift problem - the array can become “full” when the last array location has been occupied but there are empty locations in the beginning part of the array
  • Question: How to use the empty locations?

Impact / Effect

  • Leads to wasted array space at the beginning
  • Motivates the need for circular array approach (Method 3)

Examples

  • Figure 24-6 shows the array after initially filling and after removing front twice

Array Implementation of Queues - Method 3: Circular Array

Definition

  • When queue reaches end of array, add subsequent entries to beginning
  • Array behaves as though it were circular - first location follows last one
  • backIndex initialized to -1; frontIndex initialized to 0
  • Uses modulo arithmetic to update indices

Causes

  • To solve the rightward drift problem of Method 2
  • To utilize empty locations at the beginning of the array

Goals / Objectives

  • Eliminate wasted array locations
  • Avoid shifting entries after last array location is used
  • Allow the array to “wrap around”

Importance

  • Solves both major problems: shifting overhead and wasted space

Procedures

Data Fields:

  • T[] array - array of queue entries
  • int frontIndex - index of front entry
  • int backIndex - index of back entry

Method enqueue(newEntry):

  1. Update backIndex using modulo arithmetic: backIndex = (backIndex + 1) % array.length
  2. Assign new value at array location indicated by backIndex

Method dequeue():

  1. Assign entry at array location frontIndex to temporary variable (to be returned)
  2. Update frontIndex using modulo arithmetic: frontIndex = (frontIndex + 1) % array.length

Detecting Empty and Full Queues - Problem:

  • With circular array, frontIndex == backIndex + 1 both when queue is empty AND when full

Solution 1: Use a counter

  • Keep track of total entries in queue
  • Empty queue detected when counter is 0
  • Full queue detected when counter equals array length

Solution 2: Leave one unused location

  • Empty queue detected when frontIndex is one location “in front” of backIndex (with wraparound)
  • Full queue detected when only one vacant array location left
  • Queue is empty if: (backIndex + 1) % array.length == frontIndex

Method doubleArray() for Circular Array:

  • Must carefully copy elements maintaining queue order
  • Front elements copied to beginning of new array
  • Adjust indices appropriately

Advantages & Disadvantages

Advantages:

  • No rightward drift problem
  • No wasted array locations
  • Do not have to shift entries after last array location is used

Disadvantages:

  • More complex logic for detecting empty vs full queue
  • Requires modulo arithmetic

Impact / Effect

  • Most efficient array-based queue implementation

Examples

  • Figure 24-7 shows circular array in various states (full, after removals, wrapping around)
  • Figure 24-8 shows seven-location circular array with one unused location
  • Figure 24-9 shows array-based queue operations
  • Figure 24-10 shows doubling the size of array-based queue
  • Reference to Chapter4\adt\QueueInterface.java, ArrayQueue.java, CircularArrayQueue.java
  • SharePortfolio.java and SharePortfolioDriver.java (client applications)

Iterators

Definition

  • An object that enables you to traverse a collection of data, beginning with the first entry
  • Acts like a cursor or pointer, moving about on a data structure and locating individual elements for access
  • A software design pattern that abstracts the process of scanning through a collection of elements one element at a time

Causes

  • Need to go through entries of a collection in order, one at a time

Goals / Objectives

  • Provide a uniform way for traversing elements in various types of collections
  • Enable modification of the list while traversing it

Importance

  • Iteration is such a common operation that Java provides interfaces for it
  • Provides consistent interface across different collection types

Procedures

During one complete iteration:

  • Each entry is considered once

Iterator may be manipulated to:

  • Check whether next entry exists
  • Advance to next entry
  • Get a reference to current entry
  • Modify the list as you traverse it

Java’s Iterator Interface (java.util.Iterator):

  • Specifies a generic type for entries
  • hasNext() - Checks if next entry exists
  • next() - Returns next entry and advances iterator to next entry (throws NoSuchElementException if no more elements)
  • remove() - Removes entry that was returned by last call to next()

Implementation as Inner Class:

  1. Define iterator class as private inner class of the collection ADT
    • Has direct access to ADT’s data fields
  2. Provide public method getIterator() that returns an iterator to the collection
    • Includes call to inner class iterator’s constructor
    • Enables client to create an iterator

Advantages & Disadvantages

  • Not specified in notes

Impact / Effect

  • Not specified in notes

Examples

ArrayQueueIterator (inner class):

private class ArrayQueueIterator implements Iterator<T> {
    private int nextIndex = 0;
    public boolean hasNext() {
        return nextIndex <= backIndex;
    }
    public T next() {
        if (hasNext()) {
            T nextEntry = array[nextIndex];
            nextIndex++;
            return nextEntry;
        } else {
            return null;
        }
    }
}

Public method in ArrayQueue:

public Iterator<T> getIterator() {
    return new ArrayQueueIterator();
}

Sample implementations:

  • Chapter4\adt\QueueInterface.java (with getIterator() method)
  • Chapter4\adt\ArrayQueue.java
  • Chapter4\adt\SharePortfolio.java (with countTotalUnitShares() and getSharePortfolioCapital())
  • Chapter4\client\SharePortfolioDriver.java

Graph View

Backlinks