链表

[jinzhepro]

线性结构，内存不连续

单链表

• 头结点
• 后继指针
• 尾节点
• 空地址null

插入和删除

查找

链表不支持随机访问,所以需要遍历节点,时间复杂度O(n)

代码

使用数组模拟

class Node{
  // 单个节点
  constructor(data,next) {
    this.data= data
    this.next = next
  }
}
class NodeList {
  constructor(list) {
    // 初始化数据
    this.list = [2,4,3,5,6,8,45,34,32]
    this.nodeList = []
    this.createNodeList()
  }

  // 创建节点
  createNodeList(){
    for (let i = 0; i < this.list.length; i++){
      const node = new Node(this.list[i], this.list[i + 1] || null)
      this.nodeList.push(node)
    }
    return this.nodeList
  }

  insertNode({preData, data}){
    for (let i = 0; i < this.nodeList.length; i++){
      // 查找前驱节点
      if(this.nodeList[i].data === preData){
        // 构建节点
        const node = new Node(data, this.nodeList[i + 1] ? this.nodeList[i + 1].data : null)
        // 插入
        this.nodeList.splice(i,1, node)
      }
    }
    return this.nodeList
  }

  // 删除节点
  removeNode({data}){
    for (let i = 0; i < this.nodeList.length; i++){
      // 查找前驱节点
      if(this.nodeList[i].data === data){
        // 修改前驱结点的next指向
        this.nodeList[i - 1] && (this.nodeList[i - 1].next = this.nodeList[i + 1].data)
      }
    }
    return this.nodeList
  }
}

const nodeList = new NodeList()
nodeList.insertNode({preData: 8, data: 50})
nodeList.removeNode({data: 50})
console.log(nodeList)

循环链表

双向链表

查找 删除 添加

可以通过前驱结点直接查找,时间复杂度为O(1)

双向循环链表

链表和数组的比较

	数组	链表
插入,删除	O(n)	O(1)
随机访问	O(1)	O(n)
内存	连续内存,大小固定	不连续内存,动态扩容