JavaScript 实现链表(LinkedList)

单向链表

function Node(element) {
  this.element = element
  this.next = null
}

class LinkedList {
  constructor() {
    this.head = new Node("head")
  }
  find(item) {
    let currentNode = this.head 
    while (currentNode.element !== item) {
      currentNode = currentNode.next
    } 
    return currentNode
  }

  insert(newElement, item) {
    const newNode = new Node(newElement)
    const currentNode = this.find(item) 
    newNode.new = currentNode.next
    currentNode.next = newNode
  }

  display() {
    let currentNode = this.head
    while (currentNode.next !== null) {
      console.log(currentNode.next.element)
      currentNode = currentNode.next
    }
  }
  findPrevious(item) {
    let currentNode = this.head 
    while (currentNode.next !== null && currentNode.next.element !== item) {
      currentNode = currentNode.next
    }
    return currentNode
  }
  remove(item) {
    const previousNode = this.findPrevious(item)
    if (previousNode.next !== null) {
      previousNode.next = previousNode.next.next
    }
  }
}

const cities = new LinkedList()
cities.insert("Conway", "head")
cities.insert("Russellville", "Conway")
cities.insert("Carlisle", "Russellville")
cities.insert("Alma", "Carlisle")
cities.display()
cities.remove("Carlisle")
console.log('-------------')
cities.display()

双向链表

class Node {
  constructor(element) {
    this.element = element
    this.next = null
    this.previous = null
  }
}

class LinkedList {
  constructor() {
    this.head = new Node('head')
  }
  find(item) {
    let currentNode = this.head 
    while (currentNode.element !== item) {
      currentNode = currentNode.next
    } 
    return currentNode
  }
  insert(newElement, item) {
    const newNode = new Node(newElement)
    const currentNode = this.find(item)
    newNode.next = currentNode.next
    newNode.previous = currentNode
    currentNode.next = newNode
  }
  display() {
    let currentNode = this.head
    while (currentNode.next !== null) {
      console.log(currentNode.next.element)
      currentNode = currentNode.next
    }
  }
  remove(item) {
    const currentNode = this.find(item)
    if (currentNode !== null) {
      // 父节点的子节点换成当前节点的下节点
      currentNode.previous.next = currentNode.next
      // 子节点的父节点换成当前节点的父节点
      currentNode.next.previous = currentNode.previous
      // 销毁这个节点
      currentNode.next = null
      currentNode.previous = null
    }
  }
  findLastNode() {
    let currentNode = this.head 
    while (currentNode.next !== null) {
      currentNode = currentNode.next  
    }
    return currentNode
  }
  // 反序显示双向链表的元素
  displayReverse() {
    // 将第一个父节点换成最后一个
    let currentNode = this.head
    currentNode = this.findLastNode()
    while (currentNode !== null) {
      console.log('----', currentNode.element)
      currentNode = currentNode.previous
    }
  }
}

未完待续