Doubly Linked Lists and the Abstract Data Type

Experienced C programmers seeking relief from the drudgery of writing linked lists and dealing with the attending problems of keeping them, somehow, isolated from the rest of their code will appreciate this doubly linked list library. Those who are at an earlier stage in their C programming may also find here a useful tool for enhancing their cross-platform programming skills, as this linked list can serve as an example of an abstract data type (ADT).

Using ADTs allows the data in a specific piece of code to be hidden from other pieces of code that don't need and shouldn't have access to it. This is often called modular programming or encapsulation. The idea behind the ADT is to hide the actual implementation of the code, leaving only its abstraction visible. In order to do this, one needs to find a clear division between the linked list code and the surrounding code. When the linked list code is removed, what remains is its logical abstraction. This separation makes the code less dependent on any one platform. Thus, programming using the ADT method is usually considered a necessity for cross-platform development as it makes maintenance and management of the application code much easier.

The ADT concept is developed here via the example of how the doubly linked list Application Programming Interface (API) was created. The doubly linked list (DLL) can also be an independent C module and compiled into a larger program.

The DLL package consists of two C modules: dll_main.c comprises the DLL itself and dll_test.c creates an executable program for testing the DLL's functionality. There are also three header files: dll_main.h is included in dll_main.c, linklist.h is included in your application program, and dll_dbg.h is used for debugging the DLL or the DLL's implementation in your application. A word of warning needs to be expressed here: the header dll_dbg.h should never be compiled into a production program, as doing so circumvents the whole concept of ADT programming. The entire package has been compiled on three platforms with four compilers and includes three of the respective Makefiles. Only one of the platforms exhibited any problem because of a compiler that was not fully ANSI compatible. More will be said about platforms later.

Before we get into the philosophy behind this DLL, I want to explain what my goals were when I decided to write this library. It first had to be platform-independent and instantiable; in other words, the DLL had to handle an unlimited number of instances of linked lists in any one or multiple programs concurrently. Also, it had to be robust.

Figure 1. Layout of Doubly Linked List in memory. The arrows indicate to what the Prior and Next pointers point. The Current pointer can point to any Node Struct, so it is open-ended.

In order to fulfill the first requirement, I decided to strictly adhere to the ANSI C standard, and, with the possible exception of how one sets up one's data and uses the DLL's input/output functions, there should be no endian (byte order) problems. The second requirement was met with the creation of a top-level structure. There is only one of these structures per linked list. It keeps track of the node pointers, the size of the applications data in bytes, how many nodes are in the list, whether or not the list has been modified since it was created or loaded into memory, where searching starts from, and what direction a search proceeds in. Figure 1 illustrates how the top-level structure is integrated into the DLL.

typedef struct list
  {
  Node      *head;
  Node      *tail;
  Node      *current;
  Node      *saved;
  size_t     infosize;
  unsigned long listsize;
  DLL_Boolean  modified;
  DLL_SrchOrigin search_origin;
  DLL_SrchDir  search_dir;
  } List;

This and the next typedef structure remain hidden from the application program. The node pointers mentioned above are defined in the next structure, which includes the pointers to the application's data and the pointers to the next and prior nodes. One of these structures is created for each node in the list.

typedef struct node
  {
  Info    *info;
  struct node *next;
  struct node *prior;
  } Node;

typedef void Info;