为什么Javasript中链表项插入比数组项插入慢？

Question

众所周知，无论位置如何，链表项插入都需要 O(1) 时间，而数组则需要 O(n) 时间，具体取决于位置，最坏情况是 O(n)，第一个位置和最好情况都是 O(1 ），最后一个位置。

我在 VS Code 中检查过这一点，并惊讶地发现，即使将项目放置在起始位置，链表中的插入速度也比数组慢 3 倍。为什么会这样？

class Linkedlist{
    constructor(){
        this.head = null;
        this.size = 0;
    }
    add(d){
        this.head = new Node(d, this.head);
        ++this.size;
    }
    displace(){
        let d = this.head;
        this.head = d.next;
        --this.size;
        return d.data;
    }
    place(d){
        if(this.head){
            if((this.head).data >= 14)
                this.add(d);
            else{
                let pre = this.head;
                let cur = pre.next;
                while(cur && (cur.data<14)){
                    pre = cur;
                    cur = cur.next;
                }
                pre.next = new Node(d,cur);
                ++this.size;
            }
        }else
            this.add(d);
    }
}

class Node{
    constructor(data, next=null){
        this.data = data;
        this.next = next;
    }
}

let A = new Linkedlist();
A.add(29);
A.add(28);
A.add(27);
A.add(26);
A.add(25);
A.add(24);
A.add(23);
A.add(22);
A.add(21);
A.add(20);
A.add(19);
A.add(18);
A.add(17);
A.add(16);
A.add(15);
A.add(14);
A.add(13);
A.add(12);
A.add(11);
A.add(10);
const start = performance.now();
A.place(13.5);
const end = performance.now();
console.log(end-start);

因此，在这里我使用类概念实现了一个链表，并在启动计时器之前在开始处添加了所有元素。 place 函数用于迭代列表，直到到达最后一个节点或发现数据值等于或大于 14，在那里它放置 13.5。

let A = [10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29];
let j;
const start = performance.now();
for(j=0; j<A.length; j++){
    if(A[j]>=14)
        break;
}
A.splice(j,0,13.5);
const end = performance.now();
console.log(end-start);

同样，我对数组也这样做了。

Answer 1

asymptotic

行为的信息，并且 JavaScript 数组 splice 方法受益于本机实现，因此您需要使用更大的数据集来测试它。

其次，您的测试同时测试两个操作：

查找

数据结构中的位置，以及插入该位置的值。对于两种数据结构，查找部分具有相同的 O(n) 时间复杂度，因此明智的做法是从测试中删除该方面，这样您就可以只关注用于插入的时间。因此，这意味着您应该仅测试数据结构前面的插入。 最后，测试应重复多次才能获得可靠的结果。

这是一个测试，在两个结构中插入 1000 个值，然后计算重复以下操作一百万次所需的时间：

在前面插入固定值

• 再次从前面删除相同的值
为了简化测试，我还重命名了链表类中的方法，使它们具有与数组原型相同的名称（

shift

和

unshift

）。

class LinkedList{
    constructor(...values) {
        this.head = null;
        this.size = 0;
        for (const value of values.reverse()) {
            this.unshift(value);
        }
    }
    // Use the same method names as Array.prototype has
    unshift(d) {
        this.head = new Node(d, this.head);
        ++this.size;
    }
    shift() {
        let d = this.head;
        this.head = d.next;
        --this.size;
        return d.data;
    }
}

class Node{
    constructor(data, next=null) {
        this.data = data;
        this.next = next;
    }
}

function test(obj, numTests) {
    const start = performance.now();
    for (let i = 0; i < numTests; i++) {
        obj.unshift(123);
        obj.shift();
    }
    return Math.round(performance.now() - start);
}

// Set up
const numValues = 1000;
const numTests = 1_000_000;
const arr = [...Array(numValues).keys()];
const lst = new LinkedList(...arr);
// Repeatedly add and remove a value at the front of the data structure
const arrTime = test(arr, numTests);
const lstTime = test(lst, numTests);
// Report
console.log({ arrTime, lstTime });

在我的电脑上，使用此设置后阵列操作会变慢。