Sedgewick like single linked list:
Code:
EMPTY LIST
+------+
V |
+---+ +---+ |
| |------>| |---+
+---+ +---+
head tail
This structure must obey some ground rules:
1 - Never try to delete head or tail nodes;
2 - Never try to add a node after tail node;
3 - Insert or delete nodes AFTER a specific node.
The node structure is this:
Code:
struct node { struct node *next; };
Without any data! Only the link to the next node. The list structure is like this:
Code:
struct list { struct node head, tail; };
Yep... head and tail aren't pointers! And we must initialize an object of this structure with this macro:
Code:
#define INIT_LIST(list__) (struct list){ .head.next = &(list_).tail, \
.tail.next = &(list__).tail }
Like this:
Code:
struct list mylist = INIT_LIST(mylist);
These structures allow polymorphic nodes. All you have to do is to make sure the first member of any node is the next pointer. Like in:
Code:
struct mynode {
struct node *next;
// ... a bunch of my node objects here
};
Here's the insert after node function:
Code:
void slist_insertAfter( struct node *node, struct node *new )
{
new->next = node->next;
node->next = new;
}
And the delete after:
Code:
// return NULL if next node is tail.
struct node *slist_deleteAfter( struct node *node )
{
struct node *next;
next = node->next;
if ( next == next->next )
return NULL;
node->next = next->next;
return next;
}
In this particular example I choose to return NULL if the next node is tail.
To test if a list is empty is very simple:
Code:
_Bool slist_empty( struct list *list )
{ return list->head.next == &list->tail; }
Another useful routine could be:
Code:
_Bool slist_istail( struct node *node )
{ return node == node->next; }
To empty the entire list is simple:
Code:
void slist_clear( struct list *list, void (*dtor)( void * ) )
{
while ( 1 )
{
struct node *node;
node = slist_deleteAfter( &list->head );
if ( ! node )
break;
if ( dtor )
dtor( node );
}
}
Where's the nodes allocations? You may ask. They are NOT part of the list manipulation (and never should be). Here's an example of usage:
Code:
// macro for list iteration.
#define for_each(iter__,list__) \
for ( (iter__) = (list__)->head.next; \
(iter__) != (iter__)->next; \
(iter__) = (iter__)->next )
int main( void )
{
struct list list = LIST_INIT(list);
struct node *i; // list iterator.
struct mynode {
struct node *next;
int value;
};
struct mynode *p;
// As an example I did not test the success or failure of malloc here!
// you should do it... Notice the allocation is NOT part of the
// list manipulation routines.
p = malloc( sizeof *p ); p->value = 1;
slist_insertAfter( &list.head, (struct node *)p ); i = (struct node *)p;
p = malloc( sizeof *p ); p->value = 2;
slist_insertAfter( i, (struct node *)p ); i = (struct node *)p;
p = malloc( sizeof *p ); p->value = 3;
slist_insertAfter( i, (struct node *)p );
for_each( i, &list )
{
p = (struct mynode *)i;
printf( "%d ", p->value );
}
putchar( '\n' );
slist_clear( &list, free ); // using free() as destructor.
}
Originally Posted by Salem
