• Choose a category
• All
• Classic-Fiction

By Root 1399 0

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.

Example 5.5. Implementation of the Doubly-Linked List Abstract Datatype

/*****************************************************************************

* *

* ------------------------------- dlist.c -------------------------------- *

* *

*****************************************************************************/

#include

#include

#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. *