005-双向链表

moc

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)

2018-9-24 12:23 上传

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

sunwukong365

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