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); #endifAnd 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; }