Mastering Algorithms With C - Kyle Loudon [29]
Return Value
0 if inserting the element is successful, or -1 otherwise.
Description
Inserts an element just after element in the linked list specified by list. If element is NULL, the new element is inserted at the head of the list. 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
list_rem_next
Synopsis
int list_rem_next(List *list, ListElmt *element, void **data);
Return Value
0 if removing the element is successful, or -1 otherwise.
Description
Removes the element just after element from the linked list specified by list. If element is NULL, the element at the head of the list is removed. 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
list_size
Synopsis
int list_size(const List *list);
Return Value
Number of elements in the list.
Description
Macro that evaluates to the number of elements in the linked list specified by list.
Complexity
O (1)
Name
list_head
Synopsis
ListElmt *list_head(const List *list);
Return Value
Element at the head of the list.
Description
Macro that evaluates to the element at the head of the linked list specified by list.
Complexity
O (1)
Name
list_tail
Synopsis
ListElmt *list_tail(const List *list);
Return Value
Element at the tail of the list.
Description
Macro that evaluates to the element at the tail of the linked list specified by list.
Complexity
O (1)
Name
list_is_head
Synopsis
int list_is_head(const ListElmt *element);
Return Value
1 if the element is at the head of the list, or otherwise.
Description
Macro that determines whether the element specified as element is at the head of a linked list.
Complexity
O (1)
Name
list_is_tail
Synopsis
int list_is_tail(const ListElmt *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 linked list.
Complexity
O (1)
Name
list_data
Synopsis
void *list_data(const ListElmt *element);
Return Value
Data stored in the element.
Description
Macro that evaluates to the data stored in the element of a linked list specified by element.
Complexity
O (1)
Name
list_next
Synopsis
ListElmt *list_next(const ListElmt *element);
Return Value
Element following the specified element.
Description
Macro that evaluates to the element of a linked list following the element specified by element.
Complexity
O (1)
Implementation and Analysis of Linked Lists
Recall that each element of a linked list consists of two parts: a data member and a pointer to the next element in the list. The structure ListElmt represents an individual element of a linked list (see Example 5.1). As you would expect, this structure has two members that correspond to those just mentioned. The structure List is the linked list data structure (see Example 5.1). This structure consists of five members: size is the number of elements in the list, match is a member not used by linked lists but by datatypes that will be derived later from linked lists, destroy is the encapsulated destroy function passed to list_init , head is a pointer to the first of the linked elements, and tail is a pointer to the tail element.
Example 5.1. Header for the Linked List Abstract Datatype
/*****************************************************************************
* *
* -------------------------------- list.h -------------------------------- *
* *
*****************************************************************************/
#ifndef LIST_H
#define LIST_H
#include /***************************************************************************** * * * Define a structure for linked list elements.