链表的概念
链表的实现
链表的多种形式
LeeCode 题目

链表的概念

链表是有序的数据结构，链表中的每个部分称为节点
- 可以在任意位置操作
- 可以从首、尾、中间进行数据存取
链表可以从首、尾、中间进行数据存取
链表的元素在内存中不必时连续的空间
优点：添加与删除不会导致其余元素位移
缺点：无法根据索引快速定位元素

为什么不直接使用数组？
某些操作中链表的性能要比数组好

数组在内存中占用一段连续的空间
添加、移除会导致后续元素位移，（操作非末尾的数据时）性能开销大

小结:

获取、修改元素时，数组效率高
添加、删除元素时，链表效率高

链表的实现

要实现以下功能：

节点类： value、 next
链表类：
- addAtTail 尾部添加节点
- addAtHead 头部添加节点
- addAtIndex 指定位置添加节点
- get 获取节点
- removeAtIndex 删除指定节点

链表的实现

class LinkedNode {
  constructor(value) {
    this.value = value
    this.next = null 
  }
}
class LinkedList {
  constructor() {
    this.count = 0
    this.head = null
  }
  // 添加节点 尾
  addAtTail (value) {
    const node = new LinkedNode(value)
    if (this.count === 0) {
      this.head = node
    } else {
      let cur = this.head
      while(cur.next != null) {
        cur = cur.next
      }
      cur.next = node
    }
    this.count ++
  }
  // 添加节点 首
  addAtHead (value) {
    const node = new LinkedNode(value)
    if (this.count === 0) {
      this.head = node
    } else {
      node.next = this.head
      this.head = node
    }
    this.count ++
      }
      // 根据索引 获取节点
      get(index) {
      if (this.count === 0 || index< 0 || index >= this.count) {
      return 
      }
      // 迭代链表， 找到对应节点
      let current = this.head
      for (let i = 0; i < index; i++) {
      current = current.next
      }
      return current
      }
      // 根据索引 添加节点
      addAtIndex(value, index) {
      if (this.count ===0 || index >= this.count) {
      return
      }
      // 如果 index <= 0 添加到头部
      if (index <= 0) {
      return this.addAtHead(value)
      }
      // 后面为正常区间处理
      const prev = this.get(index -1)
      const next = prev.next
      const node = new LinkedNode(value)
      prev.next = node
      node.next = next
      this.count++
      }
      // 删除
      removeAtIndex (index) {
      if (this.count === 0 || index < 0 || index >= this.count) {
      return
      }
      if (index === 0) {
      this.head = this.head.next
      } else {
      const prev = this.get(index -1)
      prev.next = prev.next.next
      }
      this.count--
      }
      }
      const l = new LinkedList();

链表的多种形式

常见的链表形式有：

双向链表
循环链表（环形链表）
双向链表
双向链表指的是在普通链表的基础上，增加一个用于记录上一个节点的属性prev，可进行双向访问

循环链表（环形链表）

循环链表又称为环形链表，指的是链表最后一个节点的 next 指向第一个节点，形成首尾相连的循环结构，称为循环列表
在实际使用中，环的结束点可以为链表的任意节点

大前端

链表

链表的概念

链表的实现

链表的多种形式

双向链表

循环链表（环形链表）

反转链表