Array vs linked list (insertion)

Benchmark created on July 19, 2024

Setup

function buildArray(data, directions) {
    let index = 0;
    const result = [data[0]];
    const len = data.length;
    for (let i = 1; i < len; ++i)
        result.splice(index += directions[i], 0, data[i]);
    return result;
}
function convertToArray(list) {
    const len = list.size;
    const result = Array(len);
    for (let node = list.head, i = 0; i < len; ++i, node = node.next)
        result[i] = node.value;
    return result;
}
function buildList(data, directions) {
    let node = {
        value: data[0],
        previous: undefined,
        next: undefined
    };
    const list = {
        head: node,
        tail: node,
        size: 1
    };
    const len = data.length;
    for (let i = 1; i < len; ++i) {
        if (directions[i]) {
            const newNode = {
                value: data[i],
                previous: node,
                next: node.next
            };
            if (node.next)
                node.next.previous = newNode;
            node = node.next = newNode;
            if (node.previous === list.tail)
                list.tail = node;
        }
        else {
            const newNode = {
                value: data[i],
                previous: node.previous,
                next: node
            };
            if (node.previous)
                node.previous.next = newNode;
            node = node.previous = newNode;
            if (node.next === list.head)
                list.head = node;
        }
        list.size++;
    }
    return list;
}
function sumArray(array) {
    const len = array.length;
    let sum = 0;
    for (let i = 0; i < len; ++i)
        sum += array[i];
    return sum;
}
function sumList(list) {
    let node = list.head;
    let sum = 0;
    while (node) {
        sum += node.value;
        node = node.next;
    }
    return sum;
}
const N = 1000;
const data = Array(N);
const directions = Array(N);
let array;
let list;
for (let i = 0; i < N; ++i) {
    data[i] = ~~(Math.random() * 100);
    directions[i] = ~~(Math.random() * 2);
}

Test runner

array = buildArray(data, directions);

list = buildList(data, directions);

list = buildList(data, directions);
array = convertToArray(list);

array = buildArray(data, directions);
sumArray(array);

list = buildList(data, directions);
sumList(list);

list = buildList(data, directions);
array = convertToArray(list);
sumArray(array);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on July 19, 2024