Doubly Linked Lists and the Abstract Data Type

The ADT concept is at the heart of object-oriented programming and cross-platform development. Mr. Nobile gives us an example with his doubly linked list libraries.
Application Programming Interface

The interface itself follows logically. The first argument of all the DLL's API functions is a pointer of type List. This pointer can easily be changed to different lists, thereby accommodating the instantiation requirement of the DLL.

The API's 25 functions are broken down into seven function groups: three initialization, three status, four data modification, six pointer manipulation, six search, two input/output and one miscellaneous. The initialization group handles the creation, initialization and destruction of the DLL. The status group returns various types of information about the DLL. The pointer manipulation group allows the arbitrary repositioning of the current pointer. The data modification group adds and deletes nodes. The search group returns node information based on keyed data fields or on absolute node position. The input/output group saves or retrieves node data to or from a disk file. The miscellaneous group currently only supports version information.

The function prototypes that follow will return two or more enum types or the boolean type. Some functions have a void return value.

typedef enum
  DLL_NORMAL,       /* normal operation */
  DLL_MEM_ERROR,    /* malloc error */
  DLL_ZERO_INFO,    /* sizeof(Info) is zero */
  DLL_NULL_LIST,    /* List is NULL */
  DLL_NOT_FOUND,    /* Record not found */
  DLL_OPEN_ERROR,   /* Cannot open file */
  DLL_WRITE_ERROR,  /* File write error */
  DLL_READ_ERROR,   /* File read error */
  DLL_NOT_MODIFIED, /* Unmodified list */
  DLL_NULL_FUNCTION /* NULL function pointer */
  } DLL_Return;
typedef enum
  } DLL_Boolean;

What follows is a short description of all the functions in the API. It is not possible to describe all the intricacies of how the functions are called and what they each return in a short article like this. For this information, refer to the documentation and source code in the distribution.


First we need to create a list pointer.

List *listname = NULL;

To create the top-level structure, execute the following function:

List *DLL_CreateList(List **name);
After this structure is created it needs to be initialized using the next function:
DLL_Return DLL_InitializeList(List *list,
 size_t infosize);
That's it—one instance of the DLL is ready to work with; however, there is one last function in this group that is used when we want to permanently remove the list and the top-level structure.
void DLL_DestroyList(List **name);
Notice the pointer to pointer notation again; this is used so that name can be returned as a NULL pointer. The C standard function free does not set the pointer; it is passed to NULL after deallocating its memory. This can cause a possible problem if that pointer should unwittingly be reused.

I've written a template (see Listing 1) of the initialization sequence. This and the source code in the distribution should help in using the DLL.


The next function tests pointers in the top-level structure to determine if there are any nodes in a list.

DLL_Boolean DLL_IsListEmpty(List *list);

The inverse of this function, which follows, creates a new node to see if there is enough memory for a new node. If there is sufficient memory, the temporary node is freed.

DLL_Boolean DLL_IsListFull(List *list);
To get the number of nodes (records) in the list use this next function.
unsigned long DLL_GetNumberOfRecords(List *list);

Data Modification

The process of adding new nodes to the linked list can be as easy or as complex as you desire. The following function has the ability to do an insertion sort as it adds nodes or just stick the nodes on the end. Don't let the list of arguments scare you; the function prototyping makes it look worse than it really is.

DLL_Return DLL_AddRecord(List *list, Info *info,
 int (*pFun)(Info *, Info *));

The first argument is a pointer to the top-level structure, which is the same in all the functions. The second argument is a pointer to the data you want to put into the linked list. The third and last argument points to an optional function that you could write, which determines the sort criteria.

It is worth reviewing how this function should be written, as it shows up again in two other functions described below. It emulates the way the C standard function strcmp returns its value. As a matter of fact, it can be just that.

int compare(Info *newnode, Info *keylist)

Updating the current node (record) is a must in any linked list implementation, and this DLL API is no exception.

DLL_Return DLL_UpdateCurrentRecord(List *list,
 Info *record);
We would also want to delete the current record.
DLL_Return DLL_DeleteCurrentRecord(List *list);
The last function in this group deletes the entire list but not the top-level structure.
DLL_Return DLL_DeleteEntireList(List *list);


Geek Guide
The DevOps Toolbox

Tools and Technologies for Scale and Reliability
by Linux Journal Editor Bill Childers

Get your free copy today

Sponsored by IBM

Upcoming Webinar
8 Signs You're Beyond Cron

Scheduling Crontabs With an Enterprise Scheduler
11am CDT, April 29th
Moderated by Linux Journal Contributor Mike Diehl

Sign up now

Sponsored by Skybot