Sorted Lists - Data Structures and Abstractions with Java - page 412

The list now contains
Carlos
Jamie
Sarah

Removing the last entry, To m , did not change the positions of the other entries in the list, but remov-
ing the first entry did. Carlos is now at position 1, instead of 2.

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

Question 2 Assuming that the sorted list you created in the previous question is not empty,
write Java statements that

a. Display the last entry in the sorted list.

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

A Linked Implementation

As with all ADTs, you have a choice of several ways in which to implement the sorted list. You
could store a sorted list's entries in, for example, an array, a chain of linked nodes, an instance of a
vector, or an instance of an ADT list. In this chapter, we will consider a chain of linked nodes and
an instance of an ADT list. In the next chapter, we will use inheritance to develop a completely dif-
ferent implementation.

VideoNote

The class SortedLinkedList

16.7

An outline of the class. An implementation that uses a chain of linked nodes to store the entries in
a sorted list has several details in common with the linked implementation of the ADT list that you
studied in Chapter 14. In particular, it has the same data fields, similar constructors, the same
implementations for several of its methods, and the same definition of the inner class Node . Thus,
we outline in Listing 16-2 a class definition that implements the ADT sorted list.

LISTING 16-2

An outline of a linked implementation of the ADT sorted list

public class SortedLinkedList<T extends Comparable<? super T>>
implements SortedListInterface<T>

{

private Node firstNode; // reference to first node of chain
private int numberOfEntries;

public SortedLinkedList()
{

firstNode = null ;
numberOfEntries = 0;
} // end default constructor

< Implementations of the sorted list operations go here.>
. . .

private class Node
{