This is a C module useful for implementing homogenous singly-linked lists in C, similar in some ways to C++'s std::list. Its advantages include:
ints.However, like C++'s std::list, it has the disadvantage of generating code for each different type you wish to construct a list of.
Here is some sample code using it (which you may download here):
#include <stdio.h> /* printf */
#include "list.h"
typedef struct
{
int x;
int y;
} point;
DECLARE_LIST(point, point)
DEFINE_LIST(point, point)
point create_point(int x, int y)
{
point p;
p.x = x;
p.y = y;
return p;
}
int main(void)
{
point_list points = point_list_new();
point_list_push_back(&points, create_point(10, 1));
point_list_push_back(&points, create_point(2, 3));
point_list_push_back(&points, create_point(4, 5));
point_list_pop_front(&points);
LIST_ITERATE(point, points, iter,
point p = *point_list_value(iter);
printf("(%d, %d)\n", p.x, p.y);
)
point_list_clear(&points);
return 0;
}
Note that normally the DECLARE_LIST would
go in a header file.
First define the type that you'll want the list to be a list of,
typically in some header file, and after this, use
DECLARE_LIST to declare the opaque list type and
all the methods for manipulating it. DECLARE_LIST
takes two arguments: the type of the elements of the list, and a
prefix for all of the methods and type names, which can contain no
spaces and is typically the type name or an abbreviation of it:
#include "list.h"
typedef struct
{
int x;
int y;
} point;
DECLARE_LIST(point, point)
The macro in this case declares the types point_list
and point_list_iterator, as well as several functions
beginning with point_list_ for manipulating these types.
The types are intended to be opaque; never touch their contents directly.
To actually define the functions, invoke
DEFINE_LIST with the same arguments in some source
file that is linked into your program, possibly one dedicated to
defining list types.
The only way to create a new list is using prefix_list_new (where
prefix is the prefix you passed to DECLARE_LIST):
point_list points = point_list_new();
This creates a new empty list, as you can verify with the handy
test function prefix_list_empty.
You can add items to the beginning or end, as well as add items before or after a given iterator using these functions:
point_list_push_back(&points, create_point(10, 1)); point_list_push_front(&points, create_point(1, 2)); point_list_iterator iter = point_list_first(points); point_list_add_after(iter, create_point(6, 2)); point_list_next(&iter); point_list_add_before(iter, create_point(4, 5));
Note that most functions that modify the list will take a pointer
to the list. Also note that adding items to the list allocates
memory. You must later call prefix_list_clear on the list
to recover it (this also destroys all the data in the list):
point_list_clear(&points);
You can remove items from the beginning, but not from the end, because this is an expensive operation on a singly-linked list. You can also remove the value at the current position of any iterator:
point_list_pop_front(&points); point_list_iterator iter = point_list_first(points); point_list_next(&iter); point_list_remove(&points, &iter); /* iter now points after removed element */
Removing an element frees the memory used by the node. Do not access
a value obtained through prefix_list_value after removing
it from the list unless you have copied it. Also do not use any copy
of an iterator you've stored that may refer to a removed element
(the one you pass in to point_list_remove will be adjusted).
When implementing queues and stacks, you often only want to
access the data at the beginning of the list. The function
prefix_list_first_data does this.
To simply iterate over the elements of the list, you can use
the LIST_ITERATE utility macro, which takes:
DECLARE_LISTWithin the loop you can use break or
continue as expected, and you can use
prefix_list_value on the iterator you specified to get a
pointer to the value stored at the current place in the list, as well
as prefix_list_remove to remove elements, but remember
that both prefix_list_remove and looping around both move
the iterator ahead one.
LIST_ITERATE(point, points, iter,
point p = *point_list_value(iter);
printf("(%d, %d)\n", p.x, p.y);
point_list_value(iter)->x = 5;
)
You can also manipulate iterators yourself, by using
prefix_list_first to retrieve an iterator positioned
at the beginning of the list, prefix_list_next to move
it to the next element of the list, and prefix_list_done
to test if the iterator has moved beyond the last element
of the list. The above loop may be written without LIST_ITERATE
as:
point_list_iterator iter = point_list_first(*points);
while(!point_list_done(iter)) {
point p = *point_list_value(iter);
printf("(%d, %d)\n", p.x, p.y);
point_list_value(iter)->x = 5;
point_list_next(&iter);
}
You can also copy iterators in the obvious way, storing one for reuse later:
point_list_iterator iter = point_list_first(*points); point_list_iterator iter2 = iter; point_list_next(&iter); /* Now iter and iter2 refer to different elements */
If you don't want to destroy data when you remove nodes of the list, or you are already storing your data in some other structure, you may wish to store pointers to it instead, like this:
typedef struct
{
int x;
int y;
} point;
DECLARE_LIST(point*, point)
DEFINE_LIST(point*, point)
Then, when adding, take addresses:
point p = create_point(10, 1); point_list_push_back(points, &p); point_list_destroy(points); /* p is still valid here */
To implement a queue or stack, simply restrict yourself to using
prefix_list_push_front and
prefix_list_pop_front for stacks, or
prefix_list_push_back and
prefix_list_pop_front for queues. To extract the first
element of the list, use prefix_list_first_data.
Putting the same data on multiple lists at once is problematic. The simplest solution is to have one master list containing the data (or the data could be stored somewhere else entirely, or just free-floating), and other lists only contain pointers to the data, as explained in Keeping Data Outside the List above.
When implementing singly-linked lists by hand in C, however, a
common practice is to include next pointers for several lists, with
nonapplicable ones left NULL. This would be nice to
have.
The implementation is contained entirely within the file
list.h, and has no external dependencies other than
malloc/free. Each function is
documented.
list.h
(view html)
list-test.c
(view html)