Linked Lists
Site Map Feedback
Download: CList.h (simple example) SList.h (full power List)		Arrays Lists Selection TreeList
	Developing a Fast and useful Linked List

Linked Lists are used for data that needs to be iterated (do something to every Node) and where data may be inserted or deleted at any point.
An example would be a line of text in a text editor: as you type you are inserting characters in a list of characters which, when printed to the screen or printer, are iterated from left to right.
The lines that you aren't currently editing could be arrays because they are not changing, but since you are very likely to do a lot of insertions on the line you are editing, a list is more appropriate.
Think of a paper chain with data written on each link: You could insert a new link in the middle with data on it, or remove a link in the middle easily.

Here's example code for the simplest Linked List Object, the narrative continues in the comments:

struct List { // The List (a struct simply because there are no private members)...
  struct Node { // will create Nodes...
    char c; // which hold data (a character in this case)...
    Node* Next; // and a Pointer to the next Node in the chain (zero means this is the last Node in the chain).
    Node(char c) : c(c), Next(0) {}
  }*First; // The List has a pointer to the First Node in the chain which is zero if the List is empty.
  List() : First(0) {} // First is initialised to zero to indicate an Empty List
  virtual ~List() {Empty();} // Destructor must be virtual since this is likely to be used as a Base Class, and must free the List.
  bool Add(char c) { // To Add data (in this case a character) to the List...
    Node* it=new Node(c); // allocate a new Node
    if(it==0) return false;
    it->Next=First; // Point the new Node's Next pointer to the existing list.
    First=it; // Now The New Node is the First in the List.
  }

  int GetNodeCount() const { // Here's an example of how to iterate the List:
    int NodeCount=0;
    for(Node* it=First; it; it=it->Next) ++NodeCount;
    return NodeCount;
  }
  void Empty() {
    for(Node* it=First; it; it=First->Next) {
      First=First->Next; // Now 'it' holds the First Node, unlink it from the chain
      delete it;
    }
  }
};

A first full example of a fast Linked List class

Since the data the list holds is not known until you use it, structures like Lists use templated types. For the moment that will be ignored and the linked list will be developed into an optimum form.
To get the best balance of speed and usefulness in a List class, it has been found that making the list Circular (so that the last Node Points at the First Node instead of having a zero Next pointer).
CCList is a sorted Circular linked List with WORD Key and serves as the next example.

Algorithmically, this is supposed to be as fast as linked lists get.
The algorithm is the sort of thing used in Assembly Language real time graphics renderers.
If you want a different key type you have to edit the class and adjust SENTINEL appropriately.

Usage:

  CCList CList;     // List={SENTINEL};
  CList.Add(3);     // List={3,SENTINEL};
  CList.Add(13);    // List={3,13,SENTINEL};
  CList.Add(23);    // List={3,13,23,SENTINEL};
  CList.Add(32);    // List={3,13,23,32,SENTINEL};
  CList.Add(3);     // List={3,3,13,23,32,SENTINEL};
  CList.Add(2);     // List={2,3,3,13,23,32,SENTINEL};
  CList.Delete(13); // List={2,3,3,23,32,SENTINEL};
  bool b=CList.Find(23);    // b=true;
  DWORD Key=CList.GetKey(); // Key=23
  b=CList.Next();           // b=true;
  Key=CList.GetKey();       // Key=32
  b=CList.Next();           // b=false;
  CList.Empty();    // List={SENTINEL};

A smart, fast and useful Linked List class

CSList, defined in SList.h,implements a fast and neat singly linked list which may be used for insertion sort or for Queues etc.
The implementation uses a circular list with a dummy Node (with NULL Data pointer) acting as a Terminator at head and tail.
The classes are template-based to allow any type of Data.
Appending to the list is as fast as Adding to the start of the list.
A Count of Nodes is maintained since the overhead during Insertion or deletion is negligible compared to the memory allocation time.
The Iterator class is normally used to access the data in the List class, though access is available to the First Node which is useful for rotating lists or queues without using an iterator at all.
There is also a CSListIteratorAndList class which is handy for quickly creating, iterating and scrapping a list.
Access to the Last node is also immediate and you can Rotate and Reverse the List.
Nodes may be quickly moved from one list to another with the Iterator's MoveTo and InsertInto methods.
One list may hold pointers to data held in another list if it calls DropAll before it is deleted (preventing it from deleting the Data is points to when its destructor is called).
The test classes give usage examples.
These classes have been used every day for years, so they are considered robust. Alterations are posted here promtly.
Note that CSListIterator has only been set up for non-const lists.

If the data class provides a Compare function you can have a sorted list.

class CInteger {
public:
  int i;
  CInteger(int i) : i(i) {}
  int Compare(const CInteger& j) const {return i-j.i;}
};

  CSList<CInteger> List;
  List.Insert(new CInteger(2));
  List.Insert(new CInteger(2)); // Insert allows multiple equal nodes
  List.Insert1(new CInteger(3));
  List.Insert1(new CInteger(3)); // Insert1 keeps the List with unique nodes

You can add nodes to the beginning or end of the list with Add and Append respectively.
For use as a stack or queue you can access the First and Last nodes' data without an iterator.

CSListIterator allows you to iterate a List and access the data at any point, like ForEach, or to Find a node in a sorted list (Created using Insert1 and Nodes with a Compare function).

  CSList<CString> List;
  List.Add(new CString("Hello "));
  List.Add(new CString("world!"));
  CString S;
  for(CSListIterator<CString> it(List); it; ++it) S+=*it;
  ASSERT(S=="Hello World!");

CSListIterator has functions to implement filters such as Move which moves a node to another CSListIterator very quickly.

Doubly-Linked Lists

My Doubly-Linked List class can also behave like a Balance Binary Tree (AVL Tree), so I've put it in the Trees section.

---

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

---