数据结构——双向链表

一、区分单/双向链表

单向链表相连的过程是单向的，只能从一个方向遍历

• 可以获取当前节点的下一个节点，但是很难回到上一个节点，但是实际开发中经常会有类似的需求

双向链表可以从两个方向遍历

• 一个节点既有向前连接的引用，也有向后连接的引用
• 每次插入和删除的时候，需要处理四个引用，比单向链表更加复杂
• 相对于单向链表，占用的内存空间相对更大

双向链表的特点

• 使用一个head和tail分别指向头部和尾部的节点
• 每个节点分别包括前指针/后指针/保存的元素
• 双向链表第一个节点的前指针指向null
• 双向链表最后一个节点的后指针指向null

二、双向链表常见的操作

在单向链表的基础上进行补充：

数据结构：单向链表

forwardString():返回正向遍历的节点字符串形式

backwordString:返回反向遍历的节点字符串形式

三、封装双向链表

1、按照位置插入数据（insert）方法图解：

• position=0

• position=length

• 0<position<length

2、按照位置删除元素

• 删除头部元素

• 删除尾部元素

• 删除中间元素

四、代码实现

/**
 * 封装双向链表
*/
function DoudlyLinkedList() {
  // 属性
  this.head = null
  this.tail = null
  this.length = 0

  // 内部类(用于创建节点)
  function Node(data) {
    this.data = data
    this.prev = null
    this.next = null
  }

  // 尾部追加数据
  DoudlyLinkedList.prototype.append = function (data) {
    // 创建节点
    let newNode = new Node(data)

    // 判断添加之前是否为空链表
    if (this.head == null) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      newNode.prev = this.tail
      this.tail = newNode
    }

    // 修改长度
    this.length += 1
  }
  // 正向遍历的方法
  DoudlyLinkedList.prototype.forwardString = function () {
    let flag = this.head
    let result = ''
    while (flag) {
      result += flag.data + ' '
      flag = flag.next
    }
    return result
  }
  // insert
  DoudlyLinkedList.prototype.insert = function (position, data) {
    // position判断
    if (position < 0 || position > this.length) return false
    // 创建节点
    let newNode = new Node(data)
    // 判断插入位置
    if (position == 0) {
      // 判断添加之前是否为空链表
      if (this.head == null) {
        this.head = newNode
        this.tail = newNode
      } else {
        this.head.prev = newNode
        newNode.next = this.head
        this.head = newNode
      }
    } else if (position == this.length) {
      this.tail.next = newNode
      newNode.prev = this.tail
      this.tail = newNode
    } else {
      let index = 0
      let flag = this.head
      this.previous = null
      while (index < position) {
        previous = flag
        flag = flag.next
        index++
      }
      newNode.next = flag
      newNode.prev = previous
      flag = prev = newNode
      previous.next = newNode
    }

    this.length += 1
    return true
  }
  // removeAt
  DoudlyLinkedList.prototype.removeAt = function (position) {
    if (position < 0 || position >= this.length) return null
    // 判断移除的位置
    let flag = this.head
    if (position == 0) {
      if (this.length == 0) {
        this.head = null
        this.tail = null
      } else {
        this.head = this.head.next
        this.head.prev = null
      }
    } else if (position == this.length - 1) {
      flag = this.tail
      this.tail = this.tail.prev
      this.tail.next = null
    } else {
      let index = 0
      let previous = null
      while (index < position) {
        previous = flag
        flag = flag.next
        index++
      }
      previous.next = flag.next
      flag.next.prev = previous
    }

    this.length -= 1
    return flag.data
  }

  // 获取元素的位置
  DoudlyLinkedList.prototype.indexOf = function (data) {
    let flag = this.head
    let index = 0
    while (flag) {
      if (flag.data == data) {
        return index
      }
      index++
      flag = flag.next
    }
    return -1
  }

  // 根据元素删除
  DoudlyLinkedList.prototype.remove = function (data) {
    let index = this.indexOf(data)
    return this.removeAt(index)
  }

  // 判断是否为空
  DoudlyLinkedList.prototype.isEmpty = function () {
    return this.length == 0
  }

  // 获取链表长度
  DoudlyLinkedList.prototype.size = function () {
    return this.length
  }
  // 获取第一个元素
  DoudlyLinkedList.prototype.getHead = function () {
    return this.head.data
  }
  // 获取最后一个元素
  DoudlyLinkedList.prototype.getTail = function () {
    return this.tail.data
  }
}

let Dlist = new DoudlyLinkedList()
Dlist.append('a')
Dlist.append('b')
Dlist.append('c')
Dlist.append('d')
console.log(Dlist.forwardString())  // a b c d
console.log(Dlist.insert(1, 'ok'))
console.log(Dlist.insert(Dlist.length, 'no'))
console.log(Dlist.insert(0, 'first'))
console.log(Dlist.forwardString())  // first a ok b c d no
console.log(Dlist.removeAt(1))  // a
console.log(Dlist.forwardString())  // first ok b c d no
console.log(Dlist.indexOf('no'))  // 5
console.log(Dlist.remove('first'))  // first
console.log(Dlist.forwardString())  // ok b c d no
console.log(Dlist.isEmpty())  // false
console.log(Dlist.size())     // 5
console.log(Dlist.getHead())  // ok
console.log(Dlist.getTail())  // no