链表手写题

[TickHeart]

基础题

给定一个链表，请写出他的 增，删，改，查

进阶

给定一个双向链表，请写出他的 增，删，改，查

[chenfan0]

class LinkList {
  constructor() {
    this.head = null
  }

  #genNode(value) {
    return {
      value,
      next: null
    }
  }

  insert(value) {
    const node = this.#genNode(value)
    if (this.head === null) {
      this.head = node
    } else {
      let dummy = this.head

      while (dummy.next) {
        dummy = dummy.next
      }
      dummy.next = node
    }
  }

  remove(value) {
    let dummy = this.head
    let prev = null
    while (dummy) {
      if (dummy.value === value) {
        prev.next = dummy.next
        return true
      }
      prev = dummy
      dummy = dummy.next
    }


    return false
  }

  search(value) {
    let dummy = this.head
    while (dummy) {
      if (dummy.value === value) {
        return true
      }
      dummy = dummy.next
    }

    return false
  }

  modify(oldValue, newValue) {
    let dummy = this.head
    while (dummy) {
      if (dummy.value === oldValue) {
        dummy.value = newValue
        return true
      }
      dummy = dummy.next
    }

    return false
  }

  toJson() {
    let dummy = this.head
    let result = ''

    while (dummy) {
       result += '=>' + dummy.value 
       dummy = dummy.next
    }

    return result.slice(2)
  }

}

const linkList = new LinkList()

linkList.insert(1)
linkList.insert(2)
linkList.insert(3)
linkList.insert(4)
linkList.insert(5)
console.log(linkList.toJson());

linkList.remove(2)
console.log(linkList.toJson());

linkList.modify(3, 10)
console.log(linkList.toJson());

console.log(linkList.search(2));

[TickHeart]

ok ,有没有挑战进阶题的

[chenfan0]

class DoubleLinkList {
  constructor() {
    this.head = null;
  }

  #genNode(value) {
    return {
      value,
      prev: null,
      next: null
    }
  }

  insert(value) {
    const node = this.#genNode(value)
    if (this.head === null) {
      this.head = node
    } else {
      let dummy = this.head
      while(dummy.next) {
        dummy = dummy.next
      }
      node.prev = dummy
      dummy.next = node
    }
  }

  remove(value) {
    if (this.head === null) return false
    if (this.head.value === value) {
      this.head = this.head.next
      if (this.head) {
        this.head.prev = null
      }
      return true
    }
    let dummy = this.head
    while (dummy.next) {
      if (dummy.value === value) {
        const prev = dummy.prev
        prev.next = dummy.next
        dummy.next.prev = prev
        return true
      }
      dummy = dummy.next
    }
    if (dummy.value === value) {
      dummy.prev.next = null
      return true
    }

    return false
  }

  search(value) {
    let dummy = this.head
    while (dummy) {
      if (dummy.value === value) {
        return true
      }
      dummy = dummy.next
    }
    return false
  }

  modify(oldValue, newValue) {
    let dummy = this.head
    while (dummy) {
      if (dummy.value === oldValue) {
        dummy.value = newValue
        return true
      }
      dummy = dummy.next
    }
    return false
  }

  toJson() {
    let str = ''
    let dummy = this.head

    while (dummy) {
      str +=  '<=>' + dummy.value
      dummy = dummy.next
    }

    return str.slice(3);
  }
}

const dbl = new DoubleLinkList()
dbl.insert(1)
dbl.insert(2)
dbl.insert(3)
dbl.insert(4)
dbl.insert(5)
console.log(dbl.toJson());
dbl.remove(1)
console.log(dbl.toJson());
dbl.remove(3)
console.log(dbl.toJson());
dbl.remove(5)
console.log(dbl.toJson());
console.log(dbl.search(2));
dbl.modify(2, 3)
console.log(dbl.toJson());