Doubly linked lists

Introduction

Like a simply linked list, a doubly linked list is not an abstract data type, but only an implementation type. This fact does not prevent doubly linked lists from being extremely useful, however.

As with simply linked lists, we assume that the elements on the list are in the form of pointers, so that we respect uniform reference semantics.

The definition

For the purpose of this document, we shall define a list as a pointer to a structure of type dcell like this:
  typedef struct dcell *dlist;

  struct dcell
  {
    void *element;
    dlist next;
    dlist prev;
  };
Notice that as usual, we prefer to manipulate the pointer rather than the structure itself. Also notice the names of the fields that we try not to change so that code that uses the list for implementation is easier and faster to read.

As with simply linked lists, there are some operations that are useful on doubly linked lists. The most basic operation is to construct a new dcell, given values of the three fields:

  dlist 
  dcons(void *element, dlist prev, dlist next)
  {
    dlist temp = malloc(sizeof(struct dcell));
    temp -> element = element;
    temp -> prev = prev;
    temp -> next = next;
    return temp;
  }
This procedure works no matter what the values of the prev and next fields are. Sometimes, when we know that these values point to other cells (as opposed to say NULL), we could use a procedure that also links in the new dcell between the two existing ones:
  dlist
  create_and_link(void *element, dlist prev, dlist next)
  {
    dlist temp = dcons(element, prev, next);
    prev -> next = temp;
    next -> prev = temp;
    return temp;
  }
As with the simply linked lists, we could use a routine that unlinks a dcell and then deallocates the memory for it:
  void *
  unlink_and_free(dlist l)
  {
    void *temp = l -> element;
    l -> next -> prev = l -> prev;
    l -> prev -> next = l -> next;
    free(l);
    return temp;
  }

Creating a reusable dlist module

As with simply linked list, we can create a reusable module out of doubly linked lists and associated operations, while recognizing that we do not have an abstract data type. Here is the header file:
  #ifndef DLIST_H
  #define DLIST_H

  typedef struct dcell *dlist;

  struct dcell
  {
    void *element;
    dlist next;
    dlist prev;
  };

  extern dlist dcons(void *element, dlist prev, dlist next);
  extern dlist create_and_link(void *element, dlist prev, dlist next);
  extern void unlink_and_free(dlist l);

  #endif
And here is the implementation file:
  #include "dlist.h"
  #include < stdlib.h>
  
  dlist 
  dcons(void *element, dlist prev, dlist next)
  {
    dlist temp = malloc(sizeof(struct dcell));
    temp -> element = element;
    temp -> prev = prev;
    temp -> next = next;
    return temp;
  }
  
  dlist
  create_and_link(void *element, dlist prev, dlist next)
  {
    dlist temp = dcons(element, prev, next);
    prev -> next = temp;
    next -> prev = temp;
    return temp;
  }

  void *
  unlink_and_free(dlist l)
  {
    void *temp = l -> element;
    l -> next -> prev = l -> prev;
    l -> prev -> next = l -> next;
    free(l);
    return temp;
  }