一个双端链表
LinkedList.h 
程序代码：/*
** 一个双端链表的实现，其结点存储的是数据的指针，所以在跨函数使用时必须
** 保证数据是静态或动态分配的。
*/
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
typedef struct NodeTag Node;
typedef struct LinkedListTag LinkedList;
struct NodeTag {
Node* prev; /* 前一个结点 */
Node* next; /* 后一个结点 */
void* data; /* 数据的指针 */
};
struct LinkedListTag {
Node* head; /* 头结点 */
Node* tail; /* 尾结点 */
Node* cur; /* 当前结点 */
int size; /* 链表大小 */
};
LinkedList* Create (void); /* 创建一个链表，成功返回该链表的指针，否则返回NULL */
void Destroy (LinkedList* list); /* 销毁一个链表，之后该链表便不能再使用 */
void Clear (LinkedList* list); /* 清空链表中的所有元素 */
int IsEmpty (LinkedList* list); /* 如果当前链表为空则返回非0，否则返回0 */
int Size (LinkedList* list); /* 获得链表的大小（元素总个数） */
void Begin (LinkedList* list); /* 将当前位置移动到链表的开始 */
void End (LinkedList* list); /* 将当前位置移动到链表的最后 */
void MoveNext (LinkedList* list); /* 将当前位置向后移动一个位置 */
void MovePrev (LinkedList* list); /* 将当前位置向前移动一个位置 */
int HasNext (LinkedList* list); /* 如果当前位置之后还有元素则返回非0，否则返回0 */
int HasPrev (LinkedList* list); /* 如果当前位置之前还有元素则返回非0，否则返回0 */
void* Current (LinkedList* list); /* 返回当前位置的元素 */
int AddBack (LinkedList* list, void* data); /* 将元素添加到链表末尾，成功返回非0，否则返回0 */
int AddFront (LinkedList* list, void* data); /* 将元素添加到链表前端，成功返回非0，否则返回0 */
void* RemoveBack (LinkedList* list); /* 将元素从末端移除并返回该元素，如果链表为空则返回NULL */
void* RemoveFront(LinkedList* list); /* 将元素从前端移除并返回该元素，如果链表为空则返回NULL */
#endif /* LINKED_LIST_H */ LinkedList.c
程序代码：#include "LinkedList.h"
#include <stdlib.h>
#ifndef NULL
#define NULL ((void*)0)
#endif
/* 创建一个链表，成功返回该链表的指针，否则返回NULL */
LinkedList* Create(void)
{
LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
if (!list) return NULL;
list->head = NULL;
list->tail = NULL;
list->cur = NULL;
list->size = 0;
return list;
}
/* 销毁一个链表，之后该链表便不能再使用 */
void Destroy(LinkedList* list)
{
Clear(list);
free(list);
}
/* 清空链表中的所有元素 */
void Clear(LinkedList* list)
{
while (RemoveBack(list)) ;
}
/* 如果当前链表为空则返回非0，否则返回0 */
int IsEmpty(LinkedList* list)
{
return list->size == 0;
}
/* 获得链表的大小（元素总个数） */
int Size(LinkedList* list)
{
return list->size;
}
/* 将当前位置移动到链表的开始 */
void Begin(LinkedList* list)
{
list->cur = list->head;
}
/* 将当前位置移动到链表的最后 */
void End(LinkedList* list)
{
list->cur = list->tail;
}
/* 将当前位置向后移动一个位置 */
void MoveNext(LinkedList* list)
{
list->cur = list->cur->next;
}
/* 将当前位置向后移动一个位置 */
void MovePrev(LinkedList* list)
{
list->cur = list->cur->prev;
}
/* 如果当前位置之后还有元素则返回非0，否则返回0 */
int HasNext(LinkedList* list)
{
if (!list->cur) return 0;
if (list->cur == list->tail) return 1;
return list->cur->next != NULL;
}
/* 如果当前位置之前还有元素则返回非0，否则返回0 */
int HasPrev(LinkedList* list)
{
if (!list->cur) return 0;
if (list->cur == list->head) return 1;
return list->cur->prev != NULL;
}
/* 返回当前位置的元素 */
void* Current(LinkedList* list)
{
return list->cur->data;
}
/* 将元素添加到链表末尾，成功返回非0，否则返回0 */
int AddBack(LinkedList* list, void* data)
{
Node* node = (Node*)malloc(sizeof(Node));
if (!node) return 0;
node->data = data;
if (list->tail) {
list->tail->next = node;
node->prev = list->tail;
node->next = NULL;
} else {
node->next = NULL;
node->prev = NULL;
list->head = node;
}
list->tail = node;
return ++list->size;
}
/* 将元素添加到链表前端，成功返回非0，否则返回0 */
int AddFront(LinkedList* list, void* data)
{
Node* node = (Node*)malloc(sizeof(Node));
if (!node) return 0;
node->data = data;
if (list->head) {
list->head->prev = node;
node->next = list->head;
node->prev = NULL;
} else {
node->next = NULL;
node->prev = NULL;
list->tail = node;
}
list->head = node;
return ++list->size;
}
/* 将元素从末端移除并返回该元素，如果链表为空则返回NULL */
void* RemoveBack(LinkedList* list)
{
Node* temp;
void* data;
if (!list->size) return NULL;
temp = list->tail;
data = list->tail->data;
if (list->head == list->tail) {
list->head = NULL;
list->tail = NULL;
list->cur = NULL;
} else {
list->tail = list->tail->prev;
list->tail->next = NULL;
}
--list->size;
free(temp);
return data;
}
/* 将元素从前端移除并返回该元素，如果链表为空则返回NULL */
void* RemoveFront(LinkedList* list)
{
Node* temp;
void* data;
if (!list->size) return NULL;
temp = list->head;
data = list->head->data;
if (list->head == list->tail) {
list->head = NULL;
list->tail = NULL;
list->cur = NULL;
} else {
list->head = list->head->next;
list->head->prev = NULL;
}
--list->size;
free(temp);
return data;
} LinkedListTest.c
程序代码：#include "LinkedList.h"
#include <stdio.h>
void Traverse(LinkedList* list)
{
for (Begin(list); HasNext(list); MoveNext(list))
printf("%d ", *(int*)Current(list));
putchar('\n');
}
void RTraverse(LinkedList* list)
{
for (End(list); HasPrev(list); MovePrev(list))
printf("%d ", *(int*)Current(list));
putchar('\n');
}
int main(void)
{
LinkedList* list = Create();
int i;
int array1[10];
int array2[10];
for (i = 0; i < 10; ++i) {
array1[i] = i + 1;
array2[i] = i + 10 + 1;
AddBack(list, &array1[i]);
}
puts("1:");
Traverse(list);
RTraverse(list);
printf("Size: %d\n", Size(list));
AddBack(list, &array2[0]);
puts("2:");
Traverse(list);
RTraverse(list);
printf("Size: %d\n", Size(list));
AddFront(list, &array2[1]);
puts("3:");
Traverse(list);
RTraverse(list);
printf("Size: %d\n", Size(list));
RemoveBack(list);
puts("4:");
Traverse(list);
RTraverse(list);
printf("Size: %d\n", Size(list));
RemoveFront(list);
puts("5:");
Traverse(list);
RTraverse(list);
printf("Size: %d\n", Size(list));
Clear(list);
for (i = 0; i < 10; ++i)
AddFront(list, &array2[i]);
puts("6:");
Traverse(list);
RTraverse(list);
printf("Size: %d\n", Size(list));
Destroy(list);
return 0;
}
/*
1:
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
Size: 10
2:
1 2 3 4 5 6 7 8 9 10 11
11 10 9 8 7 6 5 4 3 2 1
Size: 11
3:
12 1 2 3 4 5 6 7 8 9 10 11
11 10 9 8 7 6 5 4 3 2 1 12
Size: 12
4:
12 1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1 12
Size: 11
5:
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
Size: 10
6:
20 19 18 17 16 15 14 13 12 11
11 12 13 14 15 16 17 18 19 20
Size: 10
*/ 写这个主要是想给“有容就大”看看，我可是收了人家100分呢。
因为不能使用模板，所以我把每个结点的元素类型设置成了void*，这样就需要在获得元素值之后用强转来恢复其本意。而且跨函数使用时，数据不能是自动变量，必须是静态或动态分配的数据，这在头文件里有描述。
灵感有些来自于Java的util包里的LinkedList。不过遍历方式上还是有些不同的。
[ 本帖最后由 lz1091914999 于 2012-11-27 19:07 编辑 ]
