JavaScript数据结构 - 链表
定义
链表是一种线性数据结构,表示一组元素,其中每个元素指向下一个元素。链表中的第一个元素是头部,最后一个元素是尾部。
链表数据结构的每个元素必须具有以下属性:
value
:元素的值next
:指向链表中下一个元素的指针(如果没有则为null
)
链表数据结构的主要属性包括:
size
:链表中的元素数量head
:链表中的第一个元素tail
:链表中的最后一个元素
链表数据结构的主要操作包括:
insertAt
:在指定索引处插入元素removeAt
:删除指定索引处的元素getAt
:获取指定索引处的元素clear
:清空链表reverse
:反转链表中的元素
实现
class LinkedList {
constructor() {
this.nodes = [];
}
get size() {
return this.nodes.length;
}
get head() {
return this.size ? this.nodes[0] : null;
}
get tail() {
return this.size ? this.nodes[this.size - 1] : null;
}
insertAt(index, value) {
const previousNode = this.nodes[index - 1] || null;
const nextNode = this.nodes[index] || null;
const node = { value, next: nextNode };
if (previousNode) previousNode.next = node;
this.nodes.splice(index, 0, node);
}
insertFirst(value) {
this.insertAt(0, value);
}
insertLast(value) {
this.insertAt(this.size, value);
}
getAt(index) {
return this.nodes[index];
}
```js
class LinkedList {
constructor() {
this.nodes = [];
}
get size() {
return this.nodes.length;
}
get head() {
return this.nodes[0] || null;
}
get tail() {
return this.nodes[this.nodes.length - 1] || null;
}
insertAt(index, value) {
const previousNode = this.nodes[index - 1];
const nextNode = this.nodes[index + 1] || null;
if (previousNode) previousNode.next = nextNode;
this.nodes.splice(index, 0, { value, next: nextNode });
}
insertFirst(value) {
this.insertAt(0, value);
}
insertLast(value) {
this.insertAt(this.size, value);
}
getAt(index) {
return this.nodes[index] || null;
}
removeAt(index) {
const previousNode = this.nodes[index - 1];
const nextNode = this.nodes[index + 1] || null;
if (previousNode) previousNode.next = nextNode;
return this.nodes.splice(index, 1);
}
clear() {
this.nodes = [];
}
reverse() {
this.nodes = this.nodes.reduce(
(acc, { value }) => [{ value, next: acc[0] || null }, ...acc],
[]
);
}
*[Symbol.iterator]() {
yield* this.nodes;
}
}
const list = new LinkedList();
list.insertFirst(1);
list.insertFirst(2);
list.insertFirst(3);
list.insertLast(4);
list.insertAt(3, 5);
list.size; // 5
list.head.value; // 3
list.head.next.value; // 2
list.tail.value; // 4
[...list.map(e => e.value)]; // [3, 2, 1, 5, 4]
list.removeAt(1); // 2
list.getAt(1).value; // 1
list.head.next.value; // 1
[...list.map(e => e.value)]; // [3, 1, 5, 4]
list.reverse();
[...list.map(e => e.value)]; // [4, 5, 1, 3]
list.clear();
list.size; // 0
list.removeAt(1); // 2
list.getAt(1).value; // 1
list.head.next.value; // 1
[...list.map(e => e.value)]; // [3, 1, 5, 4]
list.reverse();
[...list.map(e => e.value)]; // [4, 5, 1, 3]
list.clear();
list.size; // 0