文章目录
- 链表是什么？
- 链表的好处
- 详细的看一下列表
- 单向链表
- 实操链表
- 向链表尾部追加元素
- 从链表中移除元素
- 根据元素的值移除元素
- 在任意位置插入元素
- 查找链表是否有改元素
- 检查链表是否为空
- 检查链表的长度
- 查看链表头元素
- 把LinkedList对象转换成一个字符串
- 打印链表元素
- 双向链表
- 循环链表
- 单向循环链表
- 双向循环链表
- 常用的操作链表函数
- 总结
链表是什么？
JavaScript链表是一种数据结构，用于存储和组织一系列的元素。它由一系列节点（Node）组成，每个节点包含了两部分：数据域（存储数据）和指针域（指向下一个节点）。通过这种方式，链表中的节点可以按顺序链接在一起，形成一个链式结构。
与数组不同，链表的节点在内存中可以不连续存储，每个节点都可以独立分配内存，并通过指针连接到下一个节点，从而实现灵活的插入、删除操作。下图展示了一个链表的结构：
看图其实还是有点，一头雾水。用地铁举例吧，一列地铁是由一系列车厢组成的。每节车厢都相互连接。你很容易分离一节车厢，改变它的位置，添加或移除它。每节车皮都是列表的元素，车皮间的连接就是指针。
链表的好处
添加或移除元素的时候不需要移动其他元素，这是链表最大的好处。
存储多个元素，数组或列表是最常用的数据结构。每种语言都实现了数组，这种数据结构非常方便，提供了一个便利的[]语法来访问它的元素。然而，在大多数语言中这种数据结构有一个缺点：数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
链表可以灵活地插入、删除节点，不需要像数组一样进行扩容或拷贝操作。然而，链表的缺点是访问链表中的特定元素的时间复杂度较高，需要从头开始遍历链表直到找到目标节点。
详细的看一下列表
在JavaScript中，可以使用对象来实现链表。每个节点被表示为一个包含数据和指针属性的对象，通过这些对象之间的引用来构建链表结构。
常见的链表类型有单向链表（单链表），双向链表和循环链表。
以下逐一举例：
单向链表
每个节点只包含一个指向下一个节点的指针，最后一个节点的指针为空（null）。
实操链表
下面用实操一下链表，LinkedList类的骨架：
function LinkedList() {
let Node = function(element){
//Node类表示要加入列表的项。它包含一个element属性，即要添加到列表的值，以及一个next属性，即指向列表中下一个节点项的指针。
this.element = element;
this.next = null;
};
let length = 0; //存储列表项的数量
let head = null; //第一个节点的引用
this.append = function(element){}; //向链表尾部追加元素
this.insert = function(position, element){};//在任意位置插入元素
this.removeAt = function(position){}; //从链表中移除元素
this.remove = function(element){}; //根据元素的值移除元素
this.indexOf = function(element){}; //查找链表是否有改元素
this.isEmpty = function() {}; //检查链表是否为空
this.size = function() {}; //检查链表的长度
this.getHead = function(){}; //查看链表头元素
this.toString = function(){}; //把LinkedList对象转换成一个字符串
this.print = function(){}; //打印链表元素
}向链表尾部追加元素
向对象尾部添加一个元素时，可能有两种场景：列表为空，添加的是第一个元素，或者列表不为空，向其追加元素。
首先需要做的是把element作为值传入，创建Node项。
先来实现第一个场景：向为空的列表添加一个元素。当我们创建一个LinkedList对象时，
head会指向null：
this.append = function(element){
let node = new Node(element), //{1}
current; // 指向列表中current项的变量
if (head === null){ //列表中第一个节点 //如果head元素为null，要向列表添加第一个元素。
head = node;
} else {
current = head; // 要向列表的尾部添加一个元素
//循环列表，直到找到最后一项
while(current.next){
current = current.next;
}
//找到最后一项，将其next赋为node，建立链接
current.next = node; //当前（也就是最后一个）元素的next指针指向想要添加到列表的节点
}
length++; //更新列表的长度 //{6}
};从链表中移除元素
现在，让我们看看如何从LinkedList对象中移除元素。移除元素也有两种场景：第一种是移
除第一个元素，第二种是移除第一个以外的任一元素。我们要实现两种remove方法：第一种是从
特定位置移除一个元素，第二种是根据元素的值移除元素（稍后我们会展示第二种remove方法）。
this.removeAt = function(position){
//检查越界值
if (position > -1 && position 根据元素的值移除元素
需要先实现indexOf。indexOf在下面有讲述。
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};在任意位置插入元素
接下来，我们要实现insert方法。使用这个方法可以在任意位置插入一个元素。我们来看
一看它的实现：
this.insert = function(position, element){
//检查越界值
if (position >= 0 && position previous将是对列表最后一项的引用，而current将是null。在这种情况下，node.next将指向current，而previous.next将指向node，这样列表中就有了一个新的项。
现在来看看如何向列表中间添加一个新元素：
在这种情况下，试图将新的项（node）插入到previous和current元素之间。首先，需要把node.next的值指向current。然后把previous.next的值设为node。这样列表中就有了一个新的项。
使用变量引用需要控制的节点非常重要，这样就不会丢失节点之间的链接。可以只使用一个变量（previous），但那样会很难控制节点之间的链接。由于这个原因，最好是声明一个额外的变量来帮助处理这些引用。
查找链表是否有改元素
indexOf方法接收一个元素的值，如果在列表中找到它，就返回元素的位置，否则返回-1。
this.indexOf = function(element){
let current = head, //循环访问列表变量初始值是head
index = -1; //计算位置数
while (current) {
if (element === current.element) {
return index; //检查当前元素是否是要找的。如果是，就返回它的位置
}
index++; // 就继续计数
current = current.next; //检查列表中下一个节点
}
return -1;
};如果列表为空，或是到达列表的尾部（current = current.next将是null），循环就不会执行。如果没有找到值，就返回-1。
检查链表是否为空
如果列表中没有元素，isEmpty方法就返回true，否则返回false。
this.isEmpty = function() {
return length === 0;
};检查链表的长度
this.size = function() {
return length;
};查看链表头元素
需要在类的实现外部循环访问列表，就需要提供一种获取类的第一个元素的方法。
head变量是LinkedList类的私有变量,只有通过LinkedList实例才可以,在外部被访问和
更改。
this.getHead = function(){
return head;
};把LinkedList对象转换成一个字符串
toString方法会把LinkedList对象转换成一个字符串。下面是toString方法的实现：
this.toString = function(){
let current = head, //要循环访问列表中的所有元素，就需要有一个起点,把current变量当作索引
string = ''; //控制循环访问列表,初始化用于拼接元素值的变量
while (current) { //循环访问列表中的每个元素
string +=current.element +(current.next ? 'n' : '');//用current来检查元素是否存在
//如果列表为空，或是到达列表中最后一个元素的下一位（null），while循环中的代码就不会执行
//得到了元素的内容，将其拼接到字符串中
current = current.next; //继续迭代下一个元素
}
return string; // 返回列表内容的字符串
};打印链表元素
为了检查元素，实现一个辅助方法print。把元素都输出到控制台：
this.print = function(){
console.log(items.toString());
};双向链表
每个节点除了包含指向下一个节点的指针外，还包含一个指向前一个节点的指针。这样，可以在需要的时候方便地进行双向遍历。
循环链表
循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）不是引用null，而是指向第一个元素（head）。
单向循环链表
双向循环链表
常用的操作链表函数
- append(element)：向列表尾部添加一个新的项。
- insert(position, element)：向列表的特定位置插入一个新的项。
- remove(element)：从列表中移除一项。
- indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。
- removeAt(position)：从列表的特定位置移除一项。
- isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
- size()：返回链表包含的元素个数。与数组的length属性类似。
- toString()：由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
总结
链表是多个元素组成的列表，元素存储不连续，用next指针连接到一起，JS中没有链表，但是可以用Object模拟链表。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
文章目录 一、K8s安全框架 1.1 鉴权 1.1.1 HTTPS证书认证 1.1.2 HTTP Token认证 1.2 授权 1.3 准入控制 1.4 集群四大角色 二、RBAC给用户授权（TLS） 2.1 签发客户端证书 2.2 生成kubeconfig授…
