Previous Section
 < Free Open Study > 
Next Section


5.4 Implementing the Sorted List as a Linked Structure

When writing the array-based implementation of the Sorted List ADT, we found that we had to change only InsertItem and DeleteItem from the Unsorted List versions, but that RetrieveItem could be made more efficient. Because both InsertItem and DeleteItem must search the list, let's look at RetrieveItem first.

The Function RetrieveItem

For the unsorted version, we took the array-based algorithm and changed the array notation to linked notation. Let's try that approach again.

Let's look at this algorithm and be sure that the substitutions do what we want by examining the value of location at the end. There are three cases here instead of two:

  1. location = NULL. If we reach the end of the list without finding an item whose key is equal to item's key, then the item is not in the list. location correctly has the value NULL (see Figure 5.22a, assuming the people's names are in alphabetical order).

  2. item.ComparedTo(location->info) = EQUAL. In this case, we have found the element within the list and have copied it into item (see Figure 5.22b, assuming the people's names are in alphabetical order).

  3. item.ComparedTo(location->info) = LESS. In this case, we have passed the location where the item belongs, so it isn't in the list (see Figure 5.24).

    Click To expand
    Figure 5.24: Retrieving an item that is not there

The first two cases remain the same as for the unsorted list. Figure 5.24 shows the third case.

Having looked at all three cases, we can again code this algorithm, being reasonably confident that it is correct. We use the relational operators here as well.

template <class ItemType>
void SortedType<ItemType>::RetrieveItem(ItemType& item,
     bool& found)
{
  bool moreToSearch;
  NodeType<ItemType>* location;

  location = listData;
  found = false;
  moreToSearch = (location != NULL);

  while (moreToSearch && !found)
  {
    if (location->info < item)
    {
      location = location->next;
      moreToSearch = (location != NULL);
    }
    else if (item == location->info)
    {
      found = true;
      item = location->info;
    }
    else
      moreToSearch = false;
  }
}

The Function InsertItem

We only had to substitute the pointer expressions for the corresponding index expressions in RetrieveItem. Does this technique work for InsertItem? Well, we know that we don't have to shift any elements as we did in an array, so let's make the substitutions up to that point and see.

When we exit the loop, location is pointing to the location where item goes. That's correct. (See Figure 5.24.) We just need to get a new node, put item into the info member, put location into the next member, and put the address of the new node in the next member of the node before it (the node containing Kate). Oops! We don't have a pointer to the node before it. We must keep track of the previous pointer as well as the current pointer. When a similar problem arose with DeleteItem in the unsorted version, we compared one item ahead ((location->next)->info). Can we do that here? No. We could use that technique because we knew that the item for which we were searching was present in the list. Here we know that the item for which we are searching is not in the list. If the new item was supposed to go at the end of the list, this algorithm would crash because location->next would be NULL. (See Figure 5.25.)

Click To expand
Figure 5.25: Inserting at the end of the list

We could change the way of determining moreToSearch, but an easier method for handling this situation exists. We use two pointers to search the list, with one pointer always trailing one node behind. We call the previous pointer predLoc and let it trail one node behind location. When ComparedTo returns GREATER, we advance both pointers. As Figure 5.26 shows, the process resembles the movement of an inchworm. predLoc (the tail of the inchworm) catches up with location (the head), and then location advances. Because no node precedes the first one, we initialize predLoc to NULL. Now let's summarize these thoughts in an algorithm:

Click To expand
Figure 5.26: The inchworm effect

Let's do an algorithm walk-through before we code it. There are four cases: the new item goes before the first element, between two other elements, comes after the last element, or is inserted into an empty list. (See Figure 5.27.) If we insert at the first element (Figure 5.27a), Alex compared to Becca returns LESS, and we exit the loop. We store location into newNode->next and newNode into predLoc->next. Whoops! The program crashes because predLoc is NULL. We must check whether predLoc is NULL, and if it is, we must store newNode into listData rather than predLoc->next.

Click To expand
Figure 5.27: Four insertion cases

What about the in-between case? Inserting Kit (Figure 5.27b) leaves location pointing to the node with Lila and predLoc pointing to the node with Kate. newNode->next points to the node with Lila; the node with Kate points to the new node. That's fine.

What about when we insert at the end? Inserting Kate (Figure 5.27c) leaves location equal to NULL, and predLoc pointing to the node with Chris. NULL is stored in newNode->next; newNode is stored in the next member of the node containing Chris.

Does the algorithm work when the list is empty? Let's see. location and predLoc are both NULL, but we store newNode in listData when predLoc is NULL, so there isn't a problem. (See Figure 5.27d.) Now we can code the function InsertItem.

template <class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
  NodeType<ItemType>* newNode;  // Pointer to node being inserted.
  NodeType<ItemType>* predLoc;  // Trailing pointer.
  NodeType<ItemType>* location; // Traveling pointer.
  bool moreToSearch;

  location = listData;
  predLoc = NULL;
  moreToSearch = (location != NULL);

  // Find insertion point.
  while (moreToSearch)
  {
    if (location->info < item)
    {
      predLoc = location;
      location = location->next;
      moreToSearch = (location != NULL);
    }
    else
      moreToSearch = false;
  }

  // Prepare node for insertion.
  newNode = new NodeType<ItemType>;
  newNode->info = item;
  // Insert node into list.
  if (predLoc == NULL)         // Insert as first.
  {
    newNode->next = listData;
    listData = newNode;
  }
  else
  {
    newNode->next = location;
    predLoc->next = newNode;
  }
  length++;
}

The Function DeleteItem

As in the case of RetrieveItem and InsertItem, the DeleteItem algorithm begins with a search. Here we exit the searching loop when item.ComparedTo(location-> info) returns EQUAL. Once we have found the item, we delete it. Because our precondition states that the item to be deleted is present in the list, we have a choice. We can use the unsorted list algorithm exactly as it is or we can write an algorithm that is the mirror image of the insertion. We leave the coding of the new algorithm to you as an exercise. Figure 5.28 illustrates the four cases that occur.

Click To expand
Figure 5.28: Deleting from a linked list

Comparing Sorted List Implementations

We developed three algorithms for RetrieveItem in an array-based list: a sequential search, a sequential search with an exit when the place is passed where the item would be if present, and a binary search. The first two have order O(N); the binary search has order O(log2N). The first two searches can be implemented in a linked list, but a binary search cannot. (How do you get directly to the middle of a linked list?) Therefore, the array-based algorithm for searching a list works faster than the linked version if we use the binary search algorithm.

In both list implementations, the InsertItem function uses a sequential search to find the insertion position; therefore, the search parts of the algorithms have O(N) complexity. The array-based list must also move down all elements that follow the insertion position to make room for the new element. The number of elements to be moved ranges from 0, when we insert at the end of the list, to length, when we insert at the beginning of the list. Thus the insertion part of the algorithm also has O(N) complexity for the array-based list. Because O(N) + O(N) = O(N), the sequential list's InsertItem operation has O(N) complexity. Even if we used the binary search to find where the item belongs (O(log2N)), the items would have to be moved to make room for the new one (O(N)). O(log2N) + O(N) is O(N).

The insertion part of the algorithm for the linked list representation simply requires the reassignment of a couple of pointers. This makes the insertion task O(1) for a linked list, which is one of the main advantages of linking. However, adding the insertion task to the search task gives us O(N) + O(1) = O(N)-the same Big-O approximation as for the sequential list! Doesn't the linking offer any advantage in efficiency? Perhaps. But remember that the Big-O evaluations are merely rough approximations of the amount of work done by an algorithm.

The DeleteItem function is similar to InsertItem. In both implementations, the search task is performed, an O(N) operation. Then the sequential list's delete operation "deletes" the element by moving up all subsequent elements in the list, which adds O(N). The whole function is O(N) + O(N), or O(N). The linked list deletes the element by unlinking it from the list, which adds O(1) complexity to the search task. The whole function is O(N) + O(1), or O(N). Thus both DeleteItem operations are O(N); for large values of N, they are roughly equivalent.

The fact that two operations have the same Big-O measure does not mean that they take the same amount of time to execute, however. The sequential implementation requires, on average, a great deal of data movement for both InsertItem and DeleteItem. Does all this data movement really make any difference? It doesn't matter too much in our honor roll example; the list is very small. If the honor roll includes 1,000 students, however, the data movement starts to add up.

Table 5.6 summarizes the Big-O comparison of the sorted list operations for sequential and linked implementations.

Table 5.6: Big-O Comparison of Sorted List Operations
 

Array Implementation

Linked Implementation


Class constructor

O(1)

O(1)

Destructor

NA

O(N)

MakeEmpty

O(1)

O(N)

IsFull

O(1)

O(1)

LengthIs

O(1)

O(1)

ResetList

O(1)

O(1)

GetNextItem

O(1)

O(1)

RetrieveItem

   
  • Find

O(N)[*]

O(N)

  • Process

O(1)

O(1)

  • Combined

O(N)

O(N)

InsertItem

   
  • Find

O(N)[*]

O(N)

  • Insert

O(N)

O(1)

  • Combined

O(N)

O(N)

DeleteItem

   
  • Find

O(N)[*]

O(N)

O(N)

O(1)

  • Combined

O(N)

O(N)


[*]O(log2N) if a binary search is used.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)