链表是常用的数据的一种,链表是节点的组合,节点包括指针和值,当列表为空值,头指针指向null,链表有单链表和双链表,下面我们针对单链表来展开,首先看下链表的“样子”
链表的代码实现
通过上面的图示,我们知道节点是由值和指针组成,我们通过代码来表示
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
接下来创建链表,链表是有一个head指针,size表示链表的节点个数
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
}
整个链表的结构已经创建好了,我们先了解节点是如何插入和删除的
节点插入图示
插入前
插入后
节点的删除
通过上面图示可以看出,链表节点的插入和删除操作就是操作指针的指向即可
接下来将会对链表新增以下方法,代码很简单,看注释即可
add(value)
往链表新增节点insert(index, value)
指定位置插入节点removeByIndex(index)
指定位置删除节点indexOf(value)
查找目标值的节点下标removeByValue(value)
指定值删除节点pop()
弹出最后一个节点isEmpty()
判断节点是否为空print()
打印链表的值
add(value)
/**
* 尾部新增节点
* @param {*} value
*/
add(value) {
const node = new Node(value);
let curr;
if (this.head === null) {
// 空链表
this.head = node;
} else {
// 非空,获取到最后一个节点,更改指向
curr = this.head;
while (curr.next) {
curr = curr.next;
}
curr.next = node;
}
this.size += 1;
}
insert(index, value)
/**
* 指定位置插入节点
* @param {*} index
* @param {*} value
* @returns
*/
insert(index, value) {
if (index < 0 || index > this.size - 1) {
return false;
} else {
const node = new Node(value);
let prev, curr = this.head;
// 头部插入
if (index === 0) {
node.next = curr;
} else {
// 非头部插入,查找到节点,改变指针指向
while (index > 0) {
prev = curr;
curr = curr.next;
index -= 1;
}
prev.next = node;
node.next = curr;
}
this.size += 1;
}
}
removeByIndex(index)
/**
* 通过下标移除节点
* @param {*} index
* @returns
*/
removeByIndex(index) {
if (index < 0 || index > this.size - 1) {
return;
}
let prev, curr = this.head;
if (index === 0) {
this.head = curr.next;
} else {
// 遍历获取指定下标的节点
while (index > 0) {
prev = curr;
curr = curr.next;
index -= 1;
}
prev.next = curr.next;
}
this.size -= 1;
return curr.value;
}
indexOf(value)
/**
* 查找目标值的节点下标
* @param {*} value
* @returns
*/
indexOf(value) {
// 未找到返回-1
let index = 0;
let curr = this.head;
while (curr) {
if (curr.value === value) {
// 找到了直接退出循环
return index;
break;
}
curr = curr.next;
index += 1;
}
return -1;
}
removeByValue(value)
/**
* 通过值移除节点
* @param {*} value
* @returns
*/
removeByValue(value) {
const index = this.indexOf(value);
return this.removeByIndex(index);
}
pop()
/**
* 删除尾部节点
*/
pop() {
let prev, curr = this.head;
// 空链表,直接返回null
if (this.size === 0) return null;
if (!curr.next) {
// 只有一个节点的情况
this.head = null;
} else {
while (curr.next) {
prev = curr;
curr = curr.next;
}
prev.next = null;
}
this.size -= 1;
}
isEmpty()
/**
* 判断是否为空
*/
isEmpty() {
return this.size === 0;
}
print()
/**
* 打印链表的值
*/
print() {
const arr = [];
let curr = this.head;
while (curr) {
arr.push(curr.value);
curr = curr.next;
}
console.log(arr.join('->'))
}
结果测试
最后我们测试下结果
const linkList = new LinkedList();
linkList.add(1);
linkList.add(5);
linkList.add(8);
linkList.print(); // 1->5->8
linkList.insert(2, 4);
linkList.print(); // 1->5->4->8
console.log(linkList.indexOf(5)); // 1
console.log('remove value is ' + linkList.removeByIndex(1)); // remove value is 5
linkList.print(); // 1->4->8
console.log('remove value is ' + linkList.removeByIndex(8)); // remove value is undefined
linkList.print(); // 1->4->8
linkList.removeByValue(4);
linkList.print(); // 1->8
linkList.pop();
linkList.print(); // 1
linkList.insert(0, 32);
linkList.print(); // 32->1
linkList.insert(1, 44);
linkList.print(); // 32->44->1
linkList.removeByValue(32);
linkList.print(); // 44->1
linkList.removeByValue(1);
linkList.print(); // 44
linkList.removeByValue(44);
linkList.print(); // 空
console.log(linkList.isEmpty()) // true
本文为原创,未经授权,禁止任何媒体或个人自媒体转载
商业侵权必究,如需授权请联系340443366@qq.com