Doubly Linked Lists and the Abstract Data Type

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_FALSE,
  DLL_TRUE,
  } 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);

DLL_Return DLL_InitializeList(List *list,
 size_t infosize);

void DLL_DestroyList(List **name);

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);

unsigned long DLL_GetNumberOfRecords(List *list);

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)
  {
  return(strcmp(newnode->key_element,
  keylist->key_element));
  }

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);

DLL_Return DLL_DeleteCurrentRecord(List *list);

DLL_Return DLL_DeleteEntireList(List *list);