数据结构与算法 - 双向链表

本文首发于 个人博客

之前的 一篇文展 我们讲述了单链表的概念和实现,我们知道单向链表只有一个方向的,每一个节点只能找到其直接后继节点也就是 next 指针,当我们要找到一个节点只能从单链表头处循环判断,在我们需要直接找到一个节点的前驱节点的时候,我们就需要扩展我们的数据结构让其支持这种逻辑,其大概结构是:

双向链表单节点.jpg

这样我们就很容易写出其数据结构:

typedef struct Node {
    struct Node *prior;
    ListData data;
    struct Node *next;
} Node;
双向链表图解.jpg

双向链表

双向链表最终会展示成这样子(本篇文章默认都是 带头节点的链表

  • 除尾节点外,每一个节点的的 prior指针 都指向前一个节点
  • 除头节点外,每一个节点的 next指针 都指向后一个节点

初始化

同样我们还是使用尾插法来初始化指定数值的双向链表

Node * InitList(int total)  {
    //创建头节点 
    Node *list = (Node *)malloc(sizeof(Node));
    if (list == NULL) return ERROR;
    list->prior = NULL;
    list->next = NULL;
    list->data = -1;

    Node *target = list;
    Node *temp;
    for (int i = 1; i <= total; i ++) {
        temp = (Node *)malloc(sizeof(Node));
        temp->data = i;
        temp->prior = target;
        temp->next = NULL;
        target->next = temp;
        target = target->next;
    }
    return list;
}

打印

打印方法就比较简单了

// 打印链表
void PrintList (Node *list) {
    if (list == NULL) {
        printf("啥都没有\n");
        return;
    }
    Node *target = list->next;
    if (target == NULL) {
        printf("链表为空 \n");
        return;
    }
    while (target) {
        printf("%d - ",target->data);
        target = target->next;
    }
    printf("\n");
}

插入数据

双向链表插入数据.jpg

找到要插入的前一个节点 target,比如我们要插入顺序3的位置,那么就要找位置2的节点

  1. 新节点 Tempnext 指向 targetnext
  2. 新节点 Tempprior 指向 target
  3. targetnext 指向 Temp
  4. target-> nextprior 指向 Temp
// 指定位置插入节点
Status InserListData(Node **list,int location, ListData data) {
    Node *target = *list;
    int i ;
    // 找到要插入的前一个节点
    for (i = 1; i < location && target; i ++) {
        target = target->next;
    }
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->data = data;
    temp->next = target->next;
    temp->prior = target;
    target->next = temp;
    temp->next->prior = temp;
    return SUCCESS;
}

删除数据

双向链表删除数据.jpg
  1. 找到要删除的节点,并用 target 对齐进行保留
  2. target 前驱节点的 next 指向 target 的 后驱节点
  3. target 后驱节点的 prior 指向 target 的 前驱节点
  4. 释放 target
// 删除指定位置的节点
Status DeleteData(Node **list,int location, ListData *data) {
    if (location <= 0) return ERROR;
    Node *target = *list;
    // 找到要删除的节点
    int i;
    for (i = 0; i < location && target != NULL; i ++) {
        target = target->next;
    }
    if (i > location || target == NULL) {
        return ERROR;
    }
    target->prior->next = target->next;
    if (target->next != NULL) {
        target->next->prior = target->prior;
    }
    *data = target->data;
    free(target);
    return SUCCESS;
}

当然你也可以用另外一个变量保存要删除节点的前驱节点,这里因为考虑是双向链表,单单一个要删除的节点变量就够用了。

验证

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    Node *list = InitList(3);
    printf("打印双向链表: \n");
    PrintList(list);

    InserListData(&list,2,998);
    printf("第2个位置插入998之后打印: \n");
    PrintList(list);

    ListData data;
    Status status = DeleteData(&list, 2,&data);
    printf("删除第二个位置的节点之后打印: \n");
    PrintList(list);
    if (status == SUCCESS) {
        printf("被删除的数字是: %d\n",data);
    }
    return 0;
}
----------------------------- 打印数据
Hello, World!
打印双向链表: 
1 - 2 - 3 - 
第2个位置插入998之后打印: 
1 - 998 - 2 - 3 - 
删除第二个位置的节点之后打印: 
1 - 2 - 3 - 
被删除的数字是: 998
Program ended with exit code: 0

双向循环链表

跟单向循环链表一样,双向循环链表其实节点结构不变,只是首尾相连而已,其大致像这样:

双向循环链表.jpg

那么我们初始化一个空的双向循环链表应该是这样:

空双向循环链表.jpg

这里图形逻辑同双向链表差不多,我们不做过多的图形展示,以下仅以代码概述。

循环链表初始化

#define SUCCESS 1
#define ERROR 0

typedef int ListData;
typedef int Status;

typedef struct Node {
    struct Node *prior;
    ListData data;
    struct Node *next;
} Node;

typedef Node* LinkList;

Status CreatList (LinkList *L, int n) {
    *L = (LinkList)malloc(sizeof(Node));
    if (!*L) return ERROR;
    LinkList list = *L;
    Node *target = list;
    // 自己指向自己
    list->next = list;
    list->prior = list;
    // 新增数据
    for (int i = 1; i <= n; i ++) {
        Node *temp = (Node *)malloc(sizeof(Node));
        temp->data = i;
        temp->next = list;
        list->prior = temp;
        target->next = temp;
        temp->prior = target;
        target = target->next;
    }
    return SUCCESS;
}

初始化的时候,我们注意空链表的时候创建的头节点都指向自己即可,其他新加的数据都默认采用后插法插入到链表中。

循环链表插入节点

Status InsertData(LinkList *L,int location, ListData data) {
    // 找到要插入位置的前一个位置的节点
    Node *target = *L;
    if (!target) return ERROR;
    int i;
    for (i = 1; i < location && target->next != *L; i ++) {
        target = target->next;
    }
    // 超出范围
    if (i < location) return ERROR;
    Node *temp = (Node *)malloc(sizeof(Node));
    if (!temp) return ERROR;
    temp->data = data;
    temp->next = target->next;
    temp->next->prior = temp;
    target->next = temp;
    temp->prior = target;
    return SUCCESS;
}

思路依旧是找到要插入节点的前一个节点,然后通过后插法的逻辑来进行插入数据,细节方面就是要注意超出范围的判断以及循环的时候到尾节点就结束了,不能绕圈圈。

循环链表删除节点

Status DeleteData(LinkList *L,int location, ListData *data) {
    if (*L == NULL) return ERROR;
    Node *target = (*L)->next;
    // 如果只剩下首元节点,直接清空*L
    if (target->next == *L) {
        free(*L);
        (*L) = NULL;
        return SUCCESS;
    }
    for (int i = 1; i <= location && target->next != *L; i ++) {
        target = target->next;
    }
    target->prior->next = target->next;
    target->next->prior = target->prior;
    *data = target->data;
    free(target);
    return SUCCESS;
}

删除节点这里有个细节就是如果只剩下 首元节点 就对链表进行清空,注意这里不是头节点,而是判断首元节点。

打印循环链表

Status PrintList(LinkList L) {
    if (L == NULL) {
        printf("空链表");
        return ERROR;
    }
    printf("双向循环链表的内容: ");
    Node *target = L->next;
    while (target != L) {
        printf("%d--",target->data);
        target = target->next;
    }
    printf("\n");
    return SUCCESS;
}

验证

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    LinkList list;
    CreatList(&list, 10);
    printf("初始化带10个数据的双向循环链表的数据是:\n");
    PrintList(list);

    InsertData(&list, 3, 44);
    printf("第三个位置插入44后打印:\n");
    PrintList(list);

    InsertData(&list, 20, 999);
    printf("第20个位置插入999后打印:\n");
    PrintList(list);

    ListData data;
    DeleteData(&list, 3, &data);
    printf("删除第3个节点之后打印:\n");
    PrintList(list);
    printf("删除的数据是:%d \n",data);

    return 0;
}
---------------------------------打印结果
Hello, World!
初始化带10个数据的双向循环链表的数据是:
双向循环链表的内容: 1--2--3--4--5--6--7--8--9--10--
第三个位置插入44后打印:
双向循环链表的内容: 1--2--44--3--4--5--6--7--8--9--10--
第20个位置插入999后打印:
双向循环链表的内容: 1--2--44--3--4--5--6--7--8--9--10--
删除第3个节点之后打印:
双向循环链表的内容: 1--2--3--4--5--6--7--8--9--10--
删除的数据是:44 
Program ended with exit code: 0

总结

双向链表和双向循环链表的节点在结构上是一模一样的,不同之处就是一个首尾相连构成一个闭环,希望这篇文章能够将双向链表的逻辑和实现讲清楚,还望不吝赐教。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,033评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,725评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,473评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,846评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,848评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,691评论 1 282
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,053评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,700评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,856评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,676评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,787评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,430评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,034评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,990评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,218评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,174评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,526评论 2 343

推荐阅读更多精彩内容