数据类型及API声明
双向链表是指链表的每个结点有两个指针域，一个next指针指向后继结点，一个previous指针指向前驱结点。另外，双向链表也包含一个游标slider。
1. //链表句柄 2. typedef void DoubleLinkedList; 3. 4. //链表结点 5. typedef struct DoubleLinkedListNode DoubleLinkedListNode; 6. 7. //链表头 8. typedef struct DoubleLinkedListHead DoubleLinkedListHead; 9. 10. DoubleLinkedList* DoubleLinkedList_Create(); 11. 12. void DoubleLinkedList_Destroy(DoubleLinkedList* list); 13. 14. void DoubleLinkedList_Clear(DoubleLinkedList* list); 15. 16. int DoubleLinkedList_Length(DoubleLinkedList* list); 17. 18. int DoubleLinkedList_Insert(DoubleLinkedList* list, DoubleLinkedListNode* node, int pos); 19. 20. DoubleLinkedListNode* DoubleLinkedList_Get(DoubleLinkedList* list, int pos); 21. 22. DoubleLinkedListNode* DoubleLinkedList_Delete(DoubleLinkedList* list, int pos); 23. 24. //按元素值删除指定某个结点 25. DoubleLinkedListNode* DoubleLinkedList_DeleteNode(DoubleLinkedList* list, DoubleLinkedListNode* node); 26. 27. //重置游标 28. DoubleLinkedListNode* DoubleLinkedList_Reset(DoubleLinkedList* list); 29. 30. //获取当前游标 31. DoubleLinkedListNode* DoubleLinkedList_Current(DoubleLinkedList* list); 32. 33. //游标下移 34. DoubleLinkedListNode* DoubleLinkedList_Next(DoubleLinkedList* list); 35. 36. //游标上移 37. DoubleLinkedListNode* DoubleLinkedList_Pre(DoubleLinkedList* list);
双向链表的API实现
双向链表结点结构体
链表结点包含了指向后继结点的指针和指向前驱结点的指针。
1. struct DoubleLinkedListNode 2. { 3. DoubleLinkedListNode* previous; 4. DoubleLinkedListNode* next; 5. };
表头结构体
表头包含一个链表结点结构体head，用于指向链表的0号结点，包含一个游标slider，用于指示当前结点，包含一个长度length，用于指示链表元素个数。
1. struct DoubleLinkedListHead 2. { 3. DoubleLinkedListNode head; 4. DoubleLinkedListNode* slider; 5. int length; 6. };
创建双向链表并返回双向链表的句柄
- 函数功能：创建一个双向链表并返回双向链表句柄，其实就是创建一个表头
- 函数参数：无
- 函数返回：表头
1. DoubleLinkedList* DoubleLinkedList_Create() 2. { 3. DoubleLinkedListHead* pHead = NULL; 4. pHead = (DoubleLinkedListHead*)malloc(sizeof(DoubleLinkedListHead)); 5. if (pHead == NULL) 6. { 7. printf("pHead = (DoubleLinkedListHead*)malloc(sizeof(DoubleLinkedListHead)) err\n"); 8. return NULL; 9. } 10. memset(pHead, 0, sizeof(DoubleLinkedListHead)); 11. return pHead; 12. }
销毁双向链表
- 函数功能：销毁双向链表就是释放表头资源，销毁双向链表前需要逐个删除链表结点
- 函数参数：双向链表的句柄
- 函数返回：无
1. void DoubleLinkedList_Destroy(DoubleLinkedList* list) 2. { 3. DoubleLinkedListHead* pHead = NULL; 4. if (list == NULL) 5. { 6. printf("err: list == NULL\n"); 7. return; 8. } 9. pHead = (DoubleLinkedListHead*)list; 10. free(pHead); 11. }
清空双向链表
- 函数功能：返回到双向链表刚创建的状态，即表头指针域指向NULL，长度置为0
- 函数参数：双向链表的句柄
- 函数返回：无
1. void DoubleLinkedList_Clear(DoubleLinkedList* list) 2. { 3. DoubleLinkedListHead* pHead = NULL; 4. if (list == NULL) 5. { 6. printf("err: list == NULL\n"); 7. return; 8. } 9. pHead = (DoubleLinkedListHead*)list; 10. pHead->head.next = NULL; 11. pHead->head.previous = NULL; 12. pHead->slider = NULL; 13. pHead->length = 0; 14. }
返回双向链表元素个数
- 函数功能：获取双向链表长度，即结点个数
- 函数参数：双向链表句柄
- 函数返回：结点个数
1. int DoubleLinkedList_Length(DoubleLinkedList* list) 2. { 3. DoubleLinkedListHead* pHead = NULL; 4. if (list == NULL) 5. { 6. printf("err: list == NULL\n"); 7. return -1; 8. } 9. pHead = (DoubleLinkedListHead*)list; 10. return pHead->length; 11. }
插入元素
- 函数功能：在双向链表中插入一个元素，被插入的元素已经在主调函数分配好内存，只需把链表结点DoubleLinkedListNode串接起来即可
- 函数参数：list 双向链表句柄 node 待插入元素 pos 插入位置
- 函数返回：成功返回0
1. int DoubleLinkedList_Insert(DoubleLinkedList* list, DoubleLinkedListNode* node, int pos) 2. { 3. int i = 0; 4. DoubleLinkedListHead* pHead = NULL; 5. DoubleLinkedListNode* pCurrent = NULL; 6. DoubleLinkedListNode* pNext = NULL; 7. if ((list == NULL) || (node == NULL) || (pos < 0)) 8. { 9. printf("err: (list == NULL) || (node == NULL) || (pos < 0)\n"); 10. return -1; 11. } 12. pHead = (DoubleLinkedListHead*)list; 13. pCurrent = &(pHead->head); 14. for (i = 0; i < pos; i++) 15. { 16. pCurrent = pCurrent->next; 17. } 18. pNext = pCurrent->next; 19. node->next = pNext; 20. pCurrent->next = node; 21. node->previous = pCurrent; 22. if (pNext != NULL) //见分析示意图：在尾部插入 23. { 24. //在尾部插入的时候，pNext = NULL 25. pNext->previous = node; 26. } 27. if (pCurrent == (DoubleLinkedListNode*)list) //见分析示意图，在0号位置插入 28. { 29. //在0号位置插入，要修正node->previous = pCurrent; 30. node->previous = NULL; 31. } 32. if (pHead->length == 0) 33. { 34. pHead->slider = node; 35. } 36. pHead->length++; 37. return 0; 38. }
插入元素时的异常处理
（1）普通位置插入
因为双向链表既有后继结点的指针，又有前驱结点的指针，所以需要两个辅助指针pCurrent和pNext。pCurrent指针为当前指针，初始位置指向head头结点，然后根据传入的参数pos往后移动pos步，要插入的元素就是当前pCurrent后面的位置，在插入前应保存原来的pos位处的结点，也就是pCurrent->next，因为被插入的node结点应放在pCurrent->next结点的前驱指针域中，所以就有了pNext = pCurrent->next的操作。
（2）尾部插入
尾部插入时会有一个异常情况，那就是pNext指向NULL，而NULL没有指针域，所以在尾部插入元素时，应该去掉pNext->previous = node这一步。
（3）头部位置插入
在头部插入，应该对node的previous域做修正，使它指向NULL，即node->previous = NULL。
（4）首次插入
首次插入的异常情况刚好是在头部插入和在尾部插入两种情况的综合，即(2)(3)中的分析。
