005-双向链表

moc

1、基本概念
单链表的结点只有一个指向下一个元素的结点指针；
单链表的数据元素无法直接访问其前驱元素；
逆序访问单链表极其耗时。
由于单链表没有指向前驱的指针导致这些不变，于是有了双向链表。
定义：
        在单链表的结点中增加了一个指向其前驱的pre指针。

拥有的操作：
        创建链表
        销毁链表
        获取链表长度
        清空链表
        获取链表的第pos个元素
        插入元素到pos位置
        删除pos位置的元素
循环链表的新增操作：
        将游标重置，即指向链表的第一个元素；
        获取当前游标指向的数据元素；
        将游标移动至上一个元素；
        将游标移动至下一个元素；
        直接指定删除链表中的某个数据元素。
双向链表的重点是 学会各种异常情况的处理。
2、设计与实现
1. 插入操作

current->next = node;
node->next = next;
next->pre = node;
node->pre = current;
注意特殊情况处理：   ① 插入第一个元素时的处理  ② 头插时候的处理

1. int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos)
   
2. {
   
3.         TDLinkList* tlist = (TDLinkList*)list;
   
4.         int ret = 0, i = 0;
   
5.         if (tlist == NULL || node == NULL || pos < 0)
   
6.         {
   
7.                 return -1;
   
8.         }
   
9. 
   
10. 
    
11.         DLinkListNode* current = (DLinkListNode*)tlist;
    
12.         DLinkListNode* next = NULL;  // 需要next指针
    
13. 
    
14.         for (i = 0; (i < pos) && (current->next != NULL); i++)
    
15.         {
    
16.                 current = current->next;
    
17.         }
    
18. 
    
19.         next = current->next;
    
20. 
    
21.         // 步骤1-2
    
22.         current->next = node;
    
23.         node->next = next;
    
24. 
    
25.         // 步骤3-4
    
26.         if (next != NULL)  // 当链表插入第一个元素时，需要特殊处理
    
27.         {
    
28.                 next->pre = node;
    
29.         }
    
30.         node->pre = current;
    
31. 
    
32.         if (tlist->length == 0)
    
33.         {
    
34.                 tlist->slider = node;  // 当链表插入第一个元素处理游标
    
35.         }
    
36. 
    
37.         // 若在0号位置插入，需要特殊处理  新结点的next需要pre指向null
    
38.         if (current == (DLinkListNode*)tlist)
    
39.         {
    
40.                 node->pre = NULL;
    
41.         }
    
42.         tlist->length++;
    
43. 
    
44.         return ret;
    
45. }

复制代码

2. 删除操作

current->next = next;
next->pre = current;
注意特殊情况处理：   ① 删除尾部元素时的处理  ②  删除头部元素时的处理  ③删除元素恰好是游标所指的元素时的处理

1. DLinkListNode* DLinkList_Delete(DLinkList* list, int pos)
   
2. {
   
3.         TDLinkList* tlist = (TDLinkList*)list;
   
4.         DLinkListNode* ret = NULL;
   
5.         int i = 0;
   
6.         if (tlist == NULL || pos < 0)
   
7.         {
   
8.                 return NULL;
   
9.         }
   
10. 
    
11. 
    
12.         DLinkListNode* current = (DLinkListNode*)tlist;
    
13.         DLinkListNode* next = NULL;  // 需要next指针
    
14. 
    
15.         for (i = 0; i < pos; i++)
    
16.         {
    
17.                 current = current->next;
    
18.         }
    
19. 
    
20.         ret = current->next;
    
21.         next = current->next;
    
22. 
    
23.         // 步骤1
    
24.         current->next = next;
    
25. 
    
26.         // 步骤2
    
27.         if (next != NULL)  // 需要特殊处理
    
28.         {
    
29.                 next->pre = current;
    
30.                 if (current == (DLinkListNode*)tlist)  // 若删除的第0号位置，需要特殊处理
    
31.                 {
    
32.                         next->pre = NULL;
    
33.                 }
    
34.         }
    
35. 
    
36.         if (tlist->slider == ret)
    
37.         {
    
38.                 tlist->slider = next;
    
39.         }
    
40.         tlist->length--;
    
41. 
    
42.         return ret;
    
43. }

复制代码

4、优点与缺点
优点：
        在单链表的基础上增加了指向前驱元素的指针；
        功能上可以完全取代单链表的使用， 可以高效遍历链表中的元素。
缺点：
        代码复杂。
完整代码： 双向链表.zip (2.08 KB, 下载次数: 8)

2018-9-24 12:23 上传

点击文件名下载附件
双向链表

sunwukong365

图示非常清晰, 解释的很明白, 谢谢!