Sorted List (ADT): A collection of objects that maintains data in sorted order.
Unlike the basic ADT List, where entries are ordered by position, here entries are ordered by their value.
Comparable Objects: The objects in the sorted list must be Comparable, meaning they must implement the method compareTo to allow for proper sorting and comparison to determine the correct insertion location.
Causes
Some applications require data to be maintained in a sorted order.
Goals / Objectives
To provide an Abstract Data Type that conveniently maintains its entries in sorted order.
Importance
It is convenient for applications requiring sorted data.
Procedures
Constraints on Operations: A sorted list will not let you add or replace an entry by position, as this could violate the sorted order.
Enforcing Comparability: The requirement for entries to be Comparable is enforced by writing the type parameter as <T extends Comparable<T>>.
Core Operations (from specification):
Add a new entry (maintaining sorted order).
Remove an entry (by value).
Check if a certain value is contained in the list.
Clear the list.
Return the number of entries in the list.
Check if the list is empty.
Advantages & Disadvantages
Advantages:
Not specified in notes
Disadvantages:
Not specified in notes
Impact / Effect
Not specified in notes
Examples
Not specified in notes
Sorted Array List Implementation
Definition
Implementation of the Sorted List ADT using a fixed-size array.
Causes
Not specified in notes
Goals / Objectives
To maintain the sorted order of entries within the array.
Importance
Not specified in notes
Procedures
add(newEntry):
Perform a search (e.g., sequential or binary search) to determine the correct insertion position for newEntry.
Shift all entries from that position onwards down by one index to make room.
Insert the newEntry into the now-empty position.
remove(anEntry):
Perform a search (e.g., sequential or binary search) to find the position of the entry to be removed.
If found, remove the entry.
Shift all subsequent entries up by one index to close the gap.
Advantages & Disadvantages
Advantages:
Binary Search: Can be used on a sorted array to find the position of an entry in O(logn) time, which is much faster than sequential search.
Disadvantages:
Insertion/Removal Time: Operations like add and remove still require shifting elements, leading to a worst-case time efficiency of O(n).
Fixed Size: The implementation is limited by the array’s maximum capacity.
Impact / Effect
The speed advantage gained by using binary search for locating an item is offset by the O(n) time required for element shifting during insertion and removal.
Examples
Sample Code: Mentioned to be available in \Chapter7\adt\SortedArrayList.java.
Sorted Linked List Implementation (Chain of Linked Nodes)
Definition
Implementation of the Sorted List ADT using a chain of linked nodes (a linked list structure).
Causes
To provide a more efficient insertion and removal process compared to array-based shifting.
Goals / Objectives
To implement the Sorted List ADT using nodes that are linked together in sorted order.
Importance
Linked structure avoids the need for massive element shifting during modifications.
Procedures
add(newEntry) (General Logic):
Traverse the chain to find the correct insertion location by comparing the new entry with the data in each node.
The correct location is reached when the current node’s data is greater than the newEntry’s data, or the end of the chain is reached.
Insert a new node containing the newEntry at that location by manipulating the node links (pointers).
add(newEntry) (Recursive Method): Uses recursion to traverse the list and insert the node.
remove(anEntry):
Traverse the chain to find the node containing anEntry.
Once found, remove the node by adjusting the links of the node preceding it.
contains(anEntry): Traverse the list sequentially until anEntry is found or a node with data greater than anEntry is encountered (at which point the search can stop because the list is sorted).
Advantages & Disadvantages
Advantages:
No Shifting: Insertion and removal operations are generally more efficient than in the array implementation because they only involve changing pointers, not shifting data.
Disadvantages:
Search Time: Since linked lists do not support direct index access, the primary method for finding an insertion/removal location is sequential traversal, resulting in O(n) time complexity for add, remove, and contains.
Cannot Use Binary Search: The structure of a linked list prevents the use of O(logn) binary search.
Impact / Effect
Insertion and removal are fast once the location is known, but the overall efficiency is limited by the time spent traversing the list to find the correct location, resulting in O(n) worst-case time for the core modifying operations.
Examples
Recursive Add: Illustrated with examples of adding “Ally” (at the beginning), “Luke” (between existing nodes), and a general case.
Sample Code: Mentioned to be available in \Chapter7\adt\SortedLinkedList.java.
Efficiency Comparison
Definition
A comparison of the worst-case time efficiency (Big O notation) for core operations across array-based list, sorted array, and sorted linked list implementations.
Causes
To analyze and select the most efficient data structure for a given task.
Goals / Objectives
Not specified in notes
Importance
Not specified in notes
Procedures
Not specified in notes
Advantages & Disadvantages
Not specified in notes
Impact / Effect
ADT Sorted List Operation
Array List (Worst Case)
Sorted Array List (Worst Case)
Sorted Linked List (Worst Case)
add(newEntry)
O(n) (Shifting)
O(n) (Search + Shifting)
O(n) (Traversal)
remove(anEntry)
O(n) (Shifting)
O(n) (Search + Shifting)
O(n) (Traversal)
contains(anEntry)
O(n) (Sequential Search)
O(logn) (Binary Search)
O(n) (Traversal)
clear()
O(1)
O(1)
O(1)
getNumberOfEntries()
O(1)
O(1)
O(1)
isEmpty()
O(1)
O(1)
O(1)
Examples
The contains operation is the only one that can achieve better than O(n) time complexity in a sorted array implementation, leveraging the sorted property for O(logn) binary search.