1. linklist.c

#include "linklist.h"

/* Allocate new list. */
struct list *
list_new (void)
{

  return (struct list *)calloc(1, sizeof(struct list));

}

/* Free list. */
void
list_free (struct list *l)
{
  free(l);

}

/* Allocate new listnode.  Internal use only. */
static struct listnode *
listnode_new (void)
{
  return (struct listnode *)calloc(1,sizeof (struct listnode));
}

/* Free listnode. */
static void
listnode_free (struct listnode *node)
{
  free(node);
}

/* Add new data to the list. */
void
listnode_add (struct list *list, void *val)
{
  struct listnode *node;
  
  assert (val != NULL);
  
  node = listnode_new ();

  node->prev = list->tail;
  node->data = http://www.mamicode.com/val;>

2. linklist.h

#ifndef __LINKLIST_H
#define __LINKLIST_H

/* listnodes must always contain data to be valid. Adding an empty node
 * to a list is invalid
 */
struct listnode 
{
  struct listnode *next;
  struct listnode *prev;
  
  /* private member, use getdata() to retrieve, do not access directly */
  void *data;
};

struct list 
{
  struct listnode *head;
  struct listnode *tail;

  /* invariant: count is the number of listnodes in the list */
  unsigned int count;

  /*
   * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
   * Used as definition of sorted for listnode_add_sort
   */
  int (*cmp) (void *val1, void *val2);

  /* callback to free user-owned data when listnode is deleted. supplying
   * this callback is very much encouraged!
   */
  void (*del) (void *val);
};

#define listnextnode(X) ((X) ? ((X)->next) : NULL)
#define listhead(X) ((X) ? ((X)->head) : NULL)
#define listtail(X) ((X) ? ((X)->tail) : NULL)
#define listcount(X) ((X)->count)
#define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
#define listgetdata(X) (assert((X)->data != NULL), (X)->data)

/* Prototypes. */
extern struct list *list_new(void); /* encouraged: set list.del callback on new lists */
extern void list_free (struct list *);

extern void listnode_add (struct list *, void *);
extern void listnode_add_sort (struct list *, void *);
extern void listnode_add_after (struct list *, struct listnode *, void *);
extern void listnode_delete (struct list *, void *);
extern struct listnode *listnode_lookup (struct list *, void *);
extern void *listnode_head (struct list *);

extern void list_delete (struct list *);
extern void list_delete_all_node (struct list *);

extern void list_delete_node (struct list *, struct listnode *);
extern void list_add_node_prev (struct list *, struct listnode *, void *);
extern void list_add_node_next (struct list *, struct listnode *, void *);
extern void list_add_list (struct list *, struct list *);

/* List iteration macro. 
 * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
 * It is safe to delete the listnode using this macro.
 */
#define ALL_LIST_ELEMENTS(list,node,nextnode,data)   (node) = listhead(list), ((data) = NULL);   (node) != NULL &&     ((data) = listgetdata(node),(nextnode) = node->next, 1);   (node) = (nextnode), ((data) = NULL)

/* read-only list iteration macro.
 * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
 * use this macro when it is *immediately obvious* the listnode is not
 * deleted in the body of the loop. Does not have forward-reference overhead
 * of previous macro.
 */
#define ALL_LIST_ELEMENTS_RO(list,node,data)   (node) = listhead(list), ((data) = NULL);  (node) != NULL && ((data) = listgetdata(node), 1);   (node) = listnextnode(node), ((data) = NULL)

/* these *do not* cleanup list nodes and referenced data, as the functions
 * do - these macros simply {de,at}tach a listnode from/to a list.
 */
 
/* List node attach macro.  */
#define LISTNODE_ATTACH(L,N)   do {     (N)->prev = (L)->tail;     if ((L)->head == NULL)       (L)->head = (N);     else       (L)->tail->next = (N);     (L)->tail = (N);     (L)->count++;   } while (0)

/* List node detach macro.  */
#define LISTNODE_DETACH(L,N)   do {     if ((N)->prev)       (N)->prev->next = (N)->next;     else       (L)->head = (N)->next;     if ((N)->next)       (N)->next->prev = (N)->prev;     else       (L)->tail = (N)->prev;     (L)->count--;   } while (0)


#endif /* __LINKLIST_H */


好用的链表操作库。