双向循环链表（C语言描述）（二）

　　链表的基本操作基于对链表的遍历；计算链表的长度就是对链表进行一次遍历：

 1 int linkedlist_length(const LinkedList list) {
 2 　　assert(list);
 3     int length = 0;
 4     LinkedListNode * pCurNode = list->next;
 5 
 6     while (pCurNode != list) {
 7         length++;
 8         pCurNode = pCurNode->next;
 9     }
10 
11     return length;
12 }

　　双向链表有两个遍历方向，通过定义一个枚举类型，在遍历时指定遍历方向，在链表过长时可以节省遍历时间：

1 typedef enum {
2     TRAVELDIR_FORWARD, TRAVELDIR_BACKWARD
3 } LinkedListTravelDir;

　　向链表中插入元素时，首先申请新节点的内存空间，使工作指针（pCurNode）指向新节点插入位置的前一个节点，使新节点的前驱指针指向这个节点，后继指针指向这个节点的下一个节点（如下左图）；然后使插入位置前一个节点的后继指针指向新节点，使插入位置后一个节点的前驱指针指向新节点（如下右图），完成新节点的插入。

链表的头和尾不需要做特殊处理，函数linkedlist_insert()函数实现如下：

 1 void linkedlist_insert(LinkedList list, LinkedListTravelDir dir, int location,
 2         const LinkedListData data) {
 3     LinkedListNode * pCurNode = list;
 4     assert(location > 0 && location <= linkedlist_length(list) + 1);
 5 
 6     // alloc new node
 7     LinkedListNode * pNode = malloc(sizeof(LinkedListNode));
 8     assert(pNode);
 9     memcpy(&(pNode->data), &data, sizeof(LinkedListData));
10 
11     // move current pointer to prior node
12     if (dir == TRAVELDIR_FORWARD) {
13         for (int i = 0; i < location - 1; i++, pCurNode = pCurNode->next)
14             ;
15 
16     } else {
17         if (dir == TRAVELDIR_BACKWARD) {
18             for (int i = 0; i < location; i++, pCurNode = pCurNode->prior)
19                 ;
20         }
21     }
22 
23     // insert new node
24     pNode->next = pCurNode->next;
25     pNode->prior = pCurNode;
26     pCurNode->next = pNode;
27     pNode->next->prior = pNode;
28 }

因为节点数据是自定义数据类型，因此复制节点数据时使用memcpy()函数。

　　从链表中删除元素时，首先使工作指针（pCurNode）指向要删除的节点（如下左图），使它前一个节点的后继指针指向它的后一个节点，使它后一个节点的前驱指针指向它的前一个节点（如下右图），释放它的内存空间，完成节点的删除。

链表的头和尾同样不需要做特殊处理，函数linkedlist_delete()实现如下：

 1 void linkedlist_delete(LinkedList list, LinkedListTravelDir dir, int location) {
 2     LinkedListNode * pCurNode = list;
 3     assert(location > 0 && location < linkedlist_length(list) + 1);
 4 
 5     // move current pointer to the node will deleted
 6     if (dir == TRAVELDIR_FORWARD) {
 7         for (int i = 0; i < location; i++, pCurNode = pCurNode->next)
 8             ;
 9     } else {
10         if (dir == TRAVELDIR_BACKWARD) {
11             for (int i = 0; i < location; i++, pCurNode = pCurNode->prior)
12                 ;
13         }
14     }
15 
16     // delete current node
17     pCurNode->prior->next = pCurNode->next;
18     pCurNode->next->prior = pCurNode->prior;
19     free(pCurNode);
20 }

　　查找链表元素同样是对链表进行遍历，需要一个变量（location）用于记录遍历经过的节点数量；因为链表节点的数据域是自定义数据类型，函数linkedlist_locate()的第4个参数接收一个函数指针，它应该指向用于比较两个链表节点数据的函数，当两个链表节点数据相等时，这个函数应该返回0。由于链表中可能存在多个相同的元素，因此用于记录遍历经过节点数量的变量（location）和工作指针（pCurNode）是静态变量，当list参数传入值为空时，查找从上一个找到的位置开始；元素未找到，则返回-1：

 1 int linkedlist_locate(const LinkedList list, LinkedListTravelDir dir,
 2         const LinkedListData data, int (*fpCompare)(const void *, const void *)) {
 3     static int location = 0;
 4     static LinkedListNode * pCurNode = NULL;
 5 
 6     // if list argument is NULL, continue to start locate
 7     if (list) {
 8         location = 1;
 9         pCurNode = list->next;
10     }
11     assert(location && pCurNode);
12 
13     // locate data
14     while (pCurNode != list) {
15         if (!fpCompare(&(pCurNode->data), &data)) {
16             return location;
17         }
18         location++;
19         if (dir == TRAVELDIR_FORWARD) {
20             pCurNode = pCurNode->next;
21         } else {
22             if (dir == TRAVELDIR_BACKWARD) {
23                 pCurNode = pCurNode->prior;
24             }
25         }
26     }
27 
28     return -1;
29 }

　　获取元素的函数linkedlist_get()实现比较简单，它返回指向相应位置节点数据的指针，调用者可以通过这个指针修改数据而不会直接修改到节点的指针域：

 1 LinkedListData * linkedlist_get(LinkedList list, LinkedListTravelDir dir,
 2         int location) {
 3     LinkedListNode * pCurNode = list;
 4     assert(location > 0 && location < linkedlist_length(list) + 1);
 5 
 6     // move pointer to the node wanna get
 7     if (dir == TRAVELDIR_FORWARD) {
 8         for (int i = 0; i < location; i++, pCurNode = pCurNode->next)
 9             ;
10     } else {
11         if (dir == TRAVELDIR_BACKWARD) {
12             for (int i = 0; i < location; i++, pCurNode = pCurNode->prior)
13                 ;
14         }
15     }
16 
17     return &(pCurNode->data);
18 }

*本例中的图截取自Data Display Debugger，在Ubuntu Linux下可以使用apt-get命令安装它：

1 sudo apt-get install ddd