一、链表数据结构
要存储多个元素，数组（或列表）可能是最常用的数据结构。然而这种数据结构有一个缺点，数字的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。
链表存储有序的元素集合，但不用于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的饮用（也称指针或链接）组成。下图展示了一个链表的结构
image.png
相对于传统的数组，链表的一个好处在于，添加或移动元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的一个细节是可以直接访问任何位置的元素，而想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。
举几个形象的例子来形容：
- 寻宝游戏：你有一条线索，这条线索是指向寻找下一条线索的地点的指针。你顺着这条链接去下一个地点，得到另一条指向再下一处的线索。得到列表中间的线索的唯一办法，就是从起点（第一条线索）顺着列表寻找
- 火车：一列火车是由一系列车厢组成，每节车厢相互连接，你很容易分离一节车皮，改变它的位置，添加或者移除它，车厢之间的连接就是指针
特点
- 链表是多个元素组成的列表
- 元素存储不连续，用next指针连接到一起
- JS中没有链表，但是可以用Object模拟链表
二、创建链表
下面我们实现一个链表类，并给他加点方法
class Node { //节点类
//构造函数
constructor(item) {
this.item = item;
this.next = null;
}
}
class LinkedList { // 链表类
//构造函数
constructor() {
this.head = null;
this.length = 0;
}
//新增节点
append(item) {
let node = new Node(item);
let current; //暂存当前位置
if(this.head === null) { // 如果头结点为空,当前节点作为头结点
this.head = node;
} else {
current = this.head;
while(current.next) { //遍历找到链表尾部
current = current.next;
}
current.next = node; //在链表尾部加入新节点
}
this.length++; //更新链表长度
}
//删除节点,并获得删除节点的值
remove(index) {
if(index > -1 && index < this.length) { //预防下标越界
var current = this.head;//暂存当前位置
var previous; //暂存当前位置的前一个
var position = 0;
if(index === 0) { //要删除的是第一个位置，就得改变头指针指向
this.head = current.next;
} else {
while(position++ < index) { //遍历直到current处于index位置
previous = current;
current = current.next; //此时current处于index处,previous在index-1处
}
previous.next = current.next; //改变链表结构,跳过index处
}
this.length--; //更新链表长度
return current.[图片上传中...(image.png-aecada-1661950439992-0)]
; //返回index处的值
} else {
return null; //下标越界返回空
}
}
//插入节点
insert(index, item) {
if(index > -1 && index <= this.length) {
let node = new Node(item);
let current = this.head;
let previous;
let position = 0;
if(index === 0) {
node.next = current;
this.head = node;
} else {
while(position++ < index) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true; //插入成功
} else {
return false; //插入失败
}
}
//获取索引
indexOf(item) {
let current = this.head;
let position = 0;
while(current) {
if(current.item === item) {
return position;
}
position++;
current = current.next;
}
return -1; //未找到索引
}
//将链表转换成字符串
toString() {
let current = this.head;
let string = '';
while(current) {
string += current.item + ((current.next ? ',': ''));
current = current.next;
}
return string;
}
//链表长度
size() {
return this.length;
}
//判断链表是否为空
isEmpty() {
return this.length === 0;
}
}
这样我们就实现了一个链表类，我们也为其添加了很多自定义方法
- 新增节点 append
- 删除节点 remove
- 插入节点 insert
- 获取索引 indexOf
- 链表转字符串 toString
- 获取链表长度 size
- 判断链表是否为空 isEmpty
未完待续......
