The linked list is one of the simplest structures used in programming. It is frequently used to implement stacks, ordered lists and recently skip lists. One can argue from a purely object-oriented design that these structures are not children of linked list, but should contain a linked list. This arguement can be made by just looking at the insert function for stack. In the stack for example the insert is generally called push. If we do not redefine insert, then someone could destroy the stack by calling insert rather than push. How can we implement these structures in a safe way if we have a linked list defined and want to make use of it.
In a linked list, existing nodes are not reordered in specialized types of lists, the location of insertion (and deletion) are the major changes between a list and an ordered list, a stack or a queue. More complex structures such as trees may have descendents that actually reconstruct parts of the tree. This reconstruction creates other hierarchical difficulties that will be discussed next week.
As in the example of the template class for array, we first list the functions we think we will need. We want this template to have the following general features:
Unlike the array, linked lists are not implemented as a single class. Associated with every linked list there is a list node. These nodes hold the data and maintain the relationship with the rest of the list. Some of the standard functions needed for nodes are:
For any structure in an object-oriented system there should be an iterator. You have seen the array iterator used in a number of places this semester, and it makes sense that our linked list will also have an iterator. In a linked list the iterator takes on new importance since the only location generally available in a linked list it the first location. All other locations must be accessed using an iterator. This will mean that the internal structure of a linked list will be determined by the type of iterator. Our linked list will have an iterator factory.
I implemented this before I used the RcPointer class, so the linked list contains a nested class definition RCPtr. Everything is public, but only to the class List and its decendents. The actual data members are ptrToFirstItem and _size. ptrToFirstItem is never NULL since it is initialized in the constructor for List. The variable _size will always hold the current size of the list.
template < class Type>
class List
{
public:
...
protected:
class RCPtr // This is the counted pointer type used to store the first link
{
public:
RCPtr(){data = NULL;count = 1;}
RCPtr(Link< Type> *p){data = p;count = 1;}
~RCPtr(){}
Link< Type> *data; // actual pointer to first node in list
int count; // how many copies of list are active
};
RCPtr *ptrToFirstItem // pointer to node containing head of the List
int _size; // size of the list
friend class ListIterator< Type>;
};
When designing the interface for linked list, we can list the types of insertion functions we think would be appropriate. The following seem to be fairly commonly used.
You may be able to think of other types of insert, but these are commonly used and other insert functions can be constructed from them. After listing these functions, we should review our list to see if we have listed more than we need. It might be noted that Insert at the beginning is just a special case of insert at a designated position. Why not delete it? The answer is that it is the only insert function listed here that does not require an interator, because it is the only function that doesn't require a list traversal. As you will see, all internal insertions are actually handled by an iterator, and the iterator insert functions use insert at the beginning since they insert at the beginning if the list is empty.
Because of it's central nature let's consider the insert at the beginning function add.
template < class Type>
void List< Type>::add(const Type &val)
{
Link< Type> *p = new Link< Type>(val,ptrToFirstItem->data);
assert(p!=NULL);
ptrToFirstItem->data = p;
_size++;
}
Delete functions are similar to the insert functions and left for the reader to discover!
At this time we need to know about the Link type. One thing you may have noticed, is that Link is not a counted pointer, just a class so p is a standard pointer. We can save some space by just making the first pointer counted and the rest normal. When a list is copied the only thing that happens is an increase in the count of the RcPtr in list. Nodes in the list are not duplicated. This is a considerable savings over using counted pointers throughout the list. One thing that we now have to do is destroy the list when the count in the first node hits zero. This means we need to create a copy constructor, assignment operator and destructor to avoid problems with memory. See the discussion of memory management.
The iterator class is takes charge of operations that do not take place at the beginning of the list. This means Iterator classes determine the global structure of the list. They have access to the beginning of the list and the means they use to traverse the list to a given spot determines where the local Link::insert and Link::delete are going to be applied.
Consider the List::insert function. This function inserts an item if it is not already in the list. An iterator for this list is created by genIterator and the iterator tries to locate the item. If it fails, it the Iterator addBefore function is called.
template <class Type>
int List< Type>::insert(const Type &value)
{
ListIterator< Type>* next = genIterator();
if(!next->locate(value))
{
next->addBefore(value);
delete next; //done with the iterator destroy it.
return 1;
}
delete next;//done with the iterator destroy it.
return 0;
}
The iterator keeps track of its position in the list as it traverses the list. It uses its pointer to the location just before the current position in addBefore function. This pointer is to a link in the list, so a link function is used to make the local connections.
template <class Type>
void ListIterator< Type>::addBefore(const Type &val)
{
if (previous)
{
previous = previous->insert(val);
theList._size++;
}
else
{
theList.List< Type>::add(val);// add at beginning of list
previous = theList.ptrToFirstItem->data;
current = previous->getNext();
}
_pos++;
}
The important thing to remember is that local insertions always look the same, but the locate function may be different for different types of lists. The locate function is what determines the actual point where insertion takes place. In the standard list, you must look until you hit the end of the list to see if an item is present. Notice that we use locate next to do the work.
template <class Type>
int ListIterator< Type>::locate(const Type &val)
{
return locateNextAfter(0,val);
}
template <class Type>
int ListIterator< Type>::locateNextAfter(int after,const Type &val)
{
after++;
if(after <=0 || after > theList._size+1)
{
cerr << "Subscript " << after << " is out of range\n";
return 0;
}
moveTo(after);
while (current)
{
if (current->value() == val)
return _pos;
moveToNext();
}
return 0;
}
In an ordered list the locate function knows when it reaches something larger than the value it is inserting that it will not find the item in the list. In most cases this means that the search ends at someplace other than the end of the list.
templateint OrderedIterator< Type>::locate(const Type &val) { init(); while (current && current->value() <= val) { if (current->value() == val) return _pos; moveToNext(); } return 0; }
Each type of list has its own version of the function genIterator that generates its own type of iterator. All of these functions are similar to that of OrderedList.
template <class Type>
ListIterator< Type>* OrderedList< Type>::genIterator()
{
ListIterator< Type>* returnVal = new OrderedIterator< Type>(*this);
return returnVal;
}
Because the version of genIterator that is called in insert depends on the list (since genIterator is virtual), the insert function is automatically different for different types of list.
List iterators like other types of iterators do much of the dirty work for a structure. This dirty work requires the maintenance of internal pointers. If these pointers are stored directly in list, a function like print which does not alter the data in a list would alter the internal pointers. We would like functions that do not alter data to be const functions, but this is not possible if it alters pointers. In addition there are applications of list that don't need access to any location but the head of the list. In these applications the pointers simply waste space.
template <class Type>
void ListIterator< Type>::moveToNext()
{
previous = current;
current = current->getNext();
_pos++;
}
To get a complete copy of this list click here.
A descendent of list that gives great access time is a skip list. To see how the list given here can be used to create a skiplist click here.