Most implementations of link lists allocate a single node per record and these nodes are what are linked to each other. This type of algorithm works well when the link list is embedded in the application code, but not when implementing a link list within an API, because it cannot be made reenterant.

A well written Application Programming Interface (API) requires that the functions contained within it be reenterant and also creates an environment in which the code can be abstracted. In order to take advantage of these two ideas the Doubly Linked List (hereafter referred to as the DLL) has a three level hierarchy as pictured in the figure.

The first level we will refer to as the ``Top Level Struct''. All the global data is held by one of these structures and it is allocated once for each incident of the link list.

typedef struct list
   Node           *head;         /* pointer to head record */
   Node           *tail;         /* pointer to tail record */
   Node           *current;      /* pointer to current record */
   Node           *saved;        /* pointer to stored record */
   size_t         infosize;      /* size of record incident */
   unsigned long  listsize;      /* number of records in list */
   unsigned long  current_index; /* index value of current record */
   unsigned long  save_index;    /* index value of stored record */
   DLL_Boolean    modified;      /* modified flag (TRUE or FALSE) */
   DLL_SrchOrigin search_origin; /* location a search originates from */
   DLL_SrchDir    search_dir;    /* direction the search proceeds from */
   } List;

At the next level is the ``Node Struct''. This structure holds the pointer to the actual record data plus the pointers to the next and prior nodes. It is allocated once for each record structure.

typedef struct node
   Info        *info;            /* pointer to record data */
   struct node *next;            /* pointer to next node */
   struct node *prior;           /* pointer to prior node */
   } Node;

Image linklistDiagram

Hierarchical Structure of the Doubly Linked List

The third and final level is the ``Info Struct'', which holds the actual data inserted by the application. The Info Struct is defined by the developer and is only restricted by the environment in which the application runs or is compiled in.

typedef struct your_info
   type your_data;               /* Your data goes here */
   } YourInfo;

There is one more structure which is not part of this hierarchy. It is only used to return the current state of the search criteria.

typedef struct search_modes
   DLL_SrchOrigin search_origin; /* Search from head, tail, or current */
   DLL_SrchDir    search_dir;    /* Search up or down */
   } DLL_SearchModes;

Carl J. Nobile 2007-06-24