前言
hello, 我是 snow, 因个人原因在专栏中消失了很长时间, 想了很多不该想的, 做了很多不该做的. 偶尔发一些沸点来刷存在感. 感谢掘金, 相比朋友圈我更喜刷沸点, 因为在这里我能找到共鸣. 好了, 忽略.
链表
今天来了解下数据结构中的链表含义.
1 链表和数组的区别
数组是需要一块连续的内存空间来存储, 对内存的要求比较高. 而链表却相反, 它并不需要一块连续的内存空间. 链表是通过指针将一组零散的内存块串联在一起.
相比数组, 链表是一种稍微复杂一点的数据结构. 当然, 两者没有好坏之分, 各有各的优缺点.
数组可以快速的查找某个元素, 但是在插入和删除时就要移动大量元素. 原因就在于相邻元素的存储位置也具有邻居关系. 他们的编号是 0,1,2,3,4,...,n, 它们在内存中的位置也是紧挨着的, 中间没有空隙, 所以就无法快速添加元素. 而当删除后, 当中就会留出空隙, 自然需要弥补.
所以我们需要这样一种数据结构: 我们反正也是要让相邻元素间留有足够余地, 那干脆所有的元素都不要考虑相邻位置了, 哪有空位就到哪里, 只是让每个元素知道它下一个元素的位置在哪里. 我们可以在第一个元素时, 就知道第二个元素的位置在哪; 在第二个元素时, 再找到第三个元素的位置. 这样, 所有的元素都可以遍历而找到.
因此, 为了表示每个数据元素 n 和后继元素 n+1 之间的逻辑关系, 对数据元素 n 来说, 除了存储本身的信息之外, 还需要存储一个指示其后继的信息. 我们把存储元素的域称之为 数据域, 把存储直接后继位置的域称之为 指针域. 指针域中存储的信息称做 指针或链. 这两部分信息组成数据元素 n 的存储映像, 称为 结点.
而由 n 个结点链结成一个链表, 称之为 链式存储结构.
2 单链表
最简单最常用的是 单链表, 此链表的每个结点只包含一个指针域.
如上图, 就是一个简单的单链表示意图. 其中有两个结点是比较特殊的. 他们分别是第一个结点和最后一个节点. 我们习惯性地把第一个结点叫做头结点, 把最后一个结点叫做尾结点. 头结点是用来记录链表的基地址. 有了它, 我们就可以遍历得到整条链表. 而尾结点特殊地方它的指针不是指向下一个地方, 而是指向一个空地址 NULL, 表示这是链表上最后一个结点.
我们可以判断当前结点的 next 是否为空, 就知道循环是否结束.
就像一家三口并排的手牵手去逛街, 爸爸牵着妈妈, 妈妈牵着孩子. 此时的爸爸就可以当做头结点, 而孩子就是尾结点.
与数组一样, 链表也支持数据的增删改查. 对比插入和删除操作, 为了保持内存数据的连续性, 数据需要进行大量的数据搬移工作, 所以时间复杂度为 O(n). 而在链表中插入和删除数据, 并不需要担心此事, 因为链表的存储空间本身就不是连续的. 所以, 在链表中插入和删除一个数据是非常快速的.
对比查找操作, 链表就没有数组那么高效了. 因为链表中的数据并非连续存储的, 所以无法像数组那样, 根据下标等方法查找, 链表需要根据指针依次遍历, 直到找到对应的结点.
3 循环链表
屏幕前的你都还很年轻, 不会觉得日月如梭. 可上了点年纪的人, 比如我 --- 的父辈们, 就会常常感叹, 要是能回到从前该多好, 向天再借 500 年可好. 也有人说, 所谓的成功男人就是 3 岁时不尿裤子, 5 岁时能自己吃饭....80 岁能自己吃饭, 90 岁能不尿裤子. 人生是不是在循环呢.
对于单链表, 由于每个结点只存储了向后的指针, 到了尾结点就停止了向后链的操作. 这样, 当中的某一结点就无法找到它的前驱结点了, 就如上图一样, 不能回到从前了.
比如说, 我们的市场销售同学家在北京, 需要经常到上海出差. 行程就是去两地之间的各个城市. 从北京出发, 乘坐高铁经过多个城市后, 再乘坐灰机返回北京.
北京 --> 济南 --> 蚌埠 --> 南京 --> 苏州 --> 上海
有一次, 他先到南京开会, 接下来还要把以上的城市再走一遍. 此时有人对他说, 不行, 你得从上海开始, 因为北京是第一站. 这时他会对这人说什么? 神经病. 他从南京开始, 到苏州, 上海, 然后再回北京然后去济南的几个城市就可以了. 显然这表示是你从当中某一个结点开始遍历整个链表, 这是原来的单链表结构不能解决的问题.
事实上, 把北京和上海连起来, 行成一个环就解决了前面所面临的问题. 这就是 循环链表.
将单链表中尾结点的指针由空指针指向头节点, 就使整个单链表形成一个环, 这种头尾相接的单链表就简称为循环链表.
其实循环链表和单链表的主要差异就在于循环的判断条件上, 原来是判断当前结点的 next 是否为空, 现在则是判断当前结点的 next 是否等于头结点.
就像一家三口围成一个圈做游戏, 爸爸牵着妈妈, 妈妈牵着孩子, 孩子又牵着爸爸.
4 双向链表
今天我们销售又得出差了, 平时都是从北京一路停留到上海的. 可是这一次, 他得先到上海开会, 开完后, 然后又得需要例行公事, 走访各个城市, 此时他该怎么办? 这个时候, 那人又出主意了, 你可以先飞回北京, 然后再一路乘坐火车走遍这几个城市.
哎, 人生中总会避免不了这样给你出馊主意的人存在. 哪有这么麻烦, 他一路再乘坐高铁回去不就完事了嘛.
就如单链表, 总是从头到尾找结点, 难道就不可以正反遍历吗?
所以这个时候双向链表就登场了. 双向链表是在单链表的每个结点中, 再设置一个指向其前驱结点的指针域. 所以在双向链表中的结点都有两个指针域, 一个指向直接后继, 另一个指向直接前驱.
从上图中可以看出来, 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址. 所以, 如果存储同样多的数据, 双向链表要比单链表占用更多的内存空间. 虽然两个指针比较浪费存储空间, 但是可以支持双向遍历, 这样也带来了双向链表操作的灵活性.
5 双向循环链表
既然单链表可以有循环链表, 那么双向链表当然也可以是循环链表. 你可以停下来想想双向循环链表长什么样子.
6 链表和数组的性能对比
数组和链表的对比, 并不能局限于时间复杂度. 而且, 在实际开发中, 不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据. 针对不同的类型项目来权衡. 当然, 在大前端, 还是数组用的最多.
重点
各位大佬, 初碰水面, 不喜勿喷. 如有错误, 还请指出, 谢谢.
下一篇总结下如何写好链表代码.
我们下期见.
来源: https://juejin.im/post/5c8a8289f265da2dda69927d