鱼C论坛

 找回密码
 立即注册
查看: 1883|回复: 1

[学习笔记] 005-双向链表

[复制链接]
发表于 2018-9-24 12:23:59 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 moc 于 2018-9-24 12:23 编辑

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

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

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)

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-5-22 15:17:38 | 显示全部楼层
图示非常清晰, 解释的很明白, 谢谢!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 23:01

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表