Sorted Lists Chapter 16 CSISB

Seite 1

Specifications of an Abstract Data Type Sorted List

Duplicate entries are allowed, to make things easier

The sorting must determine where in a list is the element added

Can ask if list contains specified entry

Must be able to remove an entry

What is the Data in Abstract Data Type?

It is a collection of objects in sorted order and having same data type

It is the number of objects in a collection

How can we sort data in Abstract Data Types?

add(newEntry)

remove(anEntry)

getPosition(anEntry)

Operations we use for sorting Abstract Data Type lists

getEntry(givenPosition)

contains(anEntry)

remove(givenPosition)

clear()

getLength()

isEmpty()

toArray()

Seite 2

Suppose that wordList is an unsorted list of words. Using the operations of the ADT list and teh ADT sorted list, create a sorted list of these words.

SortedListInterface sortedWordList = new SortedList();

int numberOfWords = wordList.getLength();

for(int position = 1; position <= numberOfWords; position++)

{

sortedWordList.add(wordList.getEntry(position));

}

Assuming that the sorted list you created in the previous question is not empty, write java statements that display the last entry in the sorted list.

int length = sortedWordList.getLength();

String lastEntry = sortedWordList.getEntry(length);

System.out.println(lastEntry);

Add the sorted list's first entry to the sorted list again

sortedList.add(sortedList.getEntry(1));

In the while statement of the method getNodeBefore, how important is the order of the two boolean expressions that the operator && joins?

The order is critical. When currentNode is null, currentNode != null is false. Thus, the entire expression in the while statement is false without executing the call currentNode.getData(). If the latter call were to execute first when currentNode an exception would occur. Thus, the while statement should remain as written.

What does getNodeBefore return if the sorted list is empty? How can you use this fact to simplify teh implementation of the method add?

When the sorted list is empty, getNodeBefore returns null. Thus, in the definition of add, you can omit the call to isEmpty in the if statement.

Seite 3

Suppose that you use the previous method add to add an entry to a sorted list. If the entry is already in the list, where in the list will add insert it? Before the first occurrence of the entry, after the first occurrence of the entry, after the last occurrence of the entry, or somewhere else?

Before the first occurrence of the entry

What would be the answer to the previous question if you changed > to >= in the while statement of the method getNodeBefore?

After the last occurrence of the entry

The linked implementation of the ADT sorted list, as given in this chapter, does not maintain a tail reference. Why is a tail reference more significant for a linked implementation of the ADT list tha it is for a sorted list?

The method add(newEntry) for a list adds a new entry at the end of the list. A tail reference makes this method O(1) instead of (O(n). For a sorted list, add(newEntry) must traverse the chain to locate the point of insertion. If the insertion is at the end of the chain, the traversal will give you a reference to the last node. A separate tail reference is not needed.

If a sorted list contains five duplicate objects and you use the below method remove to remove one of them, what will be removed from the list: the first occurrence of the object, the last occurrence of the object, or all occurrences of the object?

public boolean remove(T anEntry)

{

boolean result = false;

int position = getPosition(anEntry);

if (position> 0)

{

list.remove(position);

result = true;

}

return result;

}

The first occurrence of the object. Note that getPosition returns the position of the first occurrence of the entry within the list.

Give an advantage and a disadvantage of using composition in the implementation of the class SortedList.

Advantage: The implementation is easy to write.

Disadvantage: The implementation is not efficient when the implementation of the underlying list is linked.