3: ADTs Unsorted List and Sorted List

Lists

• list are members of a general category og ADTs called containers
• a list is a homogeneous collection of elements, with a linear relationship between its elements
• the number of items in the list, the lenght of the list, is a property of the list
• a list can be sorted or unsorted
• key: the attributes that are used to determine the logical order of the items on a list
• two basic approaches to implementing container structures such as lists:
  • the "by-copy" approach: when a client program inserts an item into our list, it is actually a copy of the item that is placed on the list; when an item is retrieved from our list by a client program, it is a copy of the item on the list that is returned to the program
  • the "by-reference" approach

   

ADT Unsorted List

• designing an ADT to be used by an application is different from designing an application program to solve a specific problem;
• four categories of operations:
  1. constructors: create a new instance of the data type
     • should be a public method with the same name as the ADT's class name
     • ADT needs one piece of information from the client to construct an instance of the list data type: the maximum number of items to be on the list (this information with vary from application to application, so it is logical for the client to have to provide it. We can also define a default list size to be used in case the client does not provide the information.)
  2. Transformers: operators that change the content of the structure
     • insert transformer
     • delete transformer
     • the insert and delete transformer need, as a parameter, the item to be deleted or inserted
     • a transformer that takes two sorted lists and merges them into one sorted list or appends one list to anoter is called a binary transformer
  3. Observers: ask true/false questions about the ADT, select/access a particular item, return a property pf the structure
     • Our unsorted list ADT needs two observers: isFull and lenghtIs
     • if we know that our ADT is a list of numerical values, we could define statistical observers such as minimum, maximum, average, etc.; But at this point, we know nothing about the type of the item on the list, so we use only general observers
     • operatiosn that allow the client to determine whether an error condition occurs are observers; as we are assuming that out list does not include duplicate elements, we should provide an observer (say, isThere) that seaches the list for an item with a particular key and returns whether or not the item has been found: if(!list.isThere(item)) list.insert(item);
  4. Iterators: are used with composite types to allow the user to process an entire structure component-by-component. We provide two iterators in this case:
     • one to initialize the iteration process (analogous to reset or Open with a file): reset (technically, reset is not an iterator, but an auxiliarry operation that supports iteration)
     • one to return a copy of the next component each time it is called: getNextItem
• so, we have:

Unsorted List ADT Specification

Definitions (provided by user)

maxItems

an integer specifying the maximum number of items to be on the list

Operations (provided by Unsorted List ADT)

void UnsortedStringList(int maxItems)	instantiates this list with capacity of maxItems and initializes this list to empty state Precondition Postcondition
void UnsortedStringList()	instantiates this list with capacity of 100and initializes this list to empty state Precondition Postcondition
boolean isFull()	determines whether this list if full Precondition Postcondition
int lenghtIs()	determines the number of elements on this list Precondition Postcondition
boolean isThere(String item)	determines whether item is on this list Precondition Postcondition
void insert(String item)	Adds copy of item to this list Precondition Postcondition
void delete(String item)	Deletes the element of this list whose key matches item's key Precondition Postcondition
void reset()	initializes current positio for an iteration through this list Precondition Postcondition
String getNextItem()	returns a copy of the element at the current position on this list and advances the value of the current position Precondition Postcondition

* current position is a property of the list

• an alternative to contract programming (in which we provide the ADT user with "tool" like the the isThere() operation with which to adhere to the terms of the contract--the pre- and postconditions) would be to define an error variable, have each operation record whether an error occurs, and provide operations that test this varible
• a third alternative would be to let the operations detect error conditions and throw appropriate exceptions

 

• there are two standard ways to implement a list; we look at a sequential array-based list implementation here
• in the SALI, the elements are stored sequentially, in adjacent slots in an array; the order of the elements is implicit in their placement in the array
• (the second approach, introduced in Ch5, is a linked-list implementation, in which the data elements are not considered to be stored in physically contiguous, sequential order: their order is maintained by explicit links between them

Abstract Classes: Relationship between Unsorted and Sorted Lists

• all the logical operations we defined for the Unsorted List ADT are also needed for the Sorted List ADT; the logical definition of those operations did not rely on whether or not the list was sorted. In fact, the entire specification maybe resuse --, with changes made to the pre- and postconditions of the transformer methods insert and delete (as they are the only methods that affect the underlying ordering of the list items.)
• reuse options:
  1. cut and paste. downside: improvements in implementation of the class would require us to manually make to those changes in the other class
  2. direct inheritance: public class SortedStringList extends UnsortedStringList; redefine the three methods that need to be changed. problem: the relationship between the sorted and unsorted list in not an is a relationship, as called for by the notion of inheritance
  3. abstract classes: (an abstract method is one without a body; an abstract class on the other hand can contain both concrete methods and abstract methods--though it must contain at least one abstract method. To indicate that a class is abstract, we use the keyword abstract in its definition. An abstract class cannot be instantiated; it must be extended by another class, which provides the missing implementation of the abstract methods. So, in our case, we say that the relationship between a sorted list and an unsorted list is that they are both lists; we can then use an abstract class, say Lists, to model the relationship. Specifically, we first create an abstract list class; its concrete methods provide the operations that our two list ADTs share in common, and its abstract methods provide the operations that are not shared. We can then create two concrete classes that extend the abstract list class, one that implements an unsorted list and the other that implements a sorted list. Now we have a more reasonable is-a inheritance structure: an unsorted list is a list and a sorted list is a list.
     • note: since constructors cannot be inherited, we must implement our own constructors for the classes that extend the abstract class

ADT Sorted List

• let us now add an additional property to the the properties of lists discussed previously: the key member of any item (except the last) comes before the key member of the next one. We call a list with this property a sorted list.
• ...notes on implementation of the insert and delete operations...
• improving the isThere operation: there are two ways to improve the searching (isThere) operations over those implemented in the unsorted list.
  • The first way is to stop searching when we pass the place where the item would be if it were in the list and return a value of false.
  • The second way to improve the algorithm is using the binary search approach:
    1. We begin our seach with the whole list to examine: list[0] through list[numItems - 1]
    2. in each iteration we split the current search area in half at the midpoint and if the item is not found there, we search the appropriate half
    3. the part of the list being searched at any time is the current search area; we will be well served to keep track of the boundaries of the current search area with a pair of indexes, first and last.
    4. there are two possible terminating conditions: item is not on the list and item has been found; the first condition occurs when there is no more to search in the current search area, hence we only continue searching if (first <= last). the second terminating condition occurs when item has been found.

     

   

Common Orders of Magnitude

• O(1): bounded time; the amount of work is bounded by a constant and is not dependent on the size of the problem (e.g. assigning a value to the ith element in an array of N elements is O(1) because an array can be assessed directly through its index
• O(log2N): logarithmic time; the amount of work depends on the log of the size of the problem; typically algorithms that successively cut the amount of data to be processed in half at each step (as with binary search)
• O(N): linear time; the amount of work is some constant times the size of the problem (e.g. printing all the elements in a list of N elements, searching for a particular value in a list of unsorted elements because you must potentially search every elemetn on the list to find it)
• O(N log2N): involve applying a logarithmic algorithm N times; the "better" sorting algorithms, such as QuickSort, HeapSort, MergeSort, (Ch10), have N log2 N complexity.
• O(N^2): quadratic time; algorithms that involve applying a linear algorithm N times; include most simple sorting algorithms (Ch 10)
• O(2^N): exponential time: extremely costl: example: salesman problem

Generic ADTs

• The String lists we have created so far are very useful to an applicaiton programming that is creating a system that requires lists of strings. but what if we wanted some other kind of list: a list of integers, a list of dates, a list of circles, a list of real estate information
• a generic data type is one for which the operations are defined but the types of items being manipulated are not; we can make out lists generic by using Java's interface construct
• The Listable Interface
  • to ensure that the objects that we place in out list support necessary methods, we create a Java interface:
    public interface Listable