通过组合使用结构和指针创建强大的数据结构。链表是一些包含数据的独立数据结构（节点）的集合，链表中的每个节点通过链或指针连接在一起

1 单链表

在单链表中，每个节点包含一个指向链表下一节点的指针，链表最后一个节点的指针字段的值为NULL，提示链表后面不再有其他节点。链表的起始位置使用根指针，根指针指向链表的第1个节点，根指针只是一个指针，它不包含任何数据。

typedef struct NODE {
	struct NODE *link;
	int value;
} Node;

#include <stdlib.h>
#include <stdio.h>
#include "sll_node.h"

#define	FALSE	0
#define TRUE	1

int
sll_insert( register Node **linkp, int new_value )
{
	register Node	*current;
	register Node	*new;

	/*
	** Look for the right place by walking down the list
	** until we reach a node whose value is greater than
	** or equal to the new value.
	*/
	while( ( current = *linkp ) != NULL &&
	    current->value < new_value )
		linkp = &current->link;

	/*
	** Allocate a new node and store the new value into it.
	** In this event, we return FALSE.
	*/
	new = (Node *)malloc( sizeof( Node ) );
	if( new == NULL )
		return FALSE;
	new->value = new_value;

	/*
	** Insert the new node into the list, and return TRUE.
	*/
	new->link = current;
	*linkp = new;
	return TRUE;
}

2 双链表

每个节点都包含两个指针，指向前一个节点的指针和指向后一个节点的指针。两个根指针：一个指向链表的第1个节点，另一个指向最后一个节点。根节点的fwd字段指向链表的第1个节点，根节点的bed字段指向链表的最后一个节点。链表第1个节点的bwd字段和最后一个节点的fwd字段都为NULL。

typedef	struct	NODE	{
	struct	NODE	*fwd;
	struct	NODE	*bwd;
	int		value;
} Node;

#include <stdlib.h>
#include <stdio.h>
#include "dll_node.h"

int
dll_insert( register Node *rootp, int value )
{
	register Node	*this;
	register Node	*next;
	register Node	*newnode;

	/*
	** See if value is already in the list; return if it is.
	** Otherwise, allocate a new node for the value ("newnode"
	** will point to it). "this" will point to the node that the
	** new value should follow, and "next" will point to the one
	** after it.
	*/
	for( this = rootp; (next = this->fwd) != NULL; this = next ){
		if( next->value == value )
			return 0;
		if( next->value > value )
			break;
	}
	newnode = (Node *)malloc( sizeof( Node ) );
	if( newnode == NULL )
		return -1;
	newnode->value = value;

	/*
	** Add the new node to the list.
	*/
	newnode->fwd = next;
	this->fwd = newnode;

	if( this != rootp )
		newnode->bwd = this;
	else
		newnode->bwd = NULL;

	if( next != NULL )
		next->bwd = newnode;
	else
		rootp->bwd = newnode;

	return 1;
}