Linked Lists
[Data Structures]

Linked lists. More...


Files

file  list.c
 Linked lists implementation.
file  list.h
 Linked lists header.

Functions

int list_push (node_l **_x, void *_data)
 Adds a new node to the list.
int cmp (void *_a, void *_b)
 Auxiliary function for examples.
void * list_pop (node_l **_x)
 Removes the first node from the list and returns its node data.
int list_move (node_l **_dest, node_l **_src)
 Moves a node from _src to _dest.
int list_reverse (node_l **_x)
 Reverses the order of a list.
node_llist_sub (const node_l *_x, int _pos)
 Returns a sub-list of _x.
int list_insert (node_l **_x, int _pos, void *_data)
 Inserts a new node at the specified position.
void * list_remove (node_l **_x, int _pos)
 Removes element at position _pos+1 from the list, returning its data.
void * list_get (const node_l *_x, int _pos)
 Get data item of a list element.
size_t list_size (const node_l *_x)
 Computes the size of a list.
node_llist_join (node_l *_dest, node_l *_src)
 Appends the list _src to the list _dest.
void list_print (const node_l *_a)
 Prints list elements.
int list_split (node_l **_src, node_l **_front, node_l **_back)
 Splits a list in two equal-sized sublists.
int list_merge (node_l **_dest, node_l **_a, node_l **_b, int _cmp(void *, void *))
 Merges two lists using _cmp to compare nodes.
int list_sort (node_l **_x, int _cmp(void *, void *))
 Sorts a list.
int list_copy (const node_l *_src, node_l **_dest)
 Makes a copy of a list, not including its data items (see list_dup()).
int list_realloc (node_l *_x, size_t _sz)
 Re-allocates storage for a list.
int list_dup (node_l *_src, node_l **_dest, size_t _sz)
 Duplicates a list, including its data items (see list_copy()).
void list_delete (node_l **_x)
 Deletes a list, not including its data items.
void list_destroy (node_l **_x)
 Destroys a list, including its data items.
node_llist_create123 ()
 Auxiliary function for examples.
int list_foreach (node_l *_x, int _func(void *))
 Calls a function for each list element.

Detailed Description

Linked lists.

See the following pages for detailed information about linked lists:


Function Documentation

int list_push ( node_l **  _x,
void *  _data 
)

Adds a new node to the list.

Creates a new node with the given data and pushes it onto the front of the list. The list is not passed in by its head pointer. Instead the list is passed in as a "reference" pointer to the head pointer -- this allows as to modify the caller's memory.

This is a constant time operation.

Parameters:
_x reference to a list (adress might change)
_data the data item for the new node
Returns:
-1 on error (out of memory), 0 on success

Definition at line 56 of file dlist.c.

References node_l::data, and node_l::next.

Referenced by list_copy(), list_create123(), list_insert(), and stack_push().

int cmp ( void *  _a,
void *  _b 
)

Auxiliary function for examples.

This function compares to data items and returns -1, 0 or 1 if the first argument is less than, equal to or greater than the second argument respectively.

Parameters:
_a data item
_b data item
Returns:
-1, 0 or 1

Definition at line 312 of file dlist.c.

References _data::n.

void* list_pop ( node_l **  _x  ) 

Removes the first node from the list and returns its node data.

Note that NULL is a valid node data. Also note that the function will return NULL also for the empty list.

This is a constant time operation.

Parameters:
_x reference to a list (adress might change)
Returns:
a pointer to the data item of the removed node

Definition at line 80 of file list.c.

References node_l::data, and node_l::next.

Referenced by list_delete(), list_destroy(), list_remove(), and stack_pop().

int list_move ( node_l **  _dest,
node_l **  _src 
)

Moves a node from _src to _dest.

The function removes the first node of _src, making it the first node of _dest. If _src and _dest are equal, the current implementation swaps the first two nodes. This behaviour may change in future releases, so don't rely on it.

Parameters:
_dest the destination list
_src the source list
Returns:
-1 on error (_src is the empty list), 0 on success

Definition at line 109 of file list.c.

References node_l::next.

Referenced by list_merge(), and list_reverse().

int list_reverse ( node_l **  _x  ) 

Reverses the order of a list.

This function reverses the order of a list, making the last element the first, the second-last the second-first and so on... This is useful when creating a list with a few list_push() operations, because elements will then appear in reverse order.

Parameters:
_x reference to a list (adress might change)
Returns:
0 on success (currently this function can't possibly fail)

Definition at line 136 of file list.c.

References list_move().

Referenced by list_copy().

node_l* list_sub ( const node_l _x,
int  _pos 
)

Returns a sub-list of _x.

This function returns the sub-list of _x starting at position _pos+1.

Parameters:
_x pointer to a list
_pos sub-list position
Returns:
pointer to the sub-list starting at position _pos+1

Definition at line 157 of file list.c.

References node_l::next.

Referenced by list_insert().

int list_insert ( node_l **  _x,
int  _pos,
void *  _data 
)

Inserts a new node at the specified position.

This function creates a new node with the supplied _data and inserts it at position _pos+1 of _x. This is a linear time operation, for obvious reasons.

Parameters:
_x reference to a list (address might change)
_pos position of new list node
_data data item of new list node
Returns:
-1 on error, 0 on success

Definition at line 186 of file list.c.

References list_push(), list_sub(), and node_l::next.

void* list_remove ( node_l **  _x,
int  _pos 
)

Removes element at position _pos+1 from the list, returning its data.

This function removes the element at position _pos+1 from the list. If _pos is 0, its semantics are equivalent to list_pop().

Parameters:
_x reference to a list (address might change)
_pos position of element to be removed
Returns:
pointer to data item of removed element

Definition at line 214 of file list.c.

References node_l::data, list_pop(), and node_l::next.

void* list_get ( const node_l _x,
int  _pos 
)

Get data item of a list element.

This function returns a pointer to the data item of the list element at position _pos+1. It will return NULL on error. Note that NULL is also a valid data item.

Parameters:
_x pointer to a list
_pos position of a list element
Returns:
NULL on error, pointer to a data item on success

Definition at line 255 of file list.c.

References node_l::data, and node_l::next.

size_t list_size ( const node_l _x  ) 

Computes the size of a list.

This function computes the size of a list. The code should be relatively self-explanatory.

Parameters:
_x pointer to a list
Returns:
the size of the list

Definition at line 279 of file list.c.

References node_l::next.

node_l* list_join ( node_l _dest,
node_l _src 
)

Appends the list _src to the list _dest.

If _dest is empty, it simply returns _src, else it makes the last element of _dest point to the first element of _src, modifying _dest.

Parameters:
_dest the destination list
_src the source list
Returns:
a pointer to _dest, with _src appended

Definition at line 297 of file list.c.

References node_l::next.

void list_print ( const node_l _a  ) 

Prints list elements.

This function will change or vanish in future releases, so don't use it. It will be replaced by list_foreach(), which shall execute a user-supplied function for each list element.

Parameters:
_a pointer to a list
Returns:
nothing

Definition at line 324 of file list.c.

References node_l::data, _data::n, node_l::next, and _data::str.

int list_split ( node_l **  _src,
node_l **  _front,
node_l **  _back 
)

Splits a list in two equal-sized sublists.

This function uses the hare-and-tortoise approach, also known as the Classic Floyd's Cycle Finding Algorithm to split a list in two rougly equal-sized sublists (see http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm for details). You should make sure that the list doesn't contain cycles using list_cyclic() (to be implemented).

Parameters:
_src reference to a list (will be replaced by NULL)
_front reference to a list (will be replaced by the first sublist)
_back reference to a list (will be replaced by the second sublist)
Returns:
0 on success (this function cannot possibly fail)

Definition at line 351 of file list.c.

References node_l::next.

Referenced by list_sort().

int list_merge ( node_l **  _dest,
node_l **  _a,
node_l **  _b,
int   _cmp(void *, void *) 
)

Merges two lists using _cmp to compare nodes.

This function merges the two lists _a and _b into the new list _dest using the function _cmp to decide which element to choose next, the first element of _a or the first element of _b. _cmp is a comparison function and shall return -1, 0 or 1 if _a->data is less than, equal to or greater than _b->data.

This function is mainly used in list_sort() to merge two already sorted sublists together.

Parameters:
_dest a reference to the resulting list
_a reference to list A
_b reference to list B
_cmp comparison function, takes two data items and returns int

Definition at line 396 of file list.c.

References list_move().

Referenced by list_sort().

int list_sort ( node_l **  _x,
int   _cmp(void *, void *) 
)

Sorts a list.

This function sorts a list using mergesort (see http://en.wikipedia.org/wiki/Merge_sort for details). The comparison function _cmp determines the sort order: _cmp takes two data items A and B and returns -1, 0 or 1 if A is less than, equal to or greater than B respectively.

Parameters:
_x reference to a list (address might change)
_cmp comparison function

Definition at line 438 of file list.c.

References list_merge(), list_sort(), list_split(), and node_l::next.

Referenced by list_sort().

int list_copy ( const node_l _src,
node_l **  _dest 
)

Makes a copy of a list, not including its data items (see list_dup()).

This function creates a copy of a list, NOT duplicating the list's data items. The resulting list uses the same data items as the original list. If you want to duplicate the data items too, use list_dup().

On error, -1 is returned and _dest is the copy of _src up to the point where no more memory was available. In all cases, you have to list_free() _dest.

Parameters:
_src pointer to a list
_dest reference to the list copy
Returns:
-1 on error (out of memory), 0 on success

Definition at line 473 of file list.c.

References node_l::data, list_push(), list_reverse(), and node_l::next.

Referenced by list_dup().

int list_realloc ( node_l _x,
size_t  _sz 
)

Re-allocates storage for a list.

This function re-allocates all data items in _x, assigning the new address to its nodes.

This function is mainly used in list_dup().

Parameters:
_x pointer to a list
_sz size of the list's data items
Returns:
-1 on error (out of memory), 0 on success

Definition at line 500 of file list.c.

References node_l::data, and node_l::next.

Referenced by list_dup().

int list_dup ( node_l _src,
node_l **  _dest,
size_t  _sz 
)

Duplicates a list, including its data items (see list_copy()).

Makes a copy of _src, saving a pointer to the result in _dest.

This function merely calls list_copy(), followed by list_realloc().

Parameters:
_src pointer to a list
_dest reference to a list (address might change)
_sz size of the list's data items
Returns:
-1 on error (not enough memory), 0 on success

Definition at line 529 of file list.c.

References list_copy(), and list_realloc().

void list_delete ( node_l **  _x  ) 

Deletes a list, not including its data items.

This function deletes a list, not including its data items. This will result in memory leaks if you don't have a copy of the list, because all references to the data items are lost.

Parameters:
_x reference to a list (address might change)
Returns:
nothing

Definition at line 552 of file list.c.

References list_pop().

Referenced by stack_delete(), and stack_reset().

void list_destroy ( node_l **  _x  ) 

Destroys a list, including its data items.

This function deletes a list, including its data items. After a call to list_destroy(), the list and its data items will be lost. If you have a copy of the list, it will be invalid (use list_delete() on it).

Parameters:
_x reference to a list (address might change)
Returns:
nothing

Definition at line 571 of file list.c.

References list_pop().

Referenced by stack_destroy().

node_l* list_create123 (  ) 

Auxiliary function for examples.

This function creates a short list, see examples for details.

FIXME: add examples

Returns:
a pointer to the example list

Definition at line 589 of file list.c.

References list_push(), _data::n, and _data::str.

int list_foreach ( node_l _x,
int   _func(void *) 
)

Calls a function for each list element.

list_foreach() executes the user-supplied function _func for each element of the list pointed to by _x, passing the element's data to _func. list_foreach() returns the sum of all return values of _func. This is useful if you want to count all list elements that match to certain criteria, but you may also use list_foreach() for much simpler operations, e.g. print functions.

Parameters:
_x a list
_func a function
Returns:
the sum of _func return values

Definition at line 643 of file list.c.

References node_l::data, and node_l::next.


Generated on Thu Jul 19 13:36:09 2007 for libv by  doxygen 1.5.1-p1. Thank you, SourceForge.net Logo