js数据结构之链表 包能看懂的。
js数据结构之链表，带你用js手搓一个链表出来。
哈喽哈喽，大家好，我是你们的金樽清酒。数据结构呢一直是算法当中很重要的环节，很重要的一个play哦，而链表就是数据结构其中之一。而且在面试的时候还是高频考点，而我也觉得链表很抽象而没有去认真的学习，今天就让我们一起学习一下简单的链表结构吧。
什么是链表
链表（Linked List）是一种常见的线性数据结构，用于存储一系列元素。它由节点（Node）组成，每个节点包含两部分：数据（元素本身的值）和指向下一个节点的引用（指针或链接）。链表中的节点在内存中可以不必顺序地存储，而是通过每个节点中的指针将它们连接起来，形成一种逻辑上的顺序。
主要特点：
- 动态内存分配： 链表的节点可以动态地在运行时创建，因此链表的大小可以根据需要动态增加或缩小，相比之下，数组在创建时大小通常是固定的。
- 灵活的插入和删除操作： 链表在任意位置插入或删除节点相对比较高效，只需修改节点的指针即可，而不需要像数组那样移动大量元素。
- 顺序访问： 单向链表只能从头节点开始顺序访问每个节点，而双向链表可以双向访问，从头到尾或从尾到头访问。
- 内存空间的非连续性： 链表的节点在内存中存储位置可以是不连续的，每个节点通过指针指向下一个节点，这使得链表可以克服数组因内存连续性带来的限制。
链表的分类
-
单向链表 (Singly Linked List) :
- 最常见的链表类型之一。
- 每个节点包含一个指向下一个节点的引用（指针）。
- 只能从头节点开始顺序访问链表，无法反向访问。
-
双向链表 (Doubly Linked List) :
- 每个节点包含两个指针，分别指向前一个节点和后一个节点。
- 允许双向遍历，可以从头节点或尾节点开始遍历链表。
- 插入和删除节点时比单向链表更灵活，因为可以直接访问前驱节点。
-
循环链表 (Circular Linked List) :
- 最后一个节点指向第一个节点，形成一个环形结构。
- 可以用于实现循环队列等数据结构。
- 遍历时需要判断是否回到起始节点来终止循环。
-
双向循环链表 (Doubly Circular Linked List) :
- 同时具备双向链表和循环链表的特性。
- 最后一个节点指向第一个节点，同时每个节点有一个指向前一个节点的引用。
- 结合了双向链表和循环链表的优点，适合需要双向遍历和循环访问的场景。
-
静态链表 (Static Linked List) :
- 使用数组实现的链表结构。
- 需要预先分配固定大小的内存空间，不具有动态扩展能力。
- 节省了指针空间，但插入和删除操作可能较复杂。
-
跳表 (Skip List) :
- 基于多层链表实现的数据结构，用于在有序链表上进行快速查找。
- 每个节点包含多个指针，允许快速跳跃到下一个或下几个节点，从而实现快速查找。
用js实现一个单向链表
要实现一个单向链表，我们要分析一下，链表的组成，链表是从头节点开始，然后，每个节点有一个next的指针指向下一个节点。每个节点呢又是同样的结构，里面包含元素和next指针。然后链表自然要有长度。这样分析一下，我们先完成每一个节点的构造。
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
我们写了一个node构造函数，里面有element元素和next，next默认为null，这就是一个节点了。我们可以想象一下，链表其实就是由n个这样的节点组成的。比如给一个头节点，它的元素为1，它的下一个的元素为2，总链表长度为2。那么可以表示成一个这样子的数据结构。
head{
element:1
next:{
element:2
next:null
}
}
我们可以看到，其实我们就是在head这个对象里面重复增加节点node，这个head也就是头节点，可以看出它蕴含的内容是链表中最多的。
那实现了node节点，和节点之间的关系之后，我们就要实现一个链表，根据上面的分析，链表还需要什么呢？还需要一个head头节点和size链表的长度。
class LinkedList{
constructor() {
this.size = 0
this.head = null
}
}
我们又创建一个构造函数，这个就是我们的链表。然后要在这个构造函数上添加方法，将我们的节点Node添加上去。先打造一个append方法，添加元素。这里又写了一个 getNode()方法，获取当前的节点。
class LinkedList{
constructor() {
this.size = 0
this.head = null
}
append(element) {//在链表上添加元素
if (this.head == null) {
this.head = new Node(element)
} else {
let current = this.getNode(this.size - 1)
current.next = new Node(element)
}
this.size++
}
getNode(index) {
if (index < 0 || index >= this.size) {
throw new Error('越界')
} else {
let current = this.head
for (let i = 0; i < index; i++) {
current = current.next
}
return current
}
}
}
先分析一下这个getNode()函数吧，首先传递的这个参数，链表的下标是从零开始的，所以index要做一个限制。然后我们定义一个变量分配为头节点，我们头节点我们也看了那个结构，头节点包含了所有的节点。然后遍历next到我们当前的节点。看一下append方法，如果头节点为空那么就把Node节点分配给头节点，如果不为空，遍历到最后一个节点，最后一个节点的next的值为空，我们可以直接分配，最后记得将长度加一就完美了。
根据这个思路我们还有很多的方法
class LinkedList{
constructor() {
this.size = 0
this.head = null
}
append(element) {//在链表上添加元素
if (this.head == null) {
this.head = new Node(element)
} else {
let current = this.getNode(this.size - 1)
current.next = new Node(element)
}
this.size++
}
getNode(index) {
if (index < 0 || index >= this.size) {
throw new Error('越界')
} else {
let current = this.head
for (let i = 0; i < index; i++) {
current = current.next
}
return current
}
}
}
appendAt(position, element) {//在某个位置插入元素
if (position < 0 || position > this.size) {//数据边界的问题
throw new Error('position out range')
} else if (position == 0) {//在头的位置添加元素
let node = new Node(element)
node.next = this.head
this.head = node
} else {//在中间插入元素
let node = new Node(element)
let prev = this.getNode(position - 1)
node.next = prev.next
prev.next = node
}
this.size++
}
appendAt方法，在某个位置插入节点。，一样先考虑插入的边界，边界不可能小于零和大于size。然后考虑在最前面插入元素的情况。一样先创建节点node，然后node的next就是存储后面的链表也就是this.head，然后把链表的this.head分配为node。这个感觉有点抽象的友友们可以在看一下我们的node节点和linkedlist链表。 然后考虑插在链表中间，先创建节点，然后获取该位置的上一个节点，先把我们创建的节点的node值分配为上一个节点的next，然后再把上一个节点的next分配为node。这个过程就是抽象成，把上一个节点指向node，node再指向下一个节点，这样就完成了插入。不要忘记size+1。
class LinkedList{
constructor() {
this.size = 0
this.head = null
}
append(element) {//在链表上添加元素
if (this.head == null) {
this.head = new Node(element)
} else {
let current = this.getNode(this.size - 1)
current.next = new Node(element)
}
this.size++
}
getNode(index) {
if (index < 0 || index >= this.size) {
throw new Error('越界')
} else {
let current = this.head
for (let i = 0; i < index; i++) {
current = current.next
}
return current
}
}
}
appendAt(position, element) {//在某个位置插入元素
if (position < 0 || position > this.size) {//数据边界的问题
throw new Error('position out range')
} else if (position == 0) {//在头的位置添加元素
let node = new Node(element)
node.next = this.head
this.head = node
} else {//在中间插入元素
let node = new Node(element)
let prev = this.getNode(position - 1)
node.next = prev.next
prev.next = node
}
this.size++
}
removeAt(position) {//删除指定项的元素
if (position < 0 || position > this.size - 1) {
throw new Error('position out range')
}
if (position === 0) {//删除头节点
let current = this.head.next
this.head = current
} else {
let prev = this.getNode(position - 1)
let current = this.getNode(position)
prev.next = current.next
}
this.size--
}
remove方法，移除链表中的元素。首先也是考虑边界的问题。然后分情况，删除第一个节点，创建current变量，把this.head.next赋值给它，也就是删除了head的元素。再把this.head分配给current，返回current。然后在中间删除，先获取上一个节点，再获取删除的节点。上一个节点的next指向当前节点的下一个节点。 有这些思路之后，我们还可以创建其他的方法，友友们可以尝试一下。
效果
可以看到我们的链表和方法就完成了。
- 注意，最后的输出结果如果只用console.log输出的话会隐藏。所以我们用console.dir()
好了，友友们，链表一直是困扰我的问题，其实是我不敢尝试，所以，勇敢的人先享受世界，我们要敢于尝试哦。
转载自:https://juejin.cn/post/7384633860519526452