GNU   davin.50webs.com/research
Bringing to you notes for the ages

       Main Menu          Research Projects         Photo Album            Curriculum Vitae      The Greatest Artists
    Email Address       Computer Games          Web Design          Java Training Wheels      The Fly (A Story)   
  Political Activism   Bob Dylan Quotes+       My Life Story          Smoking Cessation          Other Links      
Debugging Macros     String Class I     Linked List System I Java for C Programmers Naming Convention
    String Class II         How I use m4              Strings III                 Symmetrical I/O             Linked Lists II     
Run-Time Type Info   Virtual Methods      An Array System        Science & Religion            Submodes       
  Nested Packages      Memory Leaks    Garbage Collection      Internet & Poverty      What is Knowledge?
Limits of Evolution   Emacs Additions      Function Plotter           Romantic Love        The Next Big Thing
    Science Fiction     Faster Compilation Theory of Morality         Elisp Scoping               Elisp Advice      
  S.O.G.M. Pattern       Safe Properties         School Bullying          Charisma Control          Life and Death    
     Splitting Java          Multiple Ctors       Religious Beliefs         Conversation 1           Conversation 2    
   J.T.W. Language    Emacs Additions II      Build Counter             Relation Plotter          Lisp++ Language  
  Memory Leaks II   Super Constructors CRUD Implementation Order a Website Form There Is An Afterlife
More Occam's Razor C to Java Translator Theory of Morality II


Non-intrusive doubly linked lists in C++ Free Stuff

Abstract

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.

1. Definition of Terms

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.

2. Overview

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.

Doubly linked lists diagram

3. An Example of its use

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;
}
 

4. The Sources

  • Doubly linked list system
  • Interface file:
list.hh
  • Implementation file:
list.ht
  • Some tester code:
   t-list5.cc
  • I/O library:
  • Interface file:
output.hh
  • Implementation file:
output.cc
  • Global header file:
   gccprefs.hh
  • The complete archive:
   list1.tar.gz

Back to Research Projects
This page has the following hit count:
| Main Menu | Research Projects | Photo Album | Curriculum Vitae | The Greatest Artists |
| Email Address | Computer Games | Web Design | Java Training Wheels | The Fly (A Story) |
| Political Activism | Bob Dylan Quotes+ | My Life Story | Smoking Cessation | Other Links |
| Debugging Macros | String Class I | Linked List System I | Java for C Programmers | Naming Convention |
| String Class II | How I use m4 | Strings III | Symmetrical I/O | Linked Lists II |
| Run-Time Type Info | Virtual Methods | An Array System | Science & Religion | Submodes |
| Nested Packages | Memory Leaks | Garbage Collection | Internet & Poverty | What is Knowledge? |
| Limits of Evolution | Emacs Additions | Function Plotter | Romantic Love | The Next Big Thing |
| Science Fiction | Faster Compilation | Theory of Morality | Elisp Scoping | Elisp Advice |
| S.O.G.M. Pattern | Safe Properties | School Bullying | Charisma Control | Life and Death |
| Splitting Java | Multiple Ctors | Religious Beliefs | Conversation 1 | Conversation 2 |
| J.T.W. Language | Emacs Additions II | Build Counter | Relation Plotter | Lisp++ Language |
| Memory Leaks II | Super Constructors | CRUD Implementation | Order a Website Form | There Is An Afterlife |
| More Occam's Razor | C to Java Translator | Theory of Morality II
Last modified: Sun Sep 25 16:11:32 NZDT 2016
Best viewed at 800x600 or above resolution.
© Copyright 1999-2016 Davin Pearson.
Please report any broken links to