Previous Section
 < Free Open Study > 
Next Section


5.3 Implementing the Unsorted List as a Linked Structure

Just as in the implementations of the Stack and Queue ADTs, each node in a linked list must have at least two data members. The first contains the user's data; the second acts as a pointer to the next element in the list. To implement the Unsorted List ADT, we need to record two pieces of information about the structure in addition to the list of items. The LengthIs operation returns the number of items in the list. In the array-based implementation, the length member defines the extent of the list within the array. Therefore, the length member must be present. In a link-based list, we have a choice: We can keep a length member or we can count the number of elements each time we call the LengthIs operation. Keeping a length member requires an addition operation each time InsertItem is called and a subtraction operation each time DeleteItem is called. Which option is better? We cannot determine the answer in the abstract; it depends on the relative frequency of use of the LengthIs, InsertItem, and DeleteItem operations. For our example here, let's explicitly keep track of the length of the list by including a length member in the UnsortedType class.

ResetList and GetNextItem require that we keep track of the current position during an iteration, so we need a currentPos member. In the array-based implementation, currentPos is an array index. What is the logical equivalent within a linked list? A pointer. Figure 5.21 illustrates this structure.

Click To expand
Figure 5.21: Honor roll list with two items (ResetList has not been called)

The function headings (prototypes) that complete the specification are identical to those in the array-based implementation. Recall that the specification of the class is the interface seen by the user. The interface documentation tells the user what the operations do, a situation that doesn't change with the implementation. Because the specification was given two chapters ago, we include it in the class documentation.

// Header file for Unsorted List ADT.
template <class ItemType>
struct NodeType;

// Assumption: ItemType is a type for which the operators "<"
//  and "==" are defined-either an appropriate built-in type or
//  a class that overloads these operators.
template <class ItemType>
class UnsortedType
{
public:
  UnsortedType();     // Class constructor.
  ~UnsortedType();    // Class destructor.

  bool IsFull() const;
  // Determines whether list is full.
  // Post: Function value = (list is full).

  int LengthIs() const;
  // Determines the number of elements in list.
  // Post: Function value = number of elements in list.

  void MakeEmpty();
  // Initializes list to empty state.
  // Post:  List is empty.

  void RetrieveItem(ItemType& item, bool& found);
  // Retrieves list element whose key matches item's key
  //  (if present).
  // Pre:  Key member of item is initialized.
  // Post: If there is an element someItem whose key matches
  //       item's key, then found = true and item is a copy
  //       of someItem; otherwise, found = false and item is
  //       unchanged.
  //       List is unchanged.

  void InsertItem(ItemType item);
  // Adds item to list.
  // Pre:  List is not full.
  //       item is not in list.
  // Post: item is in list.

  void DeleteItem(ItemType item);
  // Deletes the element whose key matches item's key.
  // Pre:  Key member of item is initialized.
  //       One and only one element in list has a key matching
  //       item's key.
  // Post: No element in list has a key matching item's key.

  void ResetList();
  // Initializes current position for an iteration through the
  //  list.
  // Post: Current position is prior to first item in list.
  void GetNextItem(ItemType& item);
  // Gets the next element in list.
  // Pre:  Current position is defined.
  //       Element at current position is not last in list.
  // Post: Current position is updated to next position.
  //       item is a copy of element at current position.

private:
  NodeType<ItemType>* listData;
  int length;
  NodeType<ItemType>* currentPos;
};
  

As with the stack and the queue, the UnsortedType class template is preceded by a forward declaration of the NodeType struct. Now we must give the full definition of NodeType:

template<class ItemType>
struct NodeType
{
  ItemType info;
  NodeType* next;
};

From the List ADT implementor's perspective, the algorithms for the list operations are very similar to the ones developed for the sequential (array-based) implementation. To initialize an empty list, we set listData (the external pointer to the linked list) to NULL and set length to 0. Here is the class constructor to implement this operation:

template <class ItemType>
UnsortedType<ItemType>::UnsortedType()   // Class constructor.
{
  length = 0;
  listData = NULL;
}

The IsFull operation is identical to the ones in the Stack and Queue ADTs. We use the operator new to get a node within a try block. If more space is available, we deallocate the node and return an indicator that the list is not full. If no more space is available, an exception is thrown and we return an indicator that there is no more space.

template<class ItemType>
bool UnsortedType<ItemType>::IsFull() const
// Returns true if there is no room for another NodeType object
//  on the free store and false otherwise.
{
  NodeType<ItemType>* location;
  try
  {
    location = new NodeType<ItemType>;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}

As in the array-based implementation, the LengthIs operation just returns the length data member.

template <class ItemType>
int UnsortedType<ItemType>::LengthIs() const
// Post: Number of items in the list is returned.
{
  return length;
}

The Function MakeEmpty

The MakeEmpty operation for a linked list is more complicated than its sequential list counterpart, because the dynamically allocated space used by the elements must be freed, one node at a time. The easiest approach is just to unlink each successive node in the list and free it. As this approach works exactly like our MakeEmpty functions for the Stack and the Queue, we just "borrow" the code, changing the references from topPtr or front to listData. We must also set length to zero.

template <class ItemType>
void UnsortedType<ItemType>::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
  NodeType<ItemType>* tempPtr;

  while (listData != NULL)
  {
    tempPtr = listData;
    listData = listData->next;
    delete tempPtr;
  }
  length = 0;
}

The body of the class destructor is identical to MakeEmpty, with the exception that we do not need to set length to 0. When the list object goes out of scope, all members of the object (including length) are returned to the system to be used again.

The Function RetrieveItem

The algorithm for the linked implementation is the same as the one for the array-based implementation. Given the parameter item, we traverse the list looking for a location where item.ComparedTo (Info(location)) returns EQUAL. The difference is in how we traverse the list and how we access Info(location) to send it as a parameter to ComparedTo. Table 5.4 shows the equivalent expressions for our list design notation using an index and a pointer.

Table 5.4: Comparing List Notation to C++ Code

List Notation

Index Expression

Pointer Expression

Initialize location

location = 0

location = listData

Set location to Next(location)

location++

location = location->next

Have not examined Info(last)

location < length

location != NULL

Info(location)

info[location]

location->info

When we coded the array-based function, we directly substituted the index notation for the list notation. Can we directly substitute the pointer notation for the list notation in the linked list? Let's try it and see. The algorithm follows; the substitutions are marked in boldface for emphasis.

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 two cases:

  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 null pointer value (see Figure 5.22a).

  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).

We can now code this algorithm, being reasonably confident that it is correct. We have a choice: We can write a ComparedTo function that uses "<" and "==", or we can replace the switch statement in the algorithm with an if statement. Because the code within each case is very simple, let's use the relational operators.

Click To expand
Figure 5.22: Retrieving an item in an unsorted linked list
template <class ItemType>
void UnsortedType<ItemType>::RetrieveItem(ItemType& item,
    bool& found)
// Pre:  Key member(s) of item is initialized.
// Post: If found, item's key matches an element's key in the
//       list and a copy of that element has been stored in item;
//       otherwise, item is unchanged.
{
  bool moreToSearch;
  NodeType<ItemType>* location;
  location = listData;
  found = false;
  moreToSearch = (location != NULL);

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

The Function InsertItem

In the array-based implementation, we put the new item at the end because that was the easiest place to put it. What is the analogous place in the linked implementation? At the beginning of the list. Because the list is unsorted, we can put the new item wherever we choose, and we choose the easiest place: at the front of the list. In fact, InsertItem is nearly identical to Push in the linked stack implementation. Note that we are not saying that inserting an item into an unsorted list is the same as pushing an item onto a stack. The unsorted list and the stack are entirely different ADTs. We are saying that the algorithms for the respective operations are the same.

template <class ItemType>
void UnsortedType<ItemType>::InsertItem(ItemType item)
// item is in the list; length has been incremented.
{
  NodeType<ItemType>* location;
  location = new NodeType<ItemType>;
  location->info = item;
  location->next = listData;
  listData = location;
  length++;
}

The Function DeleteItem

To delete an item, we must first find it. In Figure 5.22(b), we see that location points to the node that contains the item for which we are searching, the one to be removed. To remove it, we must change the pointer in the previous node. That is, we must change the next data member of the previous node to the next data member of the one being deleted (see Figure 5.23a).

From the specifications, we know that the item to be deleted is present in the list, so we can change our search algorithm slightly. Rather than compare the item for which we are searching with the information in Info(location), we compare it with Info(location->next). When we find a match, we have pointers to both the previous node (location) and the node containing the item to be deleted (location->next). Note that removing the first node must be a special case because we must change the external pointer to the list (listData). Is removing the last node a special case? No. The next data member of the node being deleted is NULL; it is stored in the next data member of Node(location), where it belongs.

Click To expand
Figure 5.23: Deleting an interior node and deleting the first node
template <class ItemType>
void UnsortedType<ItemType>::DeleteItem(ItemType item)
// Pre:  item's key has been initialized.
//       An element in the list has a key that matches item's.
// Post: No element in the list has a key that matches item's.
{
  NodeType<ItemType>* location = listData;
  NodeType<ItemType>* tempLocation;
  // Locate node to be deleted.
  if (item == listData->info)
  {
    tempLocation = location;
    listData = listData->next;          // Delete first node.
  }
  else
  {
    while (!(item==(location->next)->info))
      location = location->next;

    // Delete node at location->next.
    tempLocation = location->next;
    location->next = (location->next)->next;
  }
  delete tempLocation:
  length--;
}

The Functions ResetList and GetNextItem

The Unsorted List ADT specification defines the "current position" as the location of the last item accessed during an iteration through the list. In the array-based implementation, ResetList initialized currentPos to -1, and GetNextItem incremented currentPos and returned info[currentPos]. For currentPos we used the special value -1 to mean "prior to the first item in the list." In the linked implementation, what special pointer value can we use for "prior to the first item in the list"? The answer: NULL Now ResetList sets the currentPos member to NULL, and GetNextItem sets currentPos either to listData (if currentPos was NULL) or to currentPos->next (if it was not NULL) before returning currentPos->info.

template <class ItemType>
void UnsortedType<ItemType>::ResetList()
// Post: Current position has been initialized.
{
  currentPos = NULL;
}

template <class ItemType>
void UnsortedType<ItemType>::GetNextItem(ItemType& item)
// Pre:   List has not been changed since last call.
// Post:  A copy of the next item in the list is returned.
//        When the end of the list is reached, currentPos
//        is reset to begin again.
{
  if (currentPos == NULL)
    currentPos = listData; 
  else
    currentPos = currentPos->next;
  item = currentPos->info;
}

Recall from the specifications that the body of GetNextItem is not required to check for running off the end of the list. That test is the caller's responsibility. A precondition of GetNextItem is that the item at the current position not be the last in the list. When working with linked lists, however, an error can cause the program to crash with no warning. To avoid this problem, we change the postcondition to show that if the last item has been accessed the list iteration begins again.

We can test the linked implementation of the Unsorted List ADT by using the same test plan that we wrote for the array-based implementation. The test driver and files appear on the Web site.

Comparing Unsorted List Implementations

How do the sequential and linked implementations of the List ADT compare? Just as we did with the Stack and Queue ADT implementations, we look at two factors: the amount of memory required to store the structure and the amount of work done by the solution.

An array variable of the maximum list size requires the same amount of memory, no matter how many array slots are actually used, because we need to reserve space for the largest list possible. The linked implementation using dynamically allocated storage space requires only enough space for the number of elements actually contained in the list at run time. However, as we discussed in detail when evaluating queue implementations, each node element is larger, because we must store the link (the next member) as well as the user's data.

Once again, we use Big-O notation to compare the efficiency of the two implementations. As mentioned before, most of the operations are nearly identical in the two implementations. The class constructor, IsFull, Reset,and GetNextItem functions in both implementations clearly have O(1) complexity. As in the stack and queue operations, MakeEmpty is an O(1) operation for a sequential list but becomes a O(N) operation for a linked list in dynamic storage. The sequential implementation merely marks the list as empty, while the linked implementation must actually access each list element to free its dynamically allocated space.

We did not introduce the concept of an array in dynamic storage until after we discussed the statically allocated array-based list. If the list had been implemented using an array in dynamic storage, a class destructor would have been necessary and would have O(1) complexity. The class destructor for the dynamically linked version has the same complexity as MakeEmpty: O(N).

LengthIs is always O(1) in an array-based implementation, but we have a choice in the linked version. We chose to make it O(1) by keeping a counter of the number of elements we inserted and deleted. If we had chosen to implement LengthIs by counting the number of elements each time the function is called, the operation would be O(N). The moral here is that you must know how LengthIs is implemented in a linked implementation to specify its Big-O measure.

The RetrieveItem operations are virtually identical for the two implementations. Beginning at the first element, they examine one element after another until the correct element is found. Because they must potentially search through all elements in a list, the loops in both implementations are O(N).

Because the list is unsorted, we can choose to put the new item into a directly accessible place: the last position in the array-based implementation or the front position in the linked version. Therefore, the complexity of InsertItem is the same in both implementations: O1). In both implementations, DeleteItem has O(N) complexity because we must search the list to find the item to delete. Table 5.5 summarizes these observations. For those operations that require an initial search, we break the Big-O notation into two parts: the search and what happens after the search.

Table 5.5: Big-O Comparison of Unsorted 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)

Retrieveltem

   
  • Find

O(N)

O(N)

  • Process

O(1)

O(1)

  • Combined

O(N)

O(N)

InsertItem

   
  • Find

O(1)

O(1)

  • Insert

O(1)

O(1)

  • Combined

O(1)

O(1)

DeleteItem

   
  • Find

O(N)

O(N)

  • Delete

O(1)

O(1)

  • Combined

O(N)

O(N)



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