本文介绍如何在JavaScript中实现单链表和循环链表。详细解析链表节点结构、常用操作方法如append和insert，以及单链表与循环链表在尾节点指向上的核心区别，并提供完整的JS代码实现示例，帮助开发者掌握基础数据结构。
前言与学习建议
数据结构系列前言：
数据结构是程序员必须掌握的核心基础知识。近期我重新学习了数据结构，以弥补过往学习中的不足。当时上课仅跟随听讲，并未亲手实现任何数据结构，更未尝试利用其解决实际问题。如今开始填补这些空白。在此提醒阅读博客的读者，若你仍是在校学生，切勿轻视任何基础课程的学习。此时忽视基础所留下的隐患，要么需要加倍努力才能弥补，要么会直接限制个人能力的提升。务必避免给自己埋下隐患。
链表基本概念
接下来进入正题，简要介绍链表相关的数据结构知识：
链表是一种在物理存储单元上非线性、非连续的数据结构（尽管其逻辑结构是线性的）。每个节点包含两个域：数据域和指针域。数据域用于存储实际数据，指针域则存储指向链表中下一个元素或上一个元素的指针信息。正是由于指针的存在，使得链表在物理存储上呈现非连续性。
链表具有明显的优缺点。与线性表相比，链表在添加和删除节点时效率更高，因为只需修改指针信息即可完成操作，而无需像线性表（数组）那样移动元素。此外，链表的长度理论上不受限制（受限于存储器容量），且支持动态长度变化，相比线性表优势显著。然而，由于线性表无法随机访问节点，链表只能通过指针遍历来查询和访问数据元素，因此其访问效率相对较低。
JavaScript实现代码
以下是JavaScript部分的实现：
其中封装了常用方法及其描述：
| 方法 | 描述 |
|---|---|
| append(element) | 向链表尾部添加结点element |
| insert(position,element) | 向位置position处插入结点element |
| removeAt(position) | 按照索引值position删除结点 |
| remove(element) | 搜索并删除给定结点element |
| remove() | 删除链表中最后一个结点 |
| indexOf(element) | 查找并返回给定结点element的索引值 |
| isEmpty() | 判断链表是否为空 |
| size() | 获取链表长度 |
| toString() | 转换为字符串输出 |
| getHead() | 获取头结点 |
| getTail() | 获取尾结点 |
关于各常用方法的具体算法描述在此省略，相信读者能够轻松阅读并理解，因为这些属于非常基础的知识。
单链表与循环链表详解
单链表：
function LinkedList(){
/*节点定义*/
var Node = function(element){
this.element = element; //存放节点内容
this.next = null; //指针
}
var length = 0, //存放链表长度
head = null; //头指针
this.append = function(element){
var node = new Node(element),
current; //操作所用指针
if (!head){
head = node;
}else {
current = head;
while(current.next){
current = current.next;
}
current.next = node;
}
length++;
return true;
};
this.insert = function(position, element){
if (position >= 0 && position <= length) {
var node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0){
node.next = current;
head = node;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
previous,
index = 0;
if (position === 0) {
head = current.next;
}else{
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
};
length--;
return current.element;
}else{
return null;
}
};
this.remove = function(element){
var current = head,
previous;
if(element === current.element){
head = current.next;
length--;
return true;
}
previous = current;
current = current.next;
while(current){
if(element === current.element){
previous.next = current.next;
length--;
return true;
}else{
previous = current;
current = current.next;
}
}
return false;
};
this.remove = function(){
if(length < 1){
return false;
}
var current = head,
previous;
if(length == 1){
head = null;
length--;
return current.element;
}
while(current.next !== null){
previous = current;
current = current.next;
}
previous.next = null;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current){
if(element === current.element){
return index;
}
index++;
current = current.next;
}
return false;
};
this.isEmpty = function(){
return length === 0;
};
this.size = function(){
return length;
};
this.toString = function(){
var current = head,
string = '';
while(current){
string += current.element;
current = current.next;
}
return string;
};
this.getHead = function(){
return head;
}
}
循环链表：在单链表的基础上，将尾节点的指针指向头结点，从而构成一个循环链表。从循环链表中的任意节点开始，都可以遍历整个链表。
function CircularLinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0,
head = null;
this.append = function(element){
var node = new Node(element),
current;
if (!head) {
head = node;
node.next = head;
}else{
current = head;
while(current.next !== head){
current = current.next;
}
current.next = node;
node.next = head;
};
length++;
return true;
};
this.insert = function(position, element){
if(position > -1 && position < length){
var node = new Node(element),
index = 0,
current = head,
previous;
if (position === 0) {
node.next = head;
head = node;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
};
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
previous,
index = 0;
if (position === 0) {
head = current.next;
}else{
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
};
length--;
return current.element;
}else{
return null;
}
};
this.remove = function (element){
var current = head,
previous,
indexCheck = 0;
while(current && indexCheck < length){
if(current.element === element){
if(indexCheck == 0){
head = current.next;
length--;
return true;
}else{
previous.next = current.next;
length--;
return true;
}
}else{
previous = current;
current = current.next;
indexCheck++;
}
}
return false;
};
this.remove = function(){
if(length === 0){
return false;
}
var current = head,
previous,
indexCheck = 0;
if(length === 1){
head = null;
length--;
return current.element;
}
while(indexCheck++ < length){
previous = current;
current = current.next;
}
previous.next = head;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index < length){
if(current.element === element){
return index;
}else{
index++;
current = current.next;
}
}
return false;
};
this.isEmpty = function(){
return length === 0;
};
this.size = function(){
return length;
};
this.toString = function(){
var current = head,
string = '',
indexCheck = 0;
while(current && indexCheck < length){
string += current.element;
current = current.next;
indexCheck++;
}
return string;
};
}
使用方法：
在类外部扩充方法：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。