I have developed a pair of C++ class templates that enable one to use doubly linked lists without most of the complex and error-prone pointer manipulation that would otherwise be necessary with doubly linked lists.
Doubly linked list. A system that represents a sequence of elements and allows for the efficient insertion and removal of elements at any part of the list. This is often used instead of an array, which lacks this property but instead has the property of efficient random access, something that linked lists lack.
Non-intrusive. The next and previous pointers of the linked list are not part of the data objects in the list, allowing for the possibility of having objects on more than one list at a time. I have borrowed this term from Stroustrup's exposition of linked lists in section 8.3 of his book The C++ Programming Language, second Edition.
Often you have a class whose objects need to belong on various lists. I have devised a pair of template classes that enable you to achieve this goal: List<X> and Node<X>. Objects of the List<X> class denote different lists, for example:
List<X> active_objects; List<X> inactive_objects; List<X> saved_objects; |
defines three lists, active_objects, inactive_objects and saved_objects. An important property of the scheme I have devised is that an object can simultaneously be a member of several different lists. Prior to the this system, I had developed a linked list with the limitation that an object can only be on one list at a time. There were times when this was too restrictive so it led to the improved system described here.
The List<X> class contains two pointers: first and last that point to (respectively) the first and last nodes of the linked list.
The Node<X> class contains pointers to the next and previous node of the list, as well as a current property that points to or stores the current data object.
The first, last, next and previous pointers are never manipulated by the user of the linked list system, for the very point to this system is to eliminate the tiresome pointer manipulation that one often needs when using linked lists, especially doubly linked lists. These pointers are private to the List<X> and Node<X> classes and therefore can only be affected indirectly by calling the public methods.
The current property is publicly available because having it public adds no extra complexity for the user of the system. There is a choice for the user in whether or not the argument X to the template is a pointer or non-pointer variable. If X is a pointer, then the data objects pointed to via the property current could reside on more than one linked list at a time. In this case it is the responsibility of the client to delete the current property when the X objects are no longer required. If X is a non-pointer, then deletions of current are carried out automatically whenever Node<X> objects are deleted. In this case the X objects are only on one list at a time.
Finally, each Node<X> object has an owner pointer that points back to the list that this node is a part of. By following the first, last, next, previous and owner pointers it is possibly to travel backwards and forwards between nodes and lists as the need dictates.
There is no such circularity with the current property however, since each data object referred to by a current is an arbitrary class. It would be up to the user of linked list system to maintain any pointers back to lists or nodes from inside the data objects.
Suppose that the following class is defined:
class X { public: int i; X(int i) { this->i = i; } friend Writer& operator<<(Writer& w, const X& x) { w << x.i; return w; } }; |
Then after inclusion of all necessary header files and instantiation of all necessary templates our main method below can now exercise the functionality of the linked lists:
int main() { List<X*> list1; list1.add(new X(1)); list1.add(new X(2)); list1.add(new X(4)); list1.add(new X(5)); cout << list1 << endl; // prints out "(1 2 4 5)" list1.first()->next()->add(new X(3)); // demonstrates inserting to // the middle of the list. cout << list1 << endl; // prints out "(1 2 3 4 5)" delete list1.first()->current; // deletes X number 1 delete list1.first(); // deletes the node that // was associated with it. cout << list1 << endl; // prints out "(2 3 4 5)" List<X*> list2; // loop adds even X-numbers into list2 for (Node<X*>* p = list1.first(); p != null; p=p->next()) { if (p->current->i % 2 == 0) { list2.add(p->current); } } cout << list2 << endl; // prints out "(2 4)" cout << list1 << endl; // prints out "(2 3 4 5)" // Note that X numbers 2,4 belong to // both lists. List<X*> list3; list3.add(list1.first()->current); // X number 2 is now on three lists: // list1,list2 and list3 cout << list3 << endl; // prints out "(2)" List<X*>* list4 = list1.clone(); // creates a shallow copy of list1,that // is to say the X objects of list1 now // belong to list4 as well. cout << *list4 << endl; // prints out "(2 3 4 5)" delete list4->last()->previous(); // demonstrates removing from the // middle of the list. cout << *list4 << endl; // prints out "(2 3 5)" delete list4; // removes list4 and all its nodes. // The deletion is shallow in the sense // that the X objects are not affected. cout << list1 << endl; // prints out "(2 3 4 5)" // list1 is unaffected by modifications // to the clone list return 0; } |
|
|
||||
|
t-list5.cc | ||||
|
|
||||
|
gccprefs.hh | ||||
|
list1.tar.gz |
| Back to Research Projects |
|
This page has the following hit count:
|
