本文详细解析了 JavaScript 中单链表的实现原理与代码封装。对比数组与链表的优缺点，介绍了 Node 节点与 LinkedList 类的构建方法，并逐步实现了 append、insert、get、indexOf、update、removeAt、remove、isEmpty 和 size 等核心操作，帮助开发者深入理解链表数据结构。
前言：
在存储多个元素时，数组是最常用的数据结构，但它也存在一些局限性：
- 数组在创建时通常需要申请一段连续的内存空间，且大小固定。当现有容量不足时，必须进行扩容（通常是申请更大的数组并将原元素复制过去）。
- 在数组的开头或中间插入数据成本较高，因为需要移动大量元素。
因此，存储多个元素的另一种选择是链表。与数组不同，链表中的元素在内存中不需要连续。每个元素包含一个存储数据的节点以及指向下一个元素的引用。相比数组，链表具有以下优势：
- 内存空间无需连续，可以充分利用计算机内存，实现灵活的动态内存管理。
- 链表在创建时无需确定大小，且容量可以无限扩展。
- 链表在插入和删除数据时，时间复杂度可达 O（1），效率远高于数组。
然而，链表也存在一些缺点：
- 访问链表任意位置的元素时，必须从头开始遍历，无法通过下标直接访问。
一、什么是单链表
那么，单链表究竟是什么？
它类似于火车，车头连接一个节点，节点上承载数据，并指向下一个节点，依此类推，结构如下所示：
我们的链表结构定义如下：
了解了链表的直观概念后，接下来我们将通过代码进行封装。
二、单链表的封装
首先，我们封装一个 NodeList 类来表示链表结构。在该类内部，再封装一个内部类 Node，用于封装每个节点的信息（数据和指向下一个节点的引用）。在 NodeList 类中保存两个属性：链表长度和头结点。
具体实现如下：
function LinkedList(){
this.length = 0;
this.head = null;
//内部的类
function Node(data){
this.data = data;
this.next = null;
}
}
三、单链表的常用操作
接下来，我们在类中添加单链表的常用操作方法，主要包括：
append（element): 向列表尾部添加一个项insert(position,element): 向列表的特定位置插入一个项get(position): 获取对应位置的元素indexOf(element): 返回元素在列表中的索引，如果列表中不存在该元素则返回 -1update(position，ele): 修改某个位置的元素removeAt(position): 从列表的指定位置移除一项remove(element): 从列表中移除一项isEmpty(): 如果链表中不包含任何元素，返回 true；如果链表长度大于 0，返回 falsesize(): 返回链表包含的元素个数，与数组的length属性类似toString(): 由于列表项使用了 Node 类，需要重写继承自JavaScript对象默认的 toString 方法，使其输出元素的值
接下来，我们将逐一实现这些方法。
1、append(element) 方法-----向列表尾部添加一个项
向链表尾部添加数据可能面临两种情况：
- 链表本身为空，新添加的数据成为唯一的节点。
- 链表不为空，需要向现有节点后追加新节点。
因此，我们需要进行判断：如果链表为空，直接将头结点的指针指向新节点；如果链表不为空，则新建一个临时节点并初始化为头结点。遍历该临时节点，如果其指向的节点指针域为空，说明已到达尾节点，将新节点添加到末尾（即让尾节点的指针指向新节点）。如果指针域不为空，则让临时节点指向下一个节点，循环直到指针域为空（即到达尾节点）。每添加一个节点，链表长度加 1。
LinkedList.prototype.append = function(data){
var newNode = new Node(data);
// 判断链表是否为空
// 1.为空
if(this.length === 0){
this.head = newNode;
}else{
//不为空
var current = this.head;
if(current.next){
current = current.next;
}
current.next = newNode;
}
this.length += 1;
}
2、toString 方法-----输出元素的值
该方法相对简单，主要获取每个元素。由于访问链表任何元素都必须从第一个节点开始，我们可以从头结点开始循环遍历每个节点，并取出其中的 element，拼接成字符串后返回。
LinkedList.prototype.toString = function(){
var current = this.head;
var ListStr = '';
while(current){
ListStr += current.data + ' ';
current = current.next;
}
return ListStr;
}
验证：创建几个新节点并打印。
var list = new LinkedList();
list.append('a');
list.append('b');
list.append('c');
list.append('d');
list.append('e');
alert(list);
打印结果为：
3、insert 方法-----向列表的特定位置插入一个项
实现在任意位置插入数据的方法时，首先判断插入位置是否越界。若不越界，分两种情况处理：若插入到第一个位置，表示新添加的节点成为头结点，需将原头结点作为新节点的 next，再让 head 指向新节点。若插入到其他位置，则通过循环找到目标节点位置，并在循环过程中保存前一个节点和后一个节点。找到正确位置后，将新节点的 Next 指向下一个节点，将前一个节点的 next 指向新节点。
代码如下：
LinkedList.prototype.insert = function(position,data){
if(position<0 || position >this.length){
return false;
}
var newNode = new Node(data);
var index = 0;
if(position == 0){
newNode.next = this.head;
this.head = newNode;
}else{
while(index++ < position){
var current = this.head;
var previous = null;
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
this.length += 1;
return true;
}
验证：在第 1 个位置插入 xl，在第 2 个位置插入 wh。
list.insert(1,'xl')
list.insert(2,'wh')
alert(list)
4、get 方法-----获取对应位置的元素
该方法相对简单，先对 positon 进行越界判断，然后通过临时节点遍历链表直到目标位置，获取该位置的元素。
LinkedList.prototype.get = function(position,data){
var current = this.head;
var index = 0;
if(position < 0 || position >= this.length){
return null;
}else{
while(index<position){
current = current.next;
index++;
}
return current.data;
}
}
验证：获取第三个位置的元素：
alert( list.get(3));
5、indexOf() 方法-----返回元素在列表中的索引
首先判断查找的元素是否存在，若不存在则返回 -1。若存在，分两种情况：若元素在第一个位置，直接返回索引 0；若元素在其他位置，则通过循环找到节点位置，遍历过程中索引随遍历次数自增，找到正确元素后，打印索引即为目标位置。
LinkedList.prototype.indexOf = function(data){
var index = 0;
var current = this.head;
while(current){
if(current.data == data){
return index;
}
else{
current = current.next;
index++;
}
}
return -1;
}
}
验证：获取 c 的索引：
alert(list.indexOf('c'));
6、update 方法-----修改某个位置的元素
该方法与 get 方法类似，向后遍历，当 index 的值等于 position 时，表示找到目标位置，将 data 改为目标值：
LinkedList.prototype.update = function(position,ele){
if(position<0 || position>=this.length){
return false;
}else{
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
current.data = ele;
return true;
}
}
验证：修改第 0 个位置的元素为：bear
list.update(0,'bear')
alert(list)
7、removeAt 方法-----从列表的指定位置移除一项
首先判断删除项的位置是否越界。若不越界，给定两个临时节点 previous 和 current，previous 用于保存前一个 current 的值。从头节点开始遍历，直到索引等于目标位置，让临时节点 current 遍历到目标位置，让前一个节点的 next 指向下一个 next。
LinkedList.prototype.removeAt = function(position,data){
var current = this.head;
var previous = null;
var index = 0;
if(position<0 || position>=this.length){
return false;
}else{
while(index++ <position){
previous = currrent;
current = current.next;
}
previous.next = current.next;
this.length -= 1;
return true;
}
}
}
验证：移除第三个位置的元素：
list.removeAt(3)
alert(list)
8、remove 方法-----从列表中移除一项
先判断所要删除的元素是否在链表中，若不在则返回 false。否则，构建一个临时节点用于遍历链表，若临时节点的 data 值与要删除的元素相等，则停止遍历，让前一个节点的 next 指向下一个 next。这里可以构建一个临时节点用于存储前一个 current 的值。
LinkedList.prototype.remove = function(ele){
var current = this.head;
var previous = null;
var index = 0;
while(current.data !== ele){
previous = current;
current = current.next;
index++;
}
previous.next = current.next;
}
验证：删除值为 xl 的元素：
list.remove('xl')
alert(list)
9、isEmpty 方法-----判断链表是否为空
根据 length 判断，如果链表中不包含任何元素，返回 true；如果链表长度大于 0，返回 false。
LinkedList.prototype.isEmpty = function(){
return this.length == 0;
}
验证：
alert(list.isEmpty())
9、size 方法-----返回链表包含的元素个数
直接返回元素的 length 即可得到其个数。
LinkedList.prototype.size = function(){
return this.length;
}
验证：
alert(list.size())
到此这篇关于 JavaScript 实现单链表过程解析的文章就介绍到这了，更多相关 JavaScript 实现单链表内容请搜索本站以前的文章或继续浏览下面的相关文章，希望大家以后多多支持本站！