Doubly Linked Lists and the Abstract Data Type

As shown above, there are four pointers in the top-level structure. We concern ourselves here with the current pointer. This pointer is where all the power in the DLL comes from and is used in many of the DLL's functions to determine what to work on.

The next two functions move the current pointer to the head or tail of the list.

DLL_Return DLL_CurrentPointerToHead(List *list);
DLL_Return DLL_CurrentPointerToTail(List *list);

Often, incrementing or decrementing the pointer is necessary:

DLL_Return DLL_IncrementCurrentPointer(List *list);
DLL_Return DLL_DecrementCurrentPointer(List *list);

It is sometimes desirable to store the current pointer, then do something else, and then restore the pointer. We take care of this in the next two functions.

DLL_Return DLL_StoreCurrentPointer(List *list);

DLL_Return DLL_RestoreCurrentPointer(List *list);

There is little use having a linked list if you cannot find what has been stored in it. The following functions let you find your data and specify exactly how that data will be found.

DLL_Return DLL_FindRecord(List *list, Info *record,
        Info *match, int (*pFun)(Info *, Info *));

The first argument, as usual, is the pointer to the linked list. The second is a pointer to the returned data. The third is a pointer to the matching criteria, and the last argument is a pointer to the compare function that was previously described in the data modification group. This compare function can be constructed differently, but the idea is the same.

Now life gets a little difficult. The above function needs to know how to look for the data in the linked list. Does it look down from the head pointer, up from the tail pointer, or up or down from the current pointer? My solution to this problem was to use a state table.

There are two more typedef enumerations needed, relating to the state table, one to set the origin of the search and the other to set its direction.

typedef enum
  {
  DLL_ORIGIN_DEFAULT,  /* Use current origin
                        * setting */
  DLL_HEAD,    /* Set origin to head pointer */
  DLL_CURRENT, /* Set origin to current pointer */
  DLL_TAIL     /* Set origin to tail pointer */
  } DLL_SrchOrigin;
typedef enum
  {
  DLL_DIRECTION_DEFAULT, /* Use current direction
                          * setting */
  DLL_DOWN,    /* Set direction to down */
  DLL_UP,      /* Set direction to up */
  } DLL_SrchDir;

The state table defaults at initialization to DLL_HEAD and DLL_DOWN. The DLL_FindRecord function uses these values if not changed. To change the operation of this function, use the next two functions shown. If no change is desired in either of these two functions, use DLL_ORIGIN_DEFAULT or DLL_DIRECTION_DEFAULT. The first function sets the table to new values:

DLL_Return DLL_SetSearchModes(List *list,
        DLL_SrchOrigin origin, DLL_SrchDir dir);

The second function returns a pointer of a copy of the state table to the following structure:

typedef struct search_modes
  {
  DLL_SrchOrigin search_origin;
  DLL_SrchDir  search_dir;
  } DLL_SearchModes;

The purpose of this function is to check how a succeeding search will be conducted by interrogating the state table.

DLL_Return DLL_GetSearchModes(List *list);

Last in this group are three functions that return data relative to the location of the current pointer. They are not affected by the state table.

DLL_Return DLL_GetCurrentRecord(List *list,
        Info *record);
DLL_Return DLL_GetPriorRecord(List *list,
        Info *record);
DLL_Return DLL_GetNextRecord(List *list,
        Info *record);

Generally, input and output functions would not be considered a part of a linked list implementation; however, they do make life a bit easier when using ADTs. Without these functions one would have to set the current pointer to the head or tail of the list and then make repeated calls to one of the DLL_Get functions mentioned above. If sorting during this process were needed, the task would be even more tedious.

Writing to or reading from a disk tends to be very platform specific. I have striven to make the next two functions as generic as possible; they open files in binary mode and write or read the Info structure from beginning to end. Depending on how you enter data in the Info structure will determine if there will be any endian problems.

To save a list, determine the full path to the file, then pass its pointer to the next function. There are no sorting options with this function, because the list is presumably sorted in memory and will be saved in that order.

DLL_Return DLL_SaveList(List *list,
        const char *path);

When loading a file from disk, you have the option of sorting the list as it comes into memory. Passing a NULL loads the file as it exists on the disk and loads it faster than if the list is sorted.

DLL_Return DLL_LoadList(List *list,
   const char *path, int (*pFun)(Info *, Info *));