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

PS:前面已经说过线性表的两种表现形式,一种是顺序,另一种是链式,链式的一种普通表现形式就是加入一个指针,前一个的指针指向后一个结点的地址,那么还有一种形式就是双向链表,里面又加上了一个指针变量,让前指针变量指向直接前驱,后指针变量指向直接后继。

/**
 * 创建结构体
 * */
typedef struct DoubleLink {
    int data;
    struct DoubleLink *prior;
    struct DoubleLink *next;
} DoubleLink, *DoubleLinkL;

创建双向链表并初始化

注:这里我们是只创建了一个空的链表,内部无数据,所以首结点的两个指针变量要为NULL。

/**
 * 初始化
 * */
DoubleLinkL initLink() {
    DoubleLinkL L = (DoubleLinkL) malloc(sizeof(DoubleLink));
    L->next = NULL;
    L->prior = NULL;
    return L;
}

开始插入数据

在插入数据之前我们要考虑一个事情就是,链表中有数据和无数据的插入是否一样,也就是说指针改变是否一致,在左右都有值的时候平时要改变4条线,那么如果只有首结点的话移动几条呢。

其实可以说是移动3条,但画图的话就看到两条。

如图:

::|::

首先当只要一个首结点或者在最后一个结点插入的情况下,如第一个图,

     s->next = p->next;
        s->prior = p;
        p->next = s;

当前后都有结点的时候,如第二个图

     s->next = p->next;
        s->prior = p;
        p->next = s;
        s->next->prior = s;

整体插入代码就是

int insertLink(DoubleLinkL &L, int pos, int e) {
    DoubleLinkL p = L;
    int i = 0;
    while (p && i < pos-1) {
        p = p->next;
        i++;
    }
    if (!p || i > pos-1) {
        printf("插入失败,下标问题\n");
        return -1;
    }
    DoubleLinkL s = (DoubleLinkL) malloc(sizeof(DoubleLink));
    s->data = e;
    if (p->next == NULL) {
        s->next = p->next;
        s->prior = p;
        p->next = s;
    } else {
        s->next = p->next;
        s->prior = p;
        p->next = s;
        s->next->prior = s;
    }
    return 0;
}

删除图解

对于删除比较简单,在前后都有结点的情况下,如图一,如果本来只要一个结点,前面是首结点的情况下,直接把首结点的next指向NULL即可。(本人画图不怎么样不要在意)

p->next->next->prior=p;//一定要写在该位置。
p->next=p->next->next;

如果首结点后只有一个结点

p->next=NULL;

删除全部代码

int deleteLink(DoubleLinkL &L,int pos,int e){
    DoubleLinkL p = L;
    int i = 0;
    while (p && i < pos-1) {
        p = p->next;
        i++;
    }
    if (!p || i > pos-1) {
        printf("插入失败,下标问题\n");
        return -1;
    }
    if(p->next==NULL){
        p->next=NULL;
    }else{
        p->next->next->prior=p;//一定要写在该位置。
        p->next=p->next->next;
    }
    return 0;
 }

修改和查找

这个修改和查找是比较简单的,直接找到知道该结点修改就完事了,干就对了。

 int getElem(DoubleLinkL L,int pos){
     DoubleLinkL p = L;
     int i = 0;
     while (p && i < pos) {
         p = p->next;
         i++;
     }
     if (!p || i > pos) {
         printf("查找失败,下标问题\n");
         return -1;
     }
     printf("查找的数据:%d\n",p->data);
     return 0;
 }
 int updataLink(DoubleLinkL &L,int pos,int e){
     DoubleLinkL p = L;
     int i = 0;
     while (p && i < pos) {
         p = p->next;
         i++;
     }
     if (!p || i > pos) {
         printf("修改失败,下标问题\n");
         return -1;
     }
     p->data=e;
     return 0;
 }

总结:双向链表主要是插入和删除复杂点,其他的和单链表都差不多,双向链表存在着4条指向线先后顺序,如果连接顺序不正确,断开后的数据就会丢失。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Kevin-ZhangCG

Java集合总结

16920
来自专栏Golang语言社区

Golang语言--布尔型和数值类型

布尔类型 布尔类型是 bool。Go语言提供了内置的布尔值true和flase。Go语言支持标准的逻辑和比较操作。这些操作的结果都是布尔值。 布尔值和表达式可以...

39280
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高二十】集合指定初始容量&asList缺陷&subList缺陷

【Java提高二十】集合指定初始容量 &asList缺陷&subList缺陷 集合指定初始容量 集合是我们在Java编程中使用非常广泛的,它就像大海,海纳百川,...

39070
来自专栏码代码的陈同学

Java基础之你会在foreach遍历集合时进行remove操作吗?

当通过for循环遍历集合时,一般禁止操作(add or remove)集合元素。虽然开发规范里写的非常清楚,但最近还是有人掉坑里导致出了一个小BUG,那我们就一...

16960
来自专栏积累沉淀

Java设计模式(十六)----迭代子模式

迭代子模式 一、 概述 二、 结构 1.白箱聚集与外禀迭代子 2.黑箱聚集与内禀迭代子 主动...

224100
来自专栏Android机器圈

数据结构----线性表顺序和链式结构的使用(c)

PS:在学习数据结构之前,我相信很多博友也都学习过一些语言,比如说java,c语言,c++,web等,我们之前用的一些方法大都是封装好的,就java而言,里面使...

11530
来自专栏Android开发指南

13:常用类

37580
来自专栏Golang语言社区

[Go语言]实现可以枚举的map

在golang-nuts上看到有人问怎么样去枚举一个map。在go语言层面,并不支持支持枚举map,也就是说你不能获得一个枚举器在任意时刻去枚举这个map,只能...

38670
来自专栏Java爬坑系列

【Java入门提高篇】Day19 Java容器类详解(二)Map接口

  上一篇里介绍了容器家族里的大族长——Collection接口,今天来看看容器家族里的二族长——Map接口。

279190
来自专栏desperate633

LeetCode 17. Letter Combinations of a Phone Number题目分析代码

以上的答案是按照词典编撰顺序进行输出的,不过,在做本题时,你也可以任意选择你喜欢的输出顺序。

8710

扫码关注云+社区

领取腾讯云代金券