|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 moc 于 2018-9-24 12:23 编辑
1、基本概念
单链表的结点只有一个指向下一个元素的结点指针;
单链表的数据元素无法直接访问其前驱元素;
逆序访问单链表极其耗时。
由于单链表没有指向前驱的指针导致这些不变,于是有了双向链表。
定义:
在单链表的结点中增加了一个指向其前驱的pre指针。
拥有的操作:
创建链表
销毁链表
获取链表长度
清空链表
获取链表的第pos个元素
插入元素到pos位置
删除pos位置的元素
循环链表的新增操作:
将游标重置,即指向链表的第一个元素;
获取当前游标指向的数据元素;
将游标移动至上一个元素;
将游标移动至下一个元素;
直接指定删除链表中的某个数据元素。
双向链表的重点是 学会各种异常情况的处理。
2、设计与实现
1. 插入操作
current->next = node;
node->next = next;
next->pre = node;
node->pre = current;
注意特殊情况处理: ① 插入第一个元素时的处理 ② 头插时候的处理
- int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos)
- {
- TDLinkList* tlist = (TDLinkList*)list;
- int ret = 0, i = 0;
- if (tlist == NULL || node == NULL || pos < 0)
- {
- return -1;
- }
- DLinkListNode* current = (DLinkListNode*)tlist;
- DLinkListNode* next = NULL; // 需要next指针
- for (i = 0; (i < pos) && (current->next != NULL); i++)
- {
- current = current->next;
- }
- next = current->next;
- // 步骤1-2
- current->next = node;
- node->next = next;
- // 步骤3-4
- if (next != NULL) // 当链表插入第一个元素时,需要特殊处理
- {
- next->pre = node;
- }
- node->pre = current;
- if (tlist->length == 0)
- {
- tlist->slider = node; // 当链表插入第一个元素处理游标
- }
- // 若在0号位置插入,需要特殊处理 新结点的next需要pre指向null
- if (current == (DLinkListNode*)tlist)
- {
- node->pre = NULL;
- }
- tlist->length++;
- return ret;
- }
复制代码
2. 删除操作
current->next = next;
next->pre = current;
注意特殊情况处理: ① 删除尾部元素时的处理 ② 删除头部元素时的处理 ③删除元素恰好是游标所指的元素时的处理
- DLinkListNode* DLinkList_Delete(DLinkList* list, int pos)
- {
- TDLinkList* tlist = (TDLinkList*)list;
- DLinkListNode* ret = NULL;
- int i = 0;
- if (tlist == NULL || pos < 0)
- {
- return NULL;
- }
- DLinkListNode* current = (DLinkListNode*)tlist;
- DLinkListNode* next = NULL; // 需要next指针
- for (i = 0; i < pos; i++)
- {
- current = current->next;
- }
- ret = current->next;
- next = current->next;
- // 步骤1
- current->next = next;
- // 步骤2
- if (next != NULL) // 需要特殊处理
- {
- next->pre = current;
- if (current == (DLinkListNode*)tlist) // 若删除的第0号位置,需要特殊处理
- {
- next->pre = NULL;
- }
- }
- if (tlist->slider == ret)
- {
- tlist->slider = next;
- }
- tlist->length--;
- return ret;
- }
复制代码
4、优点与缺点
优点:
在单链表的基础上增加了指向前驱元素的指针;
功能上可以完全取代单链表的使用, 可以高效遍历链表中的元素。
缺点:
代码复杂。
完整代码:
双向链表.zip
(2.08 KB, 下载次数: 8)
|
|