【数据结构与算法】-(4)双向链表和双向循环链表


【数据结构与算法】-(1)基础篇

【数据结构与算法】-(2)线性表基础

【数据结构与算法】-(3)循环链表(单向)

【数据结构与算法】-(4)双向链表和双向循环链表

【数据结构与算法】-(5)链表面试题解析

【数据结构与算法】-(6)栈

【数据结构与算法】-(7)队列

一、概念

双向链表

是在单链表的每个节点中,再设置一个指向其前驱结点的指针域。

所以在双向链表中的结点有两个指针域,一个指向直接后继,另一个指向直接前驱。

双向链表

双向循环链表:

与双向链表相比,双向循环链表的尾结点的next指向头结点,头结点的prior 指向尾结点,形成一个循环。如下图所示:

双向链表

创建代码如下:

#define ElemType int;
typedef struct DulNode
{
       ElemType data;
        struct DulNode *prior            /*直接前驱指针*/
        struct DulNode *next            /*直接后继指针*/
} DulNode, *DuLinkList;

二、双向链表的操作

2.1 创建链表

创建双向链表的步骤如下:

  1. 创建空链表L,以及结点*L
  2. 指定一个尾结点为p
  3. 创建临时结点temp,并进行数值给定
  4. 将当前尾结点ptemp进行双线链接链接
    1. tempp 的后继
    2. ptemp 的前驱
  5. temp 赋值给pp依然为链表的尾结点。
    // ① 创建*L 指向头结点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;

    //② 新建一个尾结点 p
    LinkList p = *L;
    for(int i=0; i < 10;i++){

        // ③ 创建1个临时的结点
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;

        // ④ 为新增的结点建立双向链表关系
          // 1  temp 是p的后继
        p->next = temp;
          // 2 temp 的前驱是p
        temp->prior = p;
     // ⑤ p 要记录最后的结点的位置,方便下一次插入 
        p = p->next;

    }

2.2 增加结点

向双向链表种添加结点的步骤和单向链表添加结点类似,只是多了一步链接前驱的工作。

步骤如下:

  1. 新建目标结点temp
  2. 创建指针 p ,指向链表的头结点
  3. 通过循环便利,将 p 向后移,找到插入位置 i 的结点
    1. 【判断】如果插入位置超出链表本身长度,跳出
    2. 【判断】如果 p 为链表尾部,只需做 ptemp首尾相连
  4. 找到i 结点后,分两步对ptemp 进行首尾相连
    1. 将原pnextprior 指向 目标结点temp
    2. 将目标结点的next 指向 pnext
    3. pnext 指向目标结点 temp
    4. 将 目标结点 tempprior 指向 p

注意:这里的第四步中,第1,2两步必须先于3,4两步执行,否则先将ptemp,关联上,会导致原pnext 丢失,成为野指针。

画个图表示一下流程:

双向链表-插入结点

Status ListInsert(LinkList *L, int i, ElemType data){

    //1. 插入的位置不合法 为0或者为负数
    if(i < 1) return ERROR;

    //2. 新建结点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;

    //3.将p指向头结点!
    LinkList p = *L;

    //4. 找到插入位置i直接的结点
    for(int j = 1; j < i && p;j++)
        p = p->next;

    //5. 如果插入的位置超过链表本身的长度
    if(p == NULL){
        return  ERROR;
    }
    //6. 判断插入位置是否为链表尾部;
    if (p->next == NULL) {

        p->next = temp;
        temp->prior = p;
    }
      else
    {
        //1️⃣ 将p->next 结点的前驱prior = temp
        p->next->prior = temp;
        //2️⃣ 将temp->next 指向原来的p->next
        temp->next = p->next;
        //3️⃣ p->next 更新成新创建的temp
        p->next = temp;
        //4️⃣ 新创建的temp前驱 = p
        temp->prior = p;
    }

    return  OK;
}

2.3 删除结点

删除链表中的结点分两种:删除指定位置结点和删除指定元素的结点。其思路都是一致的,遍历链表中的元素,找到指定元素,并进行删除。主要流程与删除单向链表的逻辑类似,只是多了一个移除前驱结点的操作。

删除结点的通俗理解:就好比员工离职前,必要的一步就是工作交接,告诉大家接下来工作时谁来接手,锅该由谁来背,公司才能正常运行;否则你一拍屁股删库跑路了,公司可就热闹了,大家都抓瞎了,这样就乱套了。

2.3.1 删除指定位置结点

流程如下:

  1. 给定一个工具结点p,指向链表的头结点
  2. 依次循环查找,将 p 指向删除位的前一个
  3. 创建临时结点 temp 指向要删除的结点,并把该结点 data 赋值给返回的 *e
  4. 待删除结点上一结点的 next 指向 temp 的后一个结点
  5. 待删除结点是否链尾结点?
    • 并非链尾:将待删除结点 temp 的下一结点的 prior 指向工具结点p
    • 是链尾:不作处理
  6. 释放待删除结点 temp

总结一下,核心操作就两步:

  • 将目标上一个结点的 next 指给下一个
  • 将目标的下一个结点的 prior 指给上个结点

有图有真相:

双向链表-删除指定位置结点

贴一下实操的代码如下:

Status DeleteVeryNode(LinkList *L, int i, ElemType *e){
    int k = 1;
    LinkList p = (*L);
    //1.判断双向链表是否为空,如果为空则返回ERROR;
    if (*L == NULL) {
        return ERROR;
    }
    //2. 将指针p移动到删除元素位置前一个
    while (k < i && p != NULL) {
        p = p->next;
        k++;
    }
    //3.如果k>i 或者 p == NULL 则返回ERROR
    if (k>i || p == NULL) {
        return  ERROR;
    }
    //4.创建临时指针temp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
    LinkList temp = p->next;
    *e = temp->data;
    //5. p->next 等于要删除的结点的下一个结点
    p->next = temp->next;
    //6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
    if (temp->next != NULL) {
        temp->next->prior = p;
    }
    //7.删除temp结点
    free(temp);
    return OK;
}

2.3.2 删除指定元素的结点

删除指定元素的结点,会更简单,只需要遍历循环,找到相应的结点后,依次对前驱点和后继点进行重新配置。

步骤如下:

  1. 创建链表L, 将p 指向首结点。
  2. 遍历链表L,判断给定元素 datap-> data是否相等,相等即找到目标结点
  3. 修改目标结点的前驱结点后继指针,指向目标结点下一个结点(交代后事….)
  4. 若删除结点非尾结点:修改目标结点后继结点的前驱指针 prior,指向目标的上一个结点。
  5. 释放被删除的结点 p

双向链表-删除指定元素结点

贴一下实操的代码如下:

Status DeleteDefinedNode(LinkList *L, int data){
    // 1. 创建链表,以及头结点 p
    LinkList p = *L;
    //1.遍历双向循环链表
    while (p) {
        //2.判断当前结点的数据域和data是否相等,若相等则删除该结点
        if (p->data == data) {
            //修改被删除结点的前驱结点的后继指针
            p->prior->next = p->next;
            //修改被删除结点的后继结点的前驱指针
            if(p->next != NULL){
                p->next->prior = p->prior;
            }
            //释放被删除结点p
            free(p);
            //退出循环
            break;
        }
        //没有找到该结点,则继续移动指针p
        p = p->next;
    }
    return OK;
}

2.4 查询结点

  1. 创建链表L, 将p 指向首结点。
  2. 遍历链表L,判断给定元素 datap-> data是否相等,
    1. 相等即找到目标结点,跳出。
    2. 否则继续循环,将 p 移动到下一个结点
int selectElem(LinkList L,ElemType elem){
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == elem) {
            return i;
        }
        i++;
        p = p->next;
    }
    return  -1;
}

2. 5 更新结点

更新结点,只需要遍历循环链表,找到序号内的结点,将其数据域 data 替换为新的数据

Status replaceLinkList(LinkList *L,int index,ElemType newElem){
    LinkList p = (*L)->next;

    for (int i = 1; i < index; i++) {
        p = p->next;
    }

    p->data = newElem;
    return OK;
}

三、双向循环链表的操作

3.1 创建链表

双向循环链表的创建步骤,与双向链表类似。差别在于:多了将尾结点的 next 指向 头结点,而头结点的 prior 指向 尾结点。

具体步骤:

  1. 创建空链表L,以及结点*L,使得其前驱和后继都指向自己
  2. 指定一个尾结点为p
  3. 创建临时结点temp,并进行数值给定
  4. 将当前尾结点ptemp进行双线链接链接
    1. tempp 的后继
    2. ptemp 的前驱
    3. temp 的后继是 p
    4. p 的前驱是新建的 temp
  5. temp 赋值给pp依然为链表的尾结点,方便下次插入新结点

实现源码如下:

Status creatCircularLinkList(LinkList *L){
    // 1 创建空链表
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) {
        return ERROR;
    }
    (*L)->next = (*L);
    (*L)->prior = (*L);
    // 指定一个尾结点为 p
    LinkList p = *L;
    for(int i=0; i < 10;i++){
        //1.创建1个临时的结点
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->data = i;
        //2.为新增的结点建立双向链表关系
        //① temp 是p的后继
        p->next = temp;
        //② temp 的前驱是p
        temp->prior = p;
        //③ temp的后继是*L
        temp->next = (*L);
        //④ p 的前驱是新建的temp
        p->prior = temp;
        //⑤ p 要记录最后的结点的位置,方便下一次插入
        p = p->next;
    }
    return OK;
}

3.2 增加结点

与双向链表相似,区别在于双向循环链表由于有首位域,在找到指定位置后,需要先将插入结点的priornext 与 前后建立关系,之后再考虑前结点的 next链接,最后考虑的是 目标结点的next

具体步骤如下:

  1. 新建目标结点temp
  2. 创建指针 p ,指向链表的头结点
  3. 通过循环便利,将 p 向后移,找到插入位置 i 的结点
    1. 【判断】如果插入位置超出链表本身长度,跳出
    2. 【判断】如果 pnext指向 头结点跳出
  4. 找到i 结点后,分两步对ptemp 进行首尾相连
    1. tempprior 指向 p
    2. tempnext 指向 pnext
    3. pnext 指向目标结点 temp
    4. 判断 temp 是否是尾结点
      1. 如果是:将头结点的 prior 指向 temp
      2. 如果否:将目标结点 tempprior 指向 p
Status LinkCircularListInsert(LinkList *L, int index, ElemType e){

    //1. 创建指针p,指向双向链表头
    LinkList p = (*L);
    int i = 1;

    //2.双向循环链表为空,则返回error
    if(*L == NULL) return ERROR;

    //3.找到插入前一个位置上的结点p
    while (i < index && p->next != *L) {
        p = p->next;
        i++;
    }

    //4.如果i>index 则返回error
    if (i > index)  return ERROR;

    //5.创建新结点temp
    LinkList temp = (LinkList)malloc(sizeof(Node));

    //6.temp 结点为空,则返回error
    if (temp == NULL) return ERROR;

    //7.将生成的新结点temp数据域赋值e.
    temp->data = e;

    //8.将结点temp 的前驱结点为p;
    temp->prior = p;
    //9.temp的后继结点指向p->next;
    temp->next = p->next;
    //10.p的后继结点为新结点temp;
    p->next = temp;

    //如果temp 结点不是最后一个结点
    if (*L != temp->next) {
        //11.temp节点的下一个结点的前驱为temp 结点
        temp->next->prior = temp;
    }else{
        (*L)->prior = temp;

    }
    return OK;
}

3.3 删除结点

双向循环链表的结点删除,比双向链表的简单,因为链表首尾相连的特性,不需要考虑是否为尾结点或者头结点。

流程如下:

  1. 给定一个工具结点p,指向链表的头结点
  2. 依次循环查找,将 p 指向删除位的前一个
  3. 创建临时结点 temp 指向要删除的结点,并把该结点 data 赋值给返回的 *e
  4. 待删除结点上一结点的 next 指向 temp 的后一个结点
  5. 释放待删除结点 temp

总结一下,核心操作就两步:

  • 将目标上一个结点的 next 指给下一个
  • 将目标的下一个结点的 prior 指给上个结点
Status LinkListDelete(LinkList *L,int index,ElemType *e){
    int i = 1;
    LinkList temp = (*L)->next;
    if (*L == NULL) {
        return  ERROR;
    }
    //①.如果删除到只剩下首元结点了,则直接将*L置空;
    if(temp->next == *L){
        free(*L);
        (*L) = NULL;
        return OK;
    }
    //1.找到要删除的结点
    while (i < index) {
        temp = temp->next;
        i++;
    }
    //2.给e赋值要删除结点的数据域
    *e = temp->data;
    //3.修改被删除结点的前驱结点的后继指针 
    temp->prior->next = temp->next;
    //4.修改被删除结点的后继结点的前驱指针
    temp->next->prior = temp->prior;
    //5. 删除结点temp
    free(temp);
    return OK;
}

3.4 查询结点

与双向链表相同,更新结点,只需要遍历循环链表,找到序号内的结点,将其数据域 data 替换为新的数据

代码参见 2.5

四、总结

4.1 线性表结构

线性表·结构

4.2 顺序表与链表比较

顺序结构的线性表与链式结构的线性表比较起来,

从空间性能上比较

  1. 存储空间分配

  2. 存储密度的大小

存储密度 = $\frac{数据元素本身占用存储量}{结点结构占用的存储量}$

时间性能比较:

  1. 存储元素的效率
  2. 插入和删除操作的效率

4.3 其他

双向链表比起单向链表来说,增加了prior 这一指针域,可以在查找和删除时,极其迅速的操作,无须做更多的判断,极大地提高了运算效率。同时在操作时,需要注意指针修改顺序,以免形成野指针。


文章作者: 李佳
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 李佳 !
评论
 上一篇
【底层探索】- KVO(下)自定义KVO 【底层探索】- KVO(下)自定义KVO
序上文中,初步探索了KVO的使用以及背后的实现原理,这次来自己实现一个KVO,一方面在过程中加深理解,另一方面可以感受一下使用场景。 根据上文总结,KVO的实现一共有3部分: 添加KVO监听方法 KVO 通知实现方法 KVO 移除方法
2020-04-04 李佳
下一篇 
【底层探索】- KVO(上) 【底层探索】- KVO(上)
一、KVO 初探1.1 概念 Key-value observing is a mechanism that allows objects to be notified of changes to specified properties
2020-04-03 李佳
  目录