社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
举个栗子: 一列火车是由一系列车厢组成的。每节车厢或车皮都相互连接,你很容易分离一节车箱,改变它的位置、添加或移除它。每节车厢相当于链表的元素,车厢间的对接扣就是元素的引用。
const defaultCompare = function (a, b) { // 一个比较函数
if (a === b) return 0;
return a < b ? -1 : 1;
}
class Node { // 一个助手类,用来表示我们想要添加到链表中的元素
constructor(element, next) {
this.element = element; // 元素的值
this.next = next; // 指向链表中下一个元素的指针
}
}
class LinkedList { // 链表类
constructor(equalsFn = defaultEquals) {
this.equalsFn = equalsFn; // 比较链表中的元素是否相等,默认a===b
this.count = 0; // 链表中的元素数量
this.head = undefined; // 表头
}
}
push(element) {
const node = new Node(element); // 创建node项
let current; // 声明一个指向链表中的临时项
if (this.head == undefined) { // 如果链表头为空,即链表为空
this.head = node; // 直接让表头等于当前元素就好了,下一项(next)未传,因此为undefined
} else {
current = this.head; // 先让current等于第一个元素
while (current.next != null) { // 只要当前元素的下一项元素不是假的,便继续循环
current = current.next;
}
current.next = node; // 找到最后一个元素后,让它的下一个元素等于传进来的元素
}
this.count++;// 最后把总长度自增就好了
}
removeAt(index) {
if (index >= 0 && index < this.count) { // 检查越界值
let current = this.head;
if (index === 0) { // 如果是表头
this.head = current.next; // 就让表头等于下一个引用
} else {
let previous;
for (let i = 0; i < index; i++) { // 嗯,开始迭代把~~~
previous = current;
current = current.next;
}
previous.next = current.next;
// 上一个的下一个等于现在的下一个,,,(现在内心os:我是谁,我在哪???)当前节点就会被丢弃在计算机内存中,等着被垃圾回收器移除
}
this.count--;// 长度自减
return current.element; // 返回移除的元素
}
return undefined;
}
getElementAt(index) {
if (index >= 0 && index <= this.count) return undefined; // 检查越界值
let node = this.head; // 默认等于表头
for (let i = 0; i < index && node != null; i++) { // 嗯,开始迭代把~~~
node = node.next;
}
return node;
}
if(index===0){
// 第一个位置的逻辑
} else {
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.count--;
insert(element, index) {
if (index >= 0 && index <= this.count) { // 边界处理
const node = new Node(element); // 实例化当前元素
if (index === 0) { // 如果插在表头
const current = this.head;// 声明一个变量,等于原来的表头
node.next = current;// 传入元素的下一个引用等于current
this.head = node; // 当前表头等于传入的元素
} else {
const previous = this.getElementAt(index - 1);// 找到传入索引的上一个值
previous.next = node;// 上一个的引用等于传入的值
node.next = previous.next;// 传入值的下一个引用等于上一个的下一个引用
}
this.count++;// 总长度自增
return true; // 最后返回true
}
return false; // 如果位置未找到返回false
}
indexOf(element) {
let current = this.head; // 等于表头
for (let i = 0; i < this.size() && current != null; i++) { // 循环迭代所有元素
if (this.equalsFn(element, current.element)) { // 找到和当前元素相等的第一个元素
return i;// 返回索引
}
current = current.next;// 如果不相等,就继续迭代下一个
}
return -1; // 如果都没找到,就返回-1
}
remove(element) {
const index = this.indexOf(element); // 先找到这个元素的第一个索引
return this.removeAt(index); // 利用删除指定位置元素的方法,搞掉它
}
isEmpty() {
return this.size() === 0;
}
size() {
return this.count;
}
getHead() {
return this.head;
}
toString() {
if (this.head == null) { // 如果列表为空,就返回空字符串
return '';
}
let objString = `${this.head.element}`; // 创建一个变量,先让他等于表头的元素
let current = this.head.next; // 等于表头的下一个引用
for (let i = 1; i < this.size() && current != null; i++) { // 循环迭代所有元素
objString = `${objString},${current.element}`; // 让这个字符串等于原来的字符串加上当前元素
current = current.next; // 当前元素等于当前的下一个引用
}
return objString; // 最后把这个字符串返回
}
最后
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!