image.png
const ELEMENT_NOT_FOUND = -1;
class BaseList {
constructor() {
this.size = 0;
}
// 获取size
getSize() {
return this.size;
}
// list是否为空
isEmpty() {
return this.size === 0;
}
// 是否包含一个元素
contains(ele) {
return this.indexof(ele) !== ELEMENT_NOT_FOUND;
}
// 检查是否超出范围
rangeCheck(index, isadd) {
if (isadd) {
if (index > this.size || index < 0) throw new RangeError('index is out of range');
} else {
if (index >= this.size || index < 0) throw new RangeError('index is out of range');
}
}
}
class Node {
constructor(ele, next) {
this.element = ele;
this.next = next;
}
}
class LinkList extends BaseList {
constructor() {
super();
this.first = null;
}
// 清空
clear() {
this.first = null;
this.size = 0;
}
// 获取固定下标的值 复杂度： O(n)
get(index) {
return this.node(index).element;
}
// 设置固定下标的值 复杂度： O(n)
set(index, ele) {
let node = this.node(index);
let old = node.element;
node.element = ele;
return old;
}
// 向末尾增加 复杂度： O(n)
push(ele) {
this.add(ele, this.size);
}
// 添加元素 复杂度： O(n)
add(ele, index) {
this.rangeCheck();
// 要区分向头部添加和其他位置添加的情况
if (index === 0) {
this.first = new Node(ele, this.first);
} else {
let prevNode = this.node(index - 1);
prevNode.next = new Node(ele, prevNode.next);
}
this.size++;
}
// 删除元素 复杂度： O(n)
remove(index) {
this.rangeCheck();
let currentNode = this.first;
if (index === 0) {
this.first = this.first.next;
} else {
// 将前一个next指向下一个即可
let prevNode = this.node(index - 1);
currentNode = prevNode.next;
prevNode.next = currentNode.next;
}
this.size--;
return currentNode.element;
}
// 获取当前下标的元素 复杂度： O(n)
node(index) {
this.rangeCheck(index);
let node = this.first;
for (let i = 0; i < index; i++) {
node = node.next;
}
return node;
}
// 获取元素的下标 复杂度： O(n)
indexof(ele) {
let node = this.first,
index = 0;
while (!!node) {
if (ele === node.element) return index;
node = node.next;
index++
}
return ELEMENT_NOT_FOUND;
}
toString() {
let node = this.first,
str = '';
while (!!node) {
str += `${node.element}-->`;
node = node.next;
}
str += `size = ${this.size}`
return str;
}
}
单向链表优点：
- 不会造成内存空间的浪费，需要多少开辟多少。
单向链表缺点：- 会频繁的开辟、删除内存空间。
由于添加、删除链表元素都需要判断是否是操作第一个节点，可以采用增加虚拟头节点的方式来统一处理
image.png
// 虚拟头节点的链表
class Linklist extends BaseList {
constructor() {
super();
// 增加虚拟头节点 -- 方便之后统一处理
this.first = new Node(null, null);
}
clear() {
this.first = null;
this.size = 0;
}
get(index) {
return this.node(index).element;
}
set(index, ele) {
let node = this.node(index);
let old = node.element;
node.element = ele;
return old;
}
push(ele) {
this.add(ele, this.size);
}
add(ele, index) {
this.rangeCheck();
// if (index === 0) {
// this.first = new Node(ele, this.first);
// } else {
// let prevNode = this.node(index - 1);
// prevNode.next = new Node(ele, prevNode.next);
// }
`统一处理即可，不需要再进行判断`
let prevNode = index === 0 ? this.first : this.node(index - 1);
prevNode.next = new Node(ele, prevNode.next);
this.size++;
}
remove(index) {
this.rangeCheck();
// if (index === 0) {
// this.first = this.first.next;
// } else {
// let prevNode = this.node(index - 1);
// let currentNode = prevNode.next;
// prevNode.next = currentNode.next;
// }
`统一处理`
let prevNode = index === 0 ? this.first : this.node(index - 1);
let currentNode = prevNode.next;
prevNode.next = currentNode.next;
this.size--;
return currentNode.element;
}
node(index) {
this.rangeCheck(index);
// 循环的第一个一定是从虚拟节点的next开始
let node = this.first.next;
for (let i = 0; i < index; i++) {
node = node.next;
}
return node;
}
indexof(ele) {
// 循环的第一个一定是从虚拟节点的next开始
let node = this.first.next,
index = 0;
while (!!node) {
if (ele === node.element) return index;
node = node.next;
index++
}
return ELEMENT_NOT_FOUND;
}
toString() {
// 循环的第一个一定是从虚拟节点的next开始
let node = this.first.next,
str = '';
while (!!node) {
str += `${node.element}-->`;
node = node.next;
}
str += `size = ${this.size}`
return str;
}
}
