Chapter 7: Sorted Lists

Introduction to Sorted Lists

Definition

An Abstract Data Type (ADT) that maintains data in sorted order
A collection where entries are ordered by their values rather than by their positions (unlike regular ADT list)

Causes

Some applications require sorted data rather than position-based ordering
Need for maintaining data automatically in sorted order

Goals / Objectives

To provide a convenient ADT that maintains data in sorted order automatically
To allow operations on sorted collections without manual sorting

Importance

Convenient for applications that require sorted data
Automatically maintains sort order, reducing programmer burden
Enables efficient searching and ordered data access

Procedures

Not specified in notes

Advantages & Disadvantages

Advantages:
- Automatically maintains sorted order
- Convenient for applications requiring sorted data
Disadvantages:
- Does not allow adding or replacing entries by position (unlike regular list)
- Must sacrifice position-based operations to maintain sort order

Impact / Effect

For ADT list, entries are ordered simply by their positions
For sorted list, entries are ordered by their comparable values
Changes the fundamental operations available (no position-based add/replace)

Examples

Not specified in notes

Specifications for the ADT Sorted List

Definition

An ADT with specific data requirements and operations designed for maintaining sorted collections

Causes

Need for a formal specification to implement sorted list functionality

Goals / Objectives

To define the data and operations required for a sorted list
To establish a clear interface for sorted list implementations

Importance

Provides clear contract for implementations
Ensures consistent behavior across different implementations
Defines what operations are supported and what are intentionally excluded

Procedures

Refer to Appendix 7.1 for complete ADT Sorted List specifications

Advantages & Disadvantages

Not specified in notes

Impact / Effect

A sorted list will not let you add or replace an entry by position (key restriction)
Must work with entries based on their comparable values, not positions

Examples

Data:

A collection of objects in sorted order, same data type
The number of objects in the collection

Operations:

Add a new entry
Remove an entry
Check if a certain value is contained in the list
Clear the list
Return the number of entries in the list
Check if list is empty

Comparing Entries

Definition

The requirement that objects in a sorted list must be able to be compared to determine their relative order
Objects must implement the Comparable interface and the compareTo method

Causes

Need to determine the correct location to insert a new entry
Cannot maintain sorted order without ability to compare entries

Goals / Objectives

To ensure entries can be ordered properly
To enable automatic placement of new entries in correct sorted position

Importance

Essential for maintaining sorted order
Required for all sorted list operations to function correctly
Enforces type safety through generic type constraints

Procedures

Objects in the sorted list must be Comparable
Must implement the compareTo method
To enforce this requirement, use the generic type declaration: <T extends Comparable<T>>

Advantages & Disadvantages

Advantages:
- Ensures all entries can be compared
- Provides compile-time type safety
- Enables automatic correct placement of entries
Disadvantages:
- Restricts what types can be stored (only Comparable types)
- Requires implementing Comparable interface for custom classes

Impact / Effect

Entries must implement compareTo to be usable in sorted list
Generic type constraint enforces this requirement at compile time

Examples

Generic type declaration in interface header: <T extends Comparable<T>>
Generic type declaration in class header: <T extends Comparable<T>>

Sorted Array List Implementation

Definition

An implementation of the ADT sorted list using an array as the underlying data structure

Causes

Need for a concrete implementation of the sorted list ADT
Arrays provide one way to store sorted collections

Goals / Objectives

To implement the sorted list interface using array-based storage
To provide all operations specified in SortedListInterface

Importance

Provides a working implementation of sorted list
Demonstrates array-based approach to maintaining sorted order

Procedures

Sample code in \Chapter7\adt folder
Key files:
- SortedListInterface.java (interface)
- SortedArrayList.java (implementation)
- SortedArrayListDriver.java (test driver)

Advantages & Disadvantages

Not specified in notes

Impact / Effect

Generic type declaration in class header: <T extends Comparable<T>>
Array construction uses special syntax: list = (T[]) new Comparable[initialCapacity];
This construction is necessary because the generic type enforces that entries are Comparable

Examples

Note the generic type declaration in the interface header: <T extends Comparable<T>>
Note the new statement to construct the array in the constructor: list = (T[]) new Comparable[initialCapacity]; because the generic type enforces the requirement that the entries are Comparable

Sorted Linked List Implementation

Definition

An implementation of the ADT sorted list using a chain of linked nodes as the underlying data structure

Causes

Need for an alternative implementation approach to array-based sorted list
Linked structures offer different performance characteristics

Goals / Objectives

To implement the sorted list interface using linked node storage
To provide all operations specified in SortedListInterface

Importance

Provides alternative implementation with different trade-offs
Demonstrates linked structure approach to maintaining sorted order

Procedures

Sample code in folder \Chapter7\adt
Key file: SortedLinkedList.java
Also uses: SortedListInterface.java

Advantages & Disadvantages

Not specified in notes

Impact / Effect

For add() method: If list is in ascending order, insert new entry just before first entry not smaller than new entry

Examples

SortedLinkedList.java implementation file

The Method add (Linked Implementation)

Definition

The operation to add a new entry to a sorted linked list while maintaining sorted order

Causes

Need to insert entries at correct position to maintain sort order
Must handle various insertion points: beginning, middle, or end of chain

Goals / Objectives

To insert new entry at correct position in sorted chain
To maintain sorted order after insertion
To handle all possible insertion positions correctly

Importance

Core operation for sorted list functionality
Must preserve sorted order of all entries
Critical for maintaining the sorted list invariant

Procedures

If list is in ascending order, insert new entry just before first entry not smaller than new entry
Use recursive approach to traverse and find insertion point
Handle different cases: insert at beginning, between nodes, or at end

Advantages & Disadvantages

Not specified in notes

Impact / Effect

Maintains sorted order automatically
Requires traversal to find correct insertion point
Different insertion points require different pointer adjustments

Examples

Insertion points (Fig. 13.1):

Ally < Bob: insert before Bob (at beginning)
Cathy < Jill: insert before Jill
Luke < Mike: insert before Mike
Sue == Sue: insert at Sue’s position
Tom > Sue: insert after Sue (at end)

Recursive insertion of “Luke” (Fig. 13.2):

First call: Luke > Bob, so add Luke to rest of chain
Second call: Luke > Jill, so add Luke to rest of chain
Third call: Luke < Mike, so add Luke here at beginning of rest of chain

Adding “Ally” at beginning (Fig. 13.3):

(a) List before additions: Bob → Jill → Mike → Sue
(b) add(“Ally”, firstNode) begins execution, currentNode points to firstNode
(c) New node created (base case), currentNode points to Ally node
(d) Returned reference assigned to firstNode, Ally now first node

Adding “Luke” between nodes (Fig. 13.4):

(a) add(“Luke”, firstNode) begins execution, currentNode = firstNode
(b) Recursive call with currentNode.getNextNode() (Jill node), currentNode = Jill
(c) Recursive call with currentNode.getNextNode() (Mike node), currentNode = Mike
(d) New node created (base case), currentNode points to Luke
(e) Returned reference assigned to nodeAfter
(f) currentNode.setNextNode(nodeAfter) executes, Luke inserted between Jill and Mike

Efficiency of Sorted List Implementations

Definition

Analysis of the worst-case time complexity for operations on sorted lists using array and linked implementations

Causes

Need to understand performance characteristics of different implementations
Must evaluate efficiency to make informed implementation choices

Goals / Objectives

To compare efficiency of array-based and linked-based implementations
To identify which operations are more or less efficient in each approach

Importance

Helps choose appropriate implementation for specific use cases
Reveals performance trade-offs between implementations
Critical for understanding scalability

Procedures

Analyze worst-case time complexity for each operation
Express efficiency using Big O notation
Compare array and linked implementations

Advantages & Disadvantages

Advantages:
- Both implementations have O(1) operations for: clear(), getNumberOfEntries(), isEmpty()
Disadvantages:
- Both implementations have O(n) operations for: add(newEntry), remove(anEntry), contains(anEntry)
- No significant efficiency advantage of one implementation over the other for core operations

Impact / Effect

Array and linked implementations have identical worst-case efficiencies for all operations
Both require linear time for add, remove, and contains operations
Both achieve constant time for utility operations

Examples

Worst-case efficiencies (Fig. 13.5):

ADT Sorted List Operation	Array	Linked
add(newEntry)	O(n)	O(n)
remove(anEntry)	O(n)	O(n)
contains(anEntry)	O(n)	O(n)
clear()	O(1)	O(1)
getNumberOfEntries()	O(1)	O(1)
isEmpty()	O(1)	O(1)