如何提高进入链表的性能?

Question

我试图自己实现一个链表，并面临一个问题："我如何获得O(1(复杂度的Node？

是否有机会(或良好实践(来改进"获取"方法？我需要在链表中添加其他数据结构吗？我在一些关于使用哈希表进入链表的文章中读到。正常吗？

class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// O(1)
addToTail(value) {
let newNode = new Node(value);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
// O(n)
get(value) {
let cur = this.head;
while (cur && cur.value !== value) {
cur = cur.next;
}
return cur;
}
// O(n)
remove(value) {
let cur = this.head;
let prev = null;
while (cur && cur.value !== value) {
prev = cur;
cur = cur.next;
}
if (cur) {
// First Node
if (this.head === cur) {
this.head = cur.next;
if (this.head === null) {
this.tail = null;
}
} else {
// Not first Node
prev.next = cur.next;
if (cur.next === null) {
this.tail = prev;
}
}
return true;
}
return false;
}
print() {
let cur = this.head;
while (cur !== null) {
console.log(cur.value);
cur = cur.next;
}
}
}
const cars = ['Audio', 'BMW', 'Mazda', 'Toyota'];
const list = new LinkedList();
for (let i = 0; i < cars.length; i++) {
list.addToTail(cars[i])
}
list.remove('Audio')
list.addToTail('Kia')
list.addToTail('Lexus')
console.log(list.get('Mazda'));

Answer 1

...并面临一个问题："我如何获得 O(1( 复杂度的 Node？

你不能。链表始终需要一定程度的扫描。一个纯单向链表是O(n(，IIRC。

我在一些关于使用哈希表进入链表的文章中读到。正常吗？

有一个映射结构来对键进行哈希以找到正确的"存储桶"的情况并不少见，其中"存储桶"是链表或类似的线性搜索容器，用于所有键哈希相同的条目。基本上，get是：

• 对密钥进行哈希
处理
• 按哈希查找存储桶
• 在存储桶中搜索密钥

不过，在这一点上，整体的东西不再是一个链表，它更像是一个地图。即使是由哈希表支持的映射也不是 O(1(，尽管它会比 O(n( 更好。

(我知道你这样做是为了学习目的，但我必须指出JavaScript的原生Map，它确实使用哈希或(引用规范("......平均而言，提供对集合中元素数呈亚线性的访问时间的其他机制。