const assert = require('node:assert').strict

class Node {
  constructor(value) {
    this.value = value
    this.prev = null
    this.next = null
  }

  unlink() {
    if (this.prev !== null) {
      this.prev.next = this.next
    }

    if (this.next !== null) {
      this.next.prev = this.prev
    }

    this.prev = null
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.next = null
  }

  insert (node) {
    if (!(node instanceof Node)) {
      node = new Node(node)
    }
    
    if (this.head === null) {
      this.tail = node
    } else {
      node.next = this.head
      this.head.prev = node
    }
    this.head = node
  }

  pop() {
    if (this.tail === null) {
      return undefined
    }

    const node = this.tail
    if (this.head === this.tail) {
      this.head = null
      this.tail = null
    } else {
      this.tail = node.prev
    }

    node.unlink()
    return node
  }

  iterFront() {
    let ptr = this.head
    const arr = []
    while (ptr !== null) {
      arr.push(ptr.value)
      ptr = ptr.next
    }
    return arr
  }

  iterBack() {
    let ptr = this.tail
    const arr = []
    while (ptr !== null) {
      arr.push(ptr.value)
      ptr = ptr.prev
    }
    return arr
  }
}

// tests
function assertArrayEquals (a1, a2) {
  assert.deepStrictEqual(a1, a2)
}

function assertArrayLength(a1, len) {
    assert.deepStrictEqual(a1.length, len)
}

let ll = new LinkedList()

for (let i = 0; i < 10; i++) {
  ll.insert(i)
  assert.deepStrictEqual(ll.iterFront(), ll.iterBack().reverse())
  assertArrayLength(ll.iterFront(), i + 1)
  assertArrayLength(ll.iterBack(), i + 1)
}

for (let i = 9; i >= 0; i--) {
  ll.pop()
  assert.deepStrictEqual(ll.iterFront(), ll.iterBack().reverse())
  assertArrayLength(ll.iterFront(), i)
  assertArrayLength(ll.iterBack(), i)
}

for (let i = 0; i < 15; i++) {
  ll.insert(Math.random())
  assert.deepStrictEqual(ll.iterFront(), ll.iterBack().reverse())
  assertArrayLength(ll.iterFront(), i + 1)
  assertArrayLength(ll.iterBack(), i + 1)
}

for (let i = 14; i >= 0; i--) {
  ll.pop()
  assert.deepStrictEqual(ll.iterFront(), ll.iterBack().reverse())
  assertArrayLength(ll.iterFront(), i)
  assertArrayLength(ll.iterBack(), i)
}

console.log("all tests passed")