005-双向链表
本帖最后由 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、优点与缺点
优点：
在单链表的基础上增加了指向前驱元素的指针；
功能上可以完全取代单链表的使用， 可以高效遍历链表中的元素。
缺点：
代码复杂。
完整代码：
图示非常清晰, 解释的很明白, 谢谢!
页:
[1]