array_vs_linked_list.ts

import { performance } from 'node:perf_hooks'

const measure = (name: string, cb: () => void) => {
  const start = performance.now()
  cb()
  console.log(name, performance.now() - start)
}

class LLNode {
  value = 0
  constructor(public next?: LLNode) {}

  inc() {
    this.value += 1
  }
}

const test = (reverse = false) => {
  let head = new LLNode()

  let i = 1000
  while (--i) head = new LLNode(head)

  let list: Array<LLNode>

  measure('allocate list', () => {
    list = []
    let next: undefined | LLNode = head
    while (next) {
      list.push(next)
      next = next.next
    }
  })

  const tests = [
    () =>
      measure('walk on list', () => {
        // console.log('list.length', list.length)
        for (let i = 0; i < list.length; i++) {
          list[i]!.inc()
        }
      }),

    () =>
      measure('walk on sibling', () => {
        let next: undefined | LLNode = head
        while (next) {
          next.inc()
          next = next.next
        }
      }),
  ]

  if (reverse) tests.reverse()

  tests.forEach((cb) => cb())

  console.log(
    'sum',
    list!.reduce((acc, { value }) => acc + value, 0),
  )
}

test()
test(true)
test()
test(true)

allocate list 0.03955400000000964
walk on list 0.0819890000000214
walk on sibling 0.03143399999999019
sum 2000
allocate list 0.03283500000000572
walk on sibling 0.0036709999999970933
walk on list 0.002707000000015114
sum 2000
allocate list 0.027856999999983145
walk on list 0.015050999999999704
walk on sibling 0.008157999999980348
sum 2000
allocate list 0.011464999999986958
walk on sibling 0.002105999999997721
walk on list 0.0023999999999944066
sum 2000