Implementation and Analysis of Doubly Linked Lists
Recall that each element of a doubly-linked list
consists of three parts: a data member, a pointer to the next element,
and a pointer to the previous element. The structure
DListElmt represents an individual element
of a doubly-linked list (see Example 5.4). As
you would expect, this structure has three members corresponding to
those just mentioned. The structure DList
is the doubly-linked list data structure (see Example 5.4). This structure has members
analogous to the ones used for singly-linked lists.
/*****************************************************************************
* *
* ------------------------------- dlist.h -------------------------------- *
* *
*****************************************************************************/
#ifndef DLIST_H
#define DLIST_H
#include <stdlib.h>
/*****************************************************************************
* *
* Define a structure for doubly-linked list elements. *
* *
*****************************************************************************/
typedef struct DListElmt_ {
void *data;
struct DListElmt_ *prev;
struct DListElmt_ *next;
} DListElmt;
/*****************************************************************************
* *
* Define a structure for doubly-linked lists. *
* *
*****************************************************************************/
typedef struct DList_ {
int size;
int (*match)(const void *key1, const void *key2);
void (*destroy)(void *data);
DListElmt *head;
DListElmt *tail;
} DList;
/*****************************************************************************
* *
* --------------------------- Public Interface --------------------------- *
* *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data));
void dlist_destroy(DList *list);
int dlist_ins_next(DList *list, DListElmt *element, const void *data);
int dlist_ins_prev(DList *list, DListElmt *element, const void *data);
int dlist_remove(DList *list, DListElmt *element, void **data);
#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_data(element) ((element)->data)
#define dlist_next(element) ((element)->next)
#define dlist_prev(element) ((element)->prev)
#endif
dlist_init
The dlist_init operation initializes a doubly-linked list so that it can be used in other operations (see Example 5.5). Initialization is the same as with a singly-linked list.
The runtime complexity of dlist_init is O (1) because all of the steps in initializing a doubly-linked list run in a constant amount of time.
dlist_destroy
The dlist_destroy operation
destroys a doubly-linked list (see Example 5.5). Primarily this means
removing all elements from the list. The function passed as
destroy to
dlist_init is called once for each element as
it is removed, provided destroy was not
set to NULL.
The runtime complexity of dlist_destroy is O (n), where n is the number of elements in the list. This is because the O (1) operation dlist_remove must be called once for each element.
dlist_ins_next
The dlist_ins_next operation
inserts an element into a doubly-linked list just after a specified
element (see Example 5.5).
Inserting an element in a doubly-linked list is similar to inserting
one in a singly-linked list. The primary difference is that in
addition to managing the next pointers,
we must manage the prev pointers to keep
the list linked properly in the reverse direction (see Figure 5.6).
The runtime complexity of dlist_ins_next is O (1) because all of the steps in inserting an element into a doubly-linked list run in a constant amount of time.
dlist_ins_ prev
The dlist_ins_ prev operation
inserts an element into a doubly-linked list just before a specified
element (see Example 5.5).
Inserting an element in a doubly-linked list is similar to inserting
one in a singly-linked list. As with
dlist_ins_next, the primary difference is that
in addition to managing the next
pointers, we must manage the prev
pointers to keep the list linked properly in the reverse
direction.
The runtime complexity of dlist_ins_prev is O (1) because all of the steps in inserting an element into a doubly-linked list run in a constant amount of time.
dlist_remove
The dlist_remove operation
removes a specified element from a doubly-linked list
(see Example 5.5). The primary
difference from a singly-linked list is that in addition to managing
the next pointers, we must manage the
prev pointers to keep the list linked
properly in the reverse direction. Another difference is that in a
doubly-linked list, it is possible to remove the specified element
rather than the one just after it because there is a pointer back to
the previous element.
The runtime complexity of dlist_remove is O (1) because all of the steps in removing an element from a doubly-linked list run in a constant amount of time.
dlist_size, dlist_head, dlist_tail, dlist_is_head, dlist_is_tail, dlist_data, dlist_next, and dlist_ prev
These macros implement some of the simpler doubly-linked list
operations (see Example 5.4).
Generally, they provide an interface for accessing and testing
members of the DList and
DListElmt structures.
The runtime complexity of these operations is O (1) because accessing and testing members of a structure are simple tasks that run in a constant amount of time.
/*****************************************************************************
* *
* ------------------------------- dlist.c -------------------------------- *
* *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include "dlist.h"
/*****************************************************************************
* *
* ------------------------------ dlist_init ------------------------------ *
* *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data)) {
/*****************************************************************************
* *
* Initialize the list. *
* *
*****************************************************************************/
list->size = 0;
list->destroy = destroy;
list->head = NULL;
list->tail = NULL;
return;
}
/*****************************************************************************
* *
* ---------------------------- dlist_destroy ----------------------------- *
* *
*****************************************************************************/
void dlist_destroy(DList *list) {
void *data;
/*****************************************************************************
* *
* Remove each element. *
* *
*****************************************************************************/
while (dlist_size(list) > 0) {
if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->
destroy != NULL) {
/***********************************************************************
* *
* Call a user-defined function to free dynamically allocated data. *
* *
***********************************************************************/
list->destroy(data);
}
}
/*****************************************************************************
* *
* No operations are allowed now, but clear the structure as a precaution. *
* *
*****************************************************************************/
memset(list, 0, sizeof(DList));
return;
}
/*****************************************************************************
* *
* ---------------------------- dlist_ins_next ---------------------------- *
* *
*****************************************************************************/
int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
DListElmt *new_element;
/*****************************************************************************
* *
* Do not allow a NULL element unless the list is empty. *
* *
*****************************************************************************/
if (element == NULL && dlist_size(list) != 0)
return -1;
/*****************************************************************************
* *
* Allocate storage for the element. *
* *
*****************************************************************************/
if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
return -1;
/*****************************************************************************
* *
* Insert the new element into the list. *
* *
*****************************************************************************/
new_element->data = (void *)data;
if (dlist_size(list) == 0) {
/**************************************************************************
* *
* Handle insertion when the list is empty. *
* *
**************************************************************************/
list->head = new_element;
list->head->prev = NULL;
list->head->next = NULL;
list->tail = new_element;
}
else {
/**************************************************************************
* *
* Handle insertion when the list is not empty. *
* *
**************************************************************************/
new_element->next = element->next;
new_element->prev = element;
if (element->next == NULL)
list->tail = new_element;
else
element->next->prev = new_element;
element->next = new_element;
}
/*****************************************************************************
* *
* Adjust the size of the list to account for the inserted element. *
* *
*****************************************************************************/
list->size++;
return 0;
}
/*****************************************************************************
* *
* ---------------------------- dlist_ins_prev ---------------------------- *
* *
*****************************************************************************/
int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
DListElmt *new_element;
/*****************************************************************************
* *
* Do not allow a NULL element unless the list is empty. *
* *
*****************************************************************************/
if (element == NULL && dlist_size(list) != 0)
return -1;
/*****************************************************************************
* *
* Allocate storage to be managed by the abstract datatype. *
* *
*****************************************************************************/
if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
return -1;
/*****************************************************************************
* *
* Insert the new element into the list. *
* *
*****************************************************************************/
new_element->data = (void *)data;
if (dlist_size(list) == 0) {
/**************************************************************************
* *
* Handle insertion when the list is empty. *
* *
**************************************************************************/
list->head = new_element;
list->head->prev = NULL;
list->head->next = NULL;
list->tail = new_element;
}
else {
/**************************************************************************
* *
* Handle insertion when the list is not empty. *
* *
**************************************************************************/
new_element->next = element;
new_element->prev = element->prev;
if (element->prev == NULL)
list->head = new_element;
else
element->prev->next = new_element;
element->prev = new_element;
}
/*****************************************************************************
* *
* Adjust the size of the list to account for the new element. *
* *
*****************************************************************************/
list->size++;
return 0;
}
/*****************************************************************************
* *
* ----------------------------- dlist_remove ----------------------------- *
* *
*****************************************************************************/
int dlist_remove(DList *list, DListElmt *element, void **data) {
/*****************************************************************************
* *
* Do not allow a NULL element or removal from an empty list. *
* *
*****************************************************************************/
if (element == NULL || dlist_size(list) == 0)
return -1;
/*****************************************************************************
* *
* Remove the element from the list. *
* *
*****************************************************************************/
*data = element->data;
if (element == list->head) {
/**************************************************************************
* *
* Handle removal from the head of the list. *
* *
**************************************************************************/
list->head = element->next;
if (list->head == NULL)
list->tail = NULL;
else
element->next->prev = NULL;
}
else {
/**************************************************************************
* *
* Handle removal from other than the head of the list. *
* *
**************************************************************************/
element->prev->next = element->next;
if (element->next == NULL)
list->tail = element->prev;
else
element->next->prev = element->prev;
}
/*****************************************************************************
* *
* Free the storage allocated by the abstract datatype. *
* *
*****************************************************************************/
free(element);
/*****************************************************************************
* *
* Adjust the size of the list to account for the removed element. *
* *
*****************************************************************************/
list->size--;
return
0;
}