侧边栏壁纸
博主头像
CoderKui

坐中静,舍中得,事上练

  • 累计撰写 51 篇文章
  • 累计创建 69 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

数据结构-链表

CoderKui
2021-10-25 / 0 评论 / 0 点赞 / 278 阅读 / 1,490 字 / 正在检测是否收录...

在说链表之前,有必要先聊聊数组,只有理解了数组的缺点,才能明白链表的好处。

数组是一种非常基础且常用的数据结构,它的形式表现与物理表现完全一致。

在C语言中,「 int a[5] 」就是申请一块连续内存,这块内存有5个单元,每个单元占据int类型的大小,一般为4字节。

而通过a[1]这样的下标形式来映射到实际内存完成对元素的访问(这里所说的实际内存其实是操作系统提供的虚拟内存机制,最终通过MMU才映射为实际物理内存)。

这种映射很简单,即内存地址 = 首地址 + 偏移量 * 单元大小

这里数组的首地址也就是1000,偏移量就是下标,单元大小就是数组类型的大小,int类型占据4字节。

所以这个例子中,a[1]这样下标形式访问就映射为「1000 + 1 * 4」这个内存地址。

可以发现,这样数组访问每个元素的复杂度都是O(1)的,性能非常好。

既然如此,为什么还需要链表?

链表出现的背景

链表的出现就是为了解决数组的一些弊端的,尽管数组支持O(1)的随机访问,但数组有两个核心缺陷:

1.内存不连续

数组的申请需要一块连续的内存,假设要申请1MB大小的数组,内存明明还剩余2MB,完全够,但却到不到一块连续的1MB内存,这2MB剩余内存是「离散」的。

此时申请1MB大小的数组则会失败:

而用链表可以解决这个问题,链表结构核心有两个部分:一个部分存放数据,另一个部分存放下一个元素的地址。

因为数组通过下标访问映射到实际内存,所以实际内存的申请必然是连续的,否则这个映射公式会很复杂。

而链表在内存不连续时依然可以分配,只要总内存大小够用就行。

2.解决动态扩容

内存的每次申请都需要指定一个大小,在程序较小时这个数值可以依靠经验提供。当程序越来越庞大,发展为工程时,这个初始分配的大小就很难做到「准确」。

太小了后续不够用,太大了浪费内存。因此急需一个解决数组不能动态扩容的数据结构,链表就能胜任这个需求。

当需要扩容时,申请一个结点,将新结点放在链表后面即可。

你可能说,这数组也能做到啊,但数组的扩容效率实在太低了。数组的扩容需要申请一个比原先大的新数组,再把旧数组的元素一个一个拷贝到新数组。

那你又说,为什么不在数组后面追加申请呢,别忘了,数据申请需要连续的内存空间,谁知道数组尾部后面的内存有没有被其他程序占用呢。

链表的种类

理解了数组的缺陷后,链表就此诞生。随着解决问题和提升效率的需要,链表又发展为多个类型,每种类型都有各自的应用场景。

  1. 单链表

    链表里面有两个结点比较特殊,一个是头结点,另一个是尾结点。头结点即链表第一个结点,知道了它地址,就可以顺序访问整个链表了。

    而尾结点的next的指向空,表示链表结束,通常循环遍历链表可以把尾结点判空来停止循环。

    数组的插入和删除元素都需要移动大量元素,时间复杂度为O(n)。而链表却可以做到O(1)复杂度的插入和删除。

    插入操作:

    删除操作:

  2. 循环链表

    实际上跟单链表差不多,只不过尾结点指向头结点,形成了「环」。

    在解决一些算法问题时会用到,例如「约瑟夫问题」,实际开发中很少用到这个结构。

  3. 双向链表

    就是在单链表的基础上,增加一个指针,指向前置结点。

    这种结构有很多好处,例如不经可以从头结点遍历,也可以从尾结点遍历。

    还有在进行插入和删除结点时,可以轻松知道前置结点,不需要再去遍历获取被删除或插入结点的前置结点了。

    双向链表无论是算法领域还是软件开发,都用的比较多,Java里「LinkedHashMap」底层就用到了双向链表。

  4. 双向循环链表

    听名字显然就是循环链表和双向链表的融合:

    END

    总的来说,虽然数组支持O(1)性能的随机访问,但「需要连续空间」和「不能动态扩容」这两大缺点催生了链表的诞生。

    链表不仅解决了这两大问题,还支持O(1)的插入和删除操作,在很多场景下提高了性能。

    而为了解决问题的需要和进一步提升效率,链表衍生出了很多改进版本。

0

评论区