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.
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;
}
#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;
}