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


An improved doubly linked list system Free Stuff

Abstract

This article presents a C++ doubly linked list system that is based on an earlier article.

1.0 Why use Doubly Linked Lists?

It is natural to ask what is the point of using doubly linked lists when singly linked lists or arrays could be used.

1.1 Singly Linked Lists Versus Doubly Linked Lists

Singly linked lists and doubly linked lists can be efficiently traversed in both the forward and backward* directions. Given a pointer x to a list node, doubly linked lists can in O(1) steps insert and/or delete at x whereas singly linked lists need to search the entire list for the "previous" node therefore taking O(n) steps for the same result. In particular inserting or deleting at the end of the list takes O(1) time for doubly linked lists and O(n) time for singly linked lists. If insertions and/or deletions are done as part of a traversal, then the programmer can keep track of the previous pointer and traverse the singly linked list in the forward direction with optional insertions and/or deletions in O(n) time. Doubly linked lists also take O(n) time for the same operation but do not need the extra complexity of maintaining a previous pointer. Both types of linked lists need a temporary variable when traversing with optional deletions. See below for how to achieve this with doubly linked lists.


For some operations singly linked lists are marginally faster than doubly linked lists, since doubly linked lists have an extra pointer per node (called previous), which means for more pointer manipulations inside the doubly linked list classes. In spite of this extra complexity the difference in terms of big-O notation is zero. Assuming that the extra complexity for the manipulation of doubly linked lists can be subsumed into an abstract data type, then doubly linked lists are simpler than or as simple as singly linked lists.

1.2 Doubly Linked Lists Versus Arrays

The above remarks indicate that doubly linked lists are superior to singly linked lists. What follows is a comparison between doubly linked lists and arrays. Doubly linked lists can be traversed in O(n) time in either direction just like arrays. In addition to this, given a pointer to a node x of a list, insertions and deletions at x can be done in O(1) time. Given an index i of an array insertions and deletions at i take O(n) time.


Doubly linked lists have two disadvantages compared to arrays. Firstly, random access of a list takes O(n) time compared with O(1) time for arrays. This is not a disadvantage if the list can be processed via a traversal which accesses all elements in O(n) time, the same speed as arrays. Secondly, searching for an element in a (singly or doubly) linked list takes O(n) time, whereas searching for an element in a pre-sorted array takes O(log(n)) time.

1.3 Trees Versus Doubly Linked Lists

If fast random access and fast searching is required in addition to fast traversal, insertion and deletion, then the programmer should use AVL trees or one of the other various types of trees. Like doubly linked lists, trees support efficient traversal, insertion and deletion. Like arrays, trees support efficient traversal, random access and searching.

1.4 Detailed Comparison

To support the above remarks, consider the following table that compares the computation times for pre-sorted arrays, singly linked lists, doubly linked lists, and AVL trees:


Pre-sorted ArraysSingly Linked ListsDoubly Linked ListsAVL Trees
Forward Traversal O(n) O(n) O(n) O(n)
Backward Traversal O(n) O(n)* O(n) O(n)
Forward Traversal with
insertions and/or deletions
O(n) * O(n) = O(n2) O(n) O(n) O(n) * O(log(n)) = O(nlog(n))
Insertion or deletion at endO(1) O(n) O(1) O(log(n))
Insertion at a given index/node O(n) O(n) O(1) O(log(n))
Deletion at a given index/node O(n) O(n) O(1) O(log(n))
Random Access O(1) O(n) O(n) O(log(n))
Searching for a given element O(log(n)) O(n) O(n) O(log(n))

NOTE: * indicates that singly linked lists can be traversed in O(n) operations in the backward direction via a stack recursion. With doubly linked lists, backward traversal can be achieved using iteration which is simpler and uses less stack memory than recursion.

1.5 Diagram of Doubly Linked List Classes

This diagram is borrowed from an earlier article.

Doubly Linked Lists diagram

2.0 My Implementation of Doubly Linked Lists

A major change has been made to the Node<X> template class from an earlier article. In the old system the property current was defined to be public of type X like so:

public:
   X current

In the new system, the property current has been renamed to private_data and has been defined to be private of type X* with one setter and two getter methods for getting/setting the value of private_data. Also the property private_dirty is set if a non-const pointer to the list internals is returned or if the list is altered via the set_data() method like so:

private:
   X* private_data;
public:
   const X* get_data_const() const
   {
      return private_data;
   }
   X* get_data()
   {
      private_dirty = true;
      return private_data;
   }
   void set_data(X* x)
   {
      private_dirty = true;
      private_data  = x;
   }

Under the earlier system, the user could choose X to be either a pointer or a non-pointer variable. If the user chose X to be a pointer property variable, then the responsibility for calling operator delete on the current property lies with the user of the doubly linked list system. On the other hand, if the user chose X to be a non-pointer property variable, then the deleting of current is done automatically whenever Node objects are deleted.


Under the new system presented in this article, the property private_data is defined to be of type X*, i.e. a pointer variable. This is a more restrictive system than the previous one as the choice between a pointer or a non-pointer variable no longer exists. The new system has the advantage that three macros of the earlier system: INSTANTIATE_OUTPUT_PROTOTYPE, INSTANTIATE_OUTPUT_DEFINITION and INSTANTIATE_OUTPUT_DEFINITION_STAR are no longer required. There is another advantage of having private_data to be of type X* and that is that the method get_data_const() can be defined as returning a const X*. If private_data was of type X then the method get_data_const() could not be defined like so.

2.1 Why Prefix Private Properties With private_* ?

Using a naming convention like naming certain variables with a prefix enables syntax highlighting to be defined on them using the Emacs text editor.

2.2 An Efficient get_length() Method

Another improvement of the previous system, this system keeps track of the length of the lists in the private property private_length. This property can be returned to the client code by a call to the method get_length(). This allows the list's length to be determined in O(1) time, compared with O(n) time for the previous system.

2.3 The private_dirty Property

Another improvement to the previous system is that the private property variable private_dirty keeps track of whether or not the list has been altered since construction, or since the most recent call to the clear_dirty() method, which sets private_dirty to false. Read access to this property is provided by the get_dirty() method. If get_dirty() returns false, it can be assumed that the list is unchanged and therefore values computed from the list do not need to be recalculated.


However this system is not completely fool-proof. If a non-const pointer to the list internals is returned, followed by a call to the clear_dirty() method, then it is possible for the list internals to be altered while the value of get_dirty() returns false. It is the duty of the client code to make sure this does not happen. Therefore non-const pointers to the list internals should be used with care.

2.4 Iterator Macros

The following macros are defined:


  • for_list (X,cursor,list)
Defines a forward non-const iteration through argument list.
  • for_list_const (X,cursor,list)
Defines a forward const iteration through argument list.
  • for_list_backwards (X,cursor,list)
Defines a backward non-const iteration through argument list.
  • for_list_backwards_const (X,cursor,list)
Defines a backward const iteration through argument list.

Using the above macros, iteration through a linked list is very easy. Example:

int main()
{
   List<int>* list1 = new List<int>();

   // prints out 0 (meaning list1 is not dirty)
   cout << list1->get_dirty() << endl;

   list1->add_element(new int(1));
   list1->add_element(new int(2));
   list1->add_element(new int(3));

   // prints out 1 (meaning list1 is dirty)
   cout << list1->get_dirty() << endl;

   // clears the "private_dirty" flag of list1
   list1->clear_dirty();

   // the following code prints out 1 2 3
   for_list_const (int,n,list1) {
      cout << *n << " ";
   }
   cout << endl;

   // prints out 0 (meaning list1 is not dirty)
   cout << list1->get_dirty() << endl;

   // the following code prints out 3 2 1
   for_list_backwards_const (int,n,list1) {
      cout << *n << " ";
   }
   cout << endl;

   // prints out 0 (meaning list1 is not dirty)
   cout << list1->get_dirty() << endl;

   List<int>* list2 = new List<int>();
   list2->add_element(new int(4));
   list2->add_element(new int(5));
   list2->add_element(new int(6));

   for_list_backwards (int,n,list1) {
      list2->add_to_start(n);
   }

   // prints out 1 (meaning list1 is dirty)
   cout << list1->get_dirty() << endl;

   // prints out 1 (meaning list2 is dirty)
   cout << list2->get_dirty() << endl;

   // clears the "private_dirty" flag of list2
   list2->clear_dirty();

   // prints out 1 2 3 4 5 6
   for_list_const (int,n,list2) {
      cout << *n << " ";
   }
   cout << endl;

   // prints out 0 (meaning list2 is not dirty)
   cout << list2->get_dirty() << endl;

   // deletes all "private_data" fields in list2
   list2->delete_deep();
   // delete all nodes in list2
   delete list2;

   // list1->delete_deep() is not called since
   // all data objects on list1 are also on list2

   // deletes all nodes in list1
   delete list1;
}

2.5 Traversing a Doubly Linked List With Optional Deletions

Traversing a doubly linked list with optional deletions cannot use the above-mentioned iterator macros. Instead a Node<X>* variable (which I will call n_next) is required to store the private_next property in case the current node is deleted.

Node<X>* n_next;
for (Node<X>* n = list->get_first(); n != null; n=n_next) {
   n_next = n->get_next();

   if (/* arbitrary bool valued expression */) {
      delete n;
      // n->get_next() is no longer valid but n_next is valid
   }
}

2.6 Emacs Syntax Highlighting

Add the following lines of Emacs Lisp code to your .emacs file to achieve correct syntax highlighting of the iterator macros:

;; The following code highlights the list iterator macros:

(add-hook 'font-lock-mode-hook 'my-cc--iterator) (defun my-cc--iterator () (if (eq major-mode 'c++-mode) (font-lock-add-keywords nil '( ("\\<for_\\sw*\\>" . font-lock-keyword-face) ) 'APPEND)))

3.0 UML Diagrams

The doubly linked list system is comprised of two main template classes List<X> and Node<X> and four extra template classes: List_Extra<X>, List_Io<X>, List_Operator_Ee<X> and List_Clone<X>. These classes can be instantiated with six lines of code:

template class List<X>;
template class Node<X>;
template class List_Extra<X>;
template class List_Io<X>;
template class List_Operator_Ee<X>;
template class List_Clone<X>;

where X is the argument to the template. The last four classes are collections of friend functions. The reason they have been put in classes is to reduce the number of lines of template instantiation that are required to use the linked list system. If the functions of these four classes had been stand-alone global functions, then one line of template instantiation per function would be required, making the system rather cumbersome to use.


If some of these last four template classes are not required by the client code, then their lines of template instantiation can be omitted, giving the client finely grained control over which functions and/or classes are to be used. Here are the UML diagrams of the above-mentioned classes:

4.0 The Source Code

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:33 NZDT 2016
Best viewed at 800x600 or above resolution.
© Copyright 1999-2016 Davin Pearson.
Please report any broken links to