Insert-to-sorted-list.js

// Insert a number to a sorted linked list with respect to the sorted order

function dll() {
  this.head = null
}

dll.prototype.push = function(val) {
  let head = this.head, curr = head, prev = head
  if (!head) this.head = { val: val, prev: null, next: null }
  else {
    while (curr && curr.next) {
      prev = curr
      curr = curr.next
    }
    curr.next = { val: val, prev: curr, next: null }
  }
}

dll.prototype.print = function() {
  let curr = this.head
  while(curr) {
    console.log(curr.val)
    curr = curr.next
  }
}

dll.prototype.pushSorted = function(val) {
  let curr = this.head
  // empty list
  if (!curr) {
    curr = { val: val, prev: null, next: null }
    this.head = curr
  } else {
    while(curr) {
      if (val <= curr.val) {       
        let n = { val: val, prev: curr.prev, next: curr }
        // only one element
        if (curr == this.head) {
          this.head = n
          return
        }
        // in between
        else {
          curr.prev.next = n
          curr.prev = n
          return;
        }
      }
      // reached last element
      if (!curr.next) {
        curr.next = { val: val, prev: curr, next: null }
        return
      }
      curr = curr.next
    }
  }
}


let l = new dll()
l.push(3)
l.push(7)
l.push(10)
l.push(10)
l.push(15)
l.push(20)
l.print()
console.log("res")
l.pushSorted(0)
l.print()