专业网站建设品牌，十四年专业建站经验，服务6000+客户--广州京杭网络

免费热线：400-683-0016      微信咨询  |  联系我们

• 网站首页
• 网站建设
• 短视频
• 网站推广
• 网站模板
• 客户案例
• 资讯动态
• 关于我们

js单链表查找原理_数据库

当前位置：网站建设 > 技术支持

js单链表查找原理？

链表的由来

一、链表的由来

我们接触最多的数据存储结构应该是数组了，在实际场景中它的出现频率极高，但是它并不能适于用所有情况。这也是的链表

原因如下：

在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。在数组中的添加和删除元素很麻烦，因为需要将数组中的其他元素向前或向后平移。JavaScript中数组的主要问题是，它们被实现成了对象，与其他语言（比如 C++ 和 Java） 的数组相比，效率较低。为了解决上述问题如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中，如果需要频繁的删除和添加操作，就主动考虑一下链表吧～

1.1 特点

优点

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。增加数据和删除数据很容易。链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。缺点？

访问时间是线性的(而且难以管道化)，更快的访问，如随机访问，是不可行的。与链表相比，数组具有更好的缓存位置。失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。下面出现的代码都是用Js实现的，如果不对的地方，欢迎大佬们指正，我们共勉。

二、单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。、

下面是一个单链表的例子：

当你得到了head节点，就得到了整个列表。

我们创建单一节点（Node）的操作应该是这样的：

2.1 添加节点

就像给绳子打结一样，添加节点，就是在两个绳结之间，再打一个新结。

如果我们想在给定的结点 prev 之后添加新值，我们应该：

创建要插入的Node——cur将cur节点的next链接到next节点（pre的下一个节点）将pre的next链接到cur节点

在开头添加结点

众所周知，我们使用头结点（head）来代表整个列表。

因此，在列表开头添加新节点时更新头结点 head 至关重要。

初始化一个新结点 cur；将新结点cur的next链接到我们的原始头结点 head.next节点将head节点的next链接到cur即可。

在末尾添加节点

创建新节点cur将链表的末尾节点的next链接到cur即可

2.2 删除节点

如果我们要删除指定的节点cur，该这么做：

找到cur的上一个节点prev，及其下一个节点prev.next（要删除的节点）将prev.next链接让 `prev.next.next，即跳过删除节点。

注意：我们必须从头节点遍历至指定节点，删除节点的平均时间复杂度是O(N)

删除末尾节点

找到next节点链接为null的节点，以及它的前节点prevprev.next 链接 null 即可

三、设计链表

以LeetCode的中的基础题为例，我们尝试用代换实现前文提过的思路。707.设计链表

题目

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。示例：

Js版代码实现

为了方便操作，我们主动创建了一个节点为头节点，实际存储过程中是完全不需要的。

四、链表的基本使用场景

对线性表的长度或者规模难以估计；频繁做插入删除操作；构建动态性比较强的线性表

链表的基本操作

1.创建节点

2.创建链表

3.查找目标节点

4.添加操作

5.查找存储目标节点的节点

6.删除操作

7.打印操作

测试数据