链表数据结构特性

优点

• 插入与删除效率高(O(1))

缺点

• 查询或随机读取某个元素时效率低，比如在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道 它所处的地址，只能从第一个开始一个个查询 (0(n))

链表的实现

一. 单链表的基础操作

对单链表的操作有：

find(item) // 在单链表中寻找item元素
insert(element, item) // 向单链表中插入元素
remove(item) // 在单链表中删除一个节点
append(element) // 在单链表的尾部添加元素
findLast() // 获取单链表的最后一个节点
display() // 单链表的遍历显示
isEmpty() // 判断单链表是否为空
show() // 显示当前节点
getLength() // 获取单链表的长度
advance(n, currNode) // 从当前节点向前移动n个位置
clear() // 清空单链表

只要实现上述的这些方法，一个基本的单链表结构就实现了。

二. 节点

链表中的节点类型描述如下：

class Node {
  constructor(data) {
    this.data = data // 节点的数据域
    this.prev = null // 节点的指针域
    this.next = null // 节点的指针域
  }
}

当然，JS 中并没有指针，节点的指针只是借用的 C 语言中的概念。
之所以用 prev 和 next 两个指针域是为了实现双向链表，在实现单链表时，prev 指针并没有用到。

三. 单链表类

将单链表的基础操作方法放在单链表的类中，就形成了单链表数据结构的大概框架了。

class SingleList {
  constructor() {
    this.size = 0 // 单链表的长度
    this.head = new Node('head') // 表头节点
    this.currNode = '' // 当前节点的指向
  }

  find(item) {} // 在单链表中寻找item元素
  insert(item, element) {} // 向单链表中插入元素
  remove(item) {} // 在单链表中删除一个节点
  append(element) {} // 在单链表的尾部添加元素
  findLast() {} // 获取单链表的最后一个节点
  isEmpty() {} // 判断单链表是否为空
  show() {} // 显示当前节点
  getLength() {} // 获取单链表的长度
  advance(n, currNode) {} // 从当前节点向前移动n个位置
  display() {} // 单链表的遍历显示
  clear() {} // 清空单链表
}

剩下的问题就拆分为了实现一个个操作方法了

四. 实现主要方法

我们就从最基础的 添加节点->查找节点->删除节点->修改节点

1.找出链表中最后一个节点

findLast() {
    let last = this.head
    while (last.next) {
      last = last.next
    }
    return last
  }

为啥要先实现这个方法？

因为你得找到最后一个节点才方便 append 节点

2.在链表的尾部添加节点

 append(item) {
    let last = this.findLast()
    const node = new Node(item)
    last.next = node
    node.prev = last
  }

3.查找节点

find(item) {
    const _find = (item, node) => {
      if (!node) return null
      if (node.data === item) {
        return node
      } else {
        return _find(item, node.next) // 不是当前节点 递归查找 直到找到节点或者查找到链表最后一个节点返回null
      }
    }
    return _find(item, this.head)
  }

4.在单链表中删除一个节点

remove(item) {
    if (item === 'head') return console.log('不能删除根元素')
    let node = this.find(item)
    if (node) {
      if (node.next) {
        // 要删除的节点有子节点 将子节点连接到当前节点
        let next = node.next
        next.prev = node.prev
        node.prev.next = next
      } else {
        // 要删除的节点为最后一个节点
        node.prev.next = null
      }
    } else {
      console.log('没有这个节点')
    }
  }

5.单链表的遍历显示

 display() {
    let res = ''
    let current = this.head
    if (current) res += current.data + ' -> '
    while (current.next) {
      current = current.next
      res += current.data + ' -> '
    }
    return res
  }

。。。 剩下的方法待实现 。。。

五、单链表完整代码

class Node {
  constructor(data) {
    this.data = data // 节点的数据域
    this.prev = null // 节点的指针域
    this.next = null // 节点的指针域
  }
}

class SingleList {
  constructor() {
    this.size = 0 // 单链表的长度
    this.head = new Node('head') // 表头节点
    this.currNode = '' // 当前节点的指向
  }

  insert(item, element) {} // 向单链表中插入元素
  isEmpty() {} // 判断单链表是否为空
  show() {} // 显示当前节点
  getLength() {} // 获取单链表的长度
  advance(n, currNode) {} // 从当前节点向前移动n个位置
  clear() {} // 清空单链表

  // 在单链表的尾部添加元素
  append(item) {
    let last = this.findLast()
    const node = new Node(item)
    last.next = node
    node.prev = last
  }

  // 获取单链表的最后一个节点
  findLast() {
    let last = this.head
    while (last.next) {
      last = last.next
    }
    return last
  }

  // 在单链表中寻找item元素
  find(item) {
    const _find = (item, node) => {
      if (!node) return null
      if (node.data === item) {
        return node
      } else {
        return _find(item, node.next)
      }
    }
    return _find(item, this.head)
  }

  // 单链表的遍历显示
  display() {
    let res = ''
    let current = this.head
    if (current) res += current.data + ' -> '
    while (current.next) {
      current = current.next
      res += current.data + ' -> '
    }
    return res
  }

  // 在单链表中删除一个节点
  remove(item) {
    if (item === 'head') return console.log('不能删除根元素')
    let node = this.find(item)
    if (node) {
      if (node.next) {
        // 要删除的节点有子节点 将子节点连接到当前节点
        let next = node.next
        next.prev = node.prev
        node.prev.next = next
      } else {
        // 要删除的节点为最后一个节点
        node.prev.next = null
      }
    } else {
      console.log('没有这个节点')
    }
  }
}

let singleList = new SingleList()
singleList.append('item1')
singleList.append('item2')
singleList.append('item3')

// console.log(singleList.find('item2'))
// console.log(singleList.display())

singleList.remove('item2')
console.log(singleList.display())

双向链表

两个节点链接允许在任一方向上遍历列表。