Doubly Linked Lists Overview

This document is an overview of doubly linked lists.

Purpose

Manipulates a doubly-linked list: an ordered, non-indexed list of elements, that can be traversed in both directions.

The API contains all the necessary functionality for doubly-linked lists. It is possible to derive from its classes to add additional features.

The API has three key concepts: list header (TDblQue), link class (TDblQueLink), and iterator class (TDblQueIter).

General properties

Note the following properties of doubly-linked lists:

the list is circular: the last element points forward to the head element and the head element points back to the last element
elements can be accessed through iterating through the list, and added to the start and end of a list, but not to the middle
elements in a linked list need not be objects of the same type but ought to be derived from the same base class

List header

The list header supplies the behaviour for managing a doubly linked list of objects.

The list header interface is provided by TDblQue <class T>. The T template parameter specifies the type of objects in the list.

Link class

To be a member of a doubly linked list, an object must contain an instance of the link class as a data member.

The link class interface is provided by TDblQueLink.

Iterator class

The iterator class supplies the behaviour for moving through the elements of a list.

The iterator class interface is provided by TDblQueIter.