Removing the First Item: Linked List vs. Array

talk random
1

For fun, I decided to calculate how much faster a linked list is at removing the first item compared to an array (using array.shift()). As it turns out, on average, when dealing with 10,000 items, a linked list is about 400% faster compared to an array.

Here is the example:

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <script src="https://www.kirupa.com/js/linkedlist_v1.js"></script>
</head>

<body>
  <script>
    let myList = new LinkedList();
    let start, end;

    for (let i = 0; i < 10000; i++) {
      let num = Math.round(Math.random() * 10000);
      myList.addFirst(num);
    }

    start = performance.now();

    for (let i = 0; i < 10000; i++) {
      myList.removeFirst();
    }

    end = performance.now();
    console.log("Elapsed time for linkedlist is: " + (end - start));

    let myArray = [];

    

    for (let i = 0; i < 10000; i++) {
      let num = Math.round(Math.random() * 10000);
      myArray.push(num)
    }

    start = performance.now();

    for (let i = 0; i < 10000; i++) {
      myArray.shift();
    }

    end = performance.now();
    console.log("Elapsed time for arrays is: " + (end - start));
  </script>
</body>

</html>
1 Like
2

Yeah, but ya cheating :stuck_out_tongue_winking_eye:
At not time do you actually remove an item, you only change a reference to what the first item is. The item that was originally pointed to still exists. Wonder how the GC would eventually react to this.

2 Likes
3

That would be an implementation detail :sweat_smile:

If you remove the last item, the performance between both are very similar!

1 Like