阅读 1313

JavaScript数据结构之链表--介绍

前言

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 链表和数组的性能对比

数组和链表的对比,并不能局限于时间复杂度。而且,在实际开发中,不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。针对不同的类型项目来权衡。当然,在大前端,还是数组用的最多。

参考书籍

《大话数据结构》

重点

各位大佬,初碰水面,不喜勿喷。如有错误,还请指出,谢谢。

下一篇总结下如何写好链表代码。

我们下期见。

关注下面的标签,发现更多相似文章
评论