Lists

A list is one of the most basic data structures in programming. It is a logically sequential order of elements, any of which can be accessed without restriction. Any element in the list can be removed, and its value be read or modified. Also, a new element may be inserted into any location in the list structure. Each element points to the next one in the list, and the last does not reference any other item.

Physically, the elements of a list can be stored at various locations in memory, and the addresses of each element are not correlated in any way. The list is linked since each element points to the location of the next item.

The dynamic representation of a list is called a linked list. Each element in the list is called a node, and contains two values. The first, is the data value that is to be stored. For instance, in a list of names, this would be a value such as John. The second value in a node is a pointer to the next node in the list. A common representation of a list node is as follows:

template <class ItemType>
struct ListNode
{
   ItemType data;
   ListNode<ItemType> *next;
};

Linked lists can be implemented in many ways, depending on how the programmer will use lists in their program. We will show how to implement a generic class, which can be adapted and modified to use in most situations. The member functions implemented will be those necessary to add, modify, or delete nodes in a linked list. The class will be constructed in such a way that if the implementation were to be changed, the class definition would remain the same, and therefore any program that uses the class will not need to be altered. This is usually good practice in the design of any class. A definition of the linked list class is displayed below.

template <class ItemType>
class List
{
public:
   List(); //constructor - initialize private variables
   ~List(); //destructor - free used memory
   void insert(const ItemType); //insert new node at current location
   void delete(); //remove the current node
   void next(); //set current to the next node in the list
   void prev(); //set current to the previous node in the list
   void reset(); //set current to the first node in the list
   void clear(); //remove all nodes in the list
   int length() const; //return the amount of nodes in the list
   bool IsEmpty() const; //returns true if the list doesn't have any nodes
   bool IsFull() const; //returns true if there is no system memory for additional nodes
   ItemType value() const; //returns the value of the current node
private:
   ListNode<ItemType> *list; //points to the list header
   ListNode<ItemType> *prevcurrent;
   int len;
}

len will contain the total number of nodes in the list, and is self explanatory. prevcurrent and list will be implemented in a special way, and require further explanation. At first, it would appear logical to have a pointer directly to the node being referenced. However, this would make the implementation of the prev(), as well as the insert() and delete() functions to be time consuming. These three functions require access to the node that precedes the current node being referenced. Therefore, if there were a pointer directly to the required node, the only solution would be to search through the entire list (in the worst case scenario) for the preceding node. A temporary pointer would be created that points to the list's first node, and be used to traverse the list. A condition would then be implemented that triggers when temp->next->data equals the current node's value.

A more efficient approach is to have prevcurrent store the pointer to the node that precedes the one being referenced. Therefore, the time needed to otherwise find this node is not wasted.

This approach raises a new concern - if the list has only one item, then a special case will need to be introduced every place prevcurrent is used, since there is no preceding node to point to. The most efficient way of solving this problem is by using a header node. A header node is a "dummy" node that acts as the first node of the list, but is not logically in the list. It is used only in the implementation of the linked list class, and the programmer who uses the class does not need to know about header nodes. It is created, manipulated, and deleted by the member functions. list will point to header node. Now let's look at the implementation of the linked list class.

The class constructor will create the header node, and set prevcurrent to point to its location. It will also set length to a value of zero.

template <class ItemType>
List<ItemType>::List()
{
   list = new ListNode; //create a new ListNode in memory
   list->next = NULL; //the header is the only node in the list
   revcurrent = list; //set current to the header, since there are no nodes
   len = 0;
}

The destructor will delete all nodes of the list, freeing up the memory they occupied. Since the clear() function does this operation, it can be called in the destructor. In addition, the header node will also be deleted in the destructor, as the clear() function only removes actual list nodes. Two local variables of type ListNode<itemType> are used for the operation. traverse is set to the first node in the list, and used to visit every node. tmp will be used to point to the node to be deleted. Since we cannot move on to the next node if the current node is deleted (the next pointer will no longer exist), traverse will be set to the next node first, after which tmp will be deleted.

template <class ItemType>
void List<ItemType>::clear()
{
   ListNode<ItemType> *tmp; //point to the node to be deleted
   ListNode<ItemType> *traverse = list->next; //used to visit each node in the list. The header node is not deleted, so we start with the first actual node.
   while(traverse != NULL) //while the list is not empty
   {
      tmp = traverse; //store the current node.
      traverse = traverse->next; //visit the next node
      delete tmp; //free the memory taken up by the current node
   }
   prevcurrent = list; //set current to the header node
   len = 0;
}

template <class ItemType<
List<ItemType>::~List()
{
   clear(); //delete all list nodes
   delete list; //delete the header "dummy" node
}

The insert() function will create a new node preceding the one being referenced, and move the reference to it. Remember, current->next is the node currently being referenced, since prevcurrent points to the preceding node.

template <class ItemType>
void List<ItemType>::insert(const ItemType item)
{
   assert(!IsFull()); //abort if there is no memory to create a new node
   ListNode<ItemType> *NewNode = new ListNode<ItemType>; //create a new node in memory
   NewNode->data = item; //set the node's value
   NewNode->next = prevcurrent->next; //referenced node will follow new node in order
   prevcurrent->next = NewNode; //The node that preceded the old node now precedes the new one. The new node is now referenced.
   len++; //increment length
}

The delete() function sets the previous node to point to the node following the one being referenced, thus removing it from the logical list. It is then deleted from memory.

template <class ItemType>
void List<ItemType>::delete()
{
   if(len != 0) //don't delete the header node
   {
      prevcurrent->next = prevcurrent->next->next; //logically remove it from the list
      delete (prevcurrent->next); //free up memory
      len--; //decrement length
   }
}

The next() function is very short, and self explanatory.

template <class ItemType>
void List<ItemType>::next()
{
   prevcurrent = prevcurrent->next;
}

The prev() function visits each node until the one that points to prevcurrent is found, and then sets prevcurrent to this node. The node being referenced now becomes the node prevcurrent pointed to before the function was executed.

template <class ItemType>
void List<ItemType>::prev()
{
   if (len > 1) //run only if there is an element behind the current
   {
      ListNode *tmp = list;
      while(tmp->next != prevcurrent)
      tmp = tmp->next;
      revcurrent = tmp;
   }
}

The reset() function sets the item in reference to the first by setting prevcurrent to the header node.

template <class ItemType>
void List<ItemType>::reset()
{
   prevcurrent = list;
}

Next, the length() function simply returns the value of the private length member len. A function would not be necessary to perform this operation if we were to make the length a public data member, in which case the programmer can read it directly. However, a member function is used to retrieve this value for two reasons. First, if the length data member were public, the programmer could also change the length of the list in the program without modifying the number of nodes in the list. Second, if we were to change the implementation of the class, and the length was no longer controlled by a single variable, the programmer would not have to modify his program in order for it to work.

template <class ItemType>
int List<ItemType>::length() const
{
   return len;
}

The IsEmpty() function works by checking if the length of the list is zero.

template <class ItemType>
bool List<ItemType>::IsEmpty() const
{
   return (len == 0);
}

The IsFull() function checks to see if there is enough system memory to create a new node. This is done by attempting to create a new node, and checking if the resulting pointer is NULL. If the new operation was unsuccessful in assigning the appropriate memory space, NULL is the return value. If the value is not NULL, the memory space is freed, and false is returned. Otherwise, the function returns true, meaning no more items can be added to the list.

template <class ItemType>

bool List<ItemType>::IsFull() const
{
   ListNode<ItemType> *tmp = new ListNode<ItemType>;
   if(tmp == NULL)
      return true;
   else
   {
      delete tmp;
      return false;
   }
}

Finally, the value() function returns the value of the node that is currently being referenced.

template <class ItemType>
ItemType List<ItemType>::value() const
{
   return prevcurrent->next->data;
}

Other Types of Lists

Like header nodes, lists may also have a trailer node, which is a dummy node at the end of the list. They are maintained in a similar fashion to that of header nodes, that is, they are not part of the logical list structure. Header nodes are used to eliminate any special cases that may arise when inserting a new node at the end of the list.

Other type of standard lists exist as well. For instance, in a circular list, the last node points to the first node instead of a NULL value. This would require minor changes in the class implementation. Nodes inserted at the end must now point to the first node, and the same must be done when searching for the last node. We must look for a node which points to the first instead of NULL.

Finally, a doubly linked list maintains a prev pointer in ListNode, which points to the previous node. This makes functions such as insert() and remove() as well as the general implementation very simple. We no longer need to maintain a pointer to the node preceding the one being referenced. Since the previous node is required by both functions, we need only check prev for it. Other modifications needed in order to create a doubly linked list include updating each new node's prev pointer when it is created. The front pointer has a prev value of NULL and requires a special condition, unless a header node or a circular doubly linked list is used.