Mastering Algorithms With C - Kyle Loudon [35]
Return Value
0 if inserting the element is successful, or -1 otherwise.
Description
Inserts an element just before element in the doubly-linked list specified by list. When inserting into an empty list, element may point anywhere, but should be NULL to avoid confusion. The new element contains a pointer to data, so the memory referenced by data should remain valid as long as the element remains in the list. It is the responsibility of the caller to manage the storage associated with data.
Complexity
O (1)
Name
dlist_remove
Synopsis
int dlist_remove(DList *list, DListElmt *element, void **data);
Return Value
0if removing the element is successful, or -1 otherwise.
Description
Removes the element specified as element from the doubly-linked list specified by list. Upon return, data points to the data stored in the element that was removed. It is the responsibility of the caller to manage the storage associated with the data.
Complexity
O (1)
Name
dlist_size
Synopsis
int dlist_size(const DList *list);
Return Value
Number of elements in the list.
Description
Macro that evaluates to the number of elements in the doubly-linked list specified by list.
Complexity
O (1)
Name
dlist_head
Synopsis
DListElmt *dlist_head(const DList *list);
Return Value
Element at the head of the list.
Description
Macro that evaluates to the element at the head of the doubly-linked list specified by list.
Complexity
O (1)
Name
dlist_tail
Synopsis
DListElmt *dlist_tail(const DList *list);
Return Value
Element at the tail of the list.
Description
Macro that evaluates to the element at the tail of the doubly-linked list specified by list.
Complexity
O (1)
Name
dlist_is_head
Synopsis
int dlist_is_head(const DListElmt *element);
Return Value
1 if the element is at the head of the list, or 0 otherwise.
Description
Macro that determines whether the element specified as element is at the head of a doubly-linked list.
Complexity
O (1)
Name
dlist_is_tail
Synopsis
int dlist_is_tail(const DListElmt *element);
Return Value
1 if the element is at the tail of the list, or otherwise.
Description
Macro that determines whether the element specified as element is at the tail of a doubly-linked list.
Complexity
O (1)
Name
dlist_data
Synopsis
void *dlist_data(const DListElmt *element);
Return Value
Data stored in the element.
Description
Macro that evaluates to the data stored in the element of a doubly-linked list specified by element.
Complexity
O (1)
Name
dlist_next
Synopsis
DListElmt *dlist_next(const DListElmt *element);
Return Value
Element following the specified element.
Description
Macro that evaluates to the element of a doubly-linked list following the element specified by element.
Complexity
O (1)
Name
dlist_prev
Synopsis
DListElmt *dlist_prev(const DListElmt *element);
Return Value
Element preceding the specified element.
Description
Macro that evaluates to the element of a doubly-linked list preceding the element specified by element.
Complexity
O (1)
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.
Example 5.4. Header for the Doubly-Linked List Abstract Datatype
/*****************************************************************************
* *
* ------------------------------- dlist.h -------------------------------- *
* *
*****************************************************************************/
#ifndef DLIST_H
#define DLIST_H
#include