链表

原文链接：https://note.noxussj.top/?source=sifo

什么是链表？

链表是有序的数据结构，链表中的每个局部称为节点。能够首、尾、两头进行数据存取，链表的元素在内存中不用是间断的空间，每个节点通过 next 指针指向下一个节点。

长处

链表的增加和删除不会导致其余元素位移。

毛病

无奈依据索引疾速定位元素。

数组和链表区别
  • 获取、批改元素时，数组效率高
  • 增加、删除元素时，链表效率高
  • 数组增加、移除会导致后续元素位移，性能开销大
环形链表

指的是链表最初一个节点的 next 指向第一个节点，造成首尾相连的循环构造。

链表环路检测

解题思路

  1. 快慢指针法实现
  2. slow 指针每次挪动一位，fast 指针每次挪动两位，如果他们相遇则阐明链表存在环
  3. 新指针 ptr 从 head 开始挪动，与 slow 相遇的地位即为环的终点
  4. 由 fast 指针挪动间隔为 slow 的两倍可得出公式： a + (nb + nc + b) = 2(a + b)
  5. 变动解决后失去新公式： a = (n - 1)(b + c) + c

实现性能

在 JavaScript 中没有链表，咱们能够通过模仿一个类或者是通过 Object 实现链表的所有性能。

节点类
  • value 以后节点值

  • next 指向下一个节点

    链表类
  • addAtTail 尾部增加节点
  • addAtHead 头部增加节点
  • addAtIndex () 指定地位增加节点
  • get 获取节点
  • removeAtIndex () 删除指定节点
利用场景
  • leetcode 两数相加

根底案例

通过对象实现

    // 链表    let a = { val: 'a', next: null }    let b = { val: 'b', next: null }    let c = { val: 'c', next: null }    let d = { val: 'd', next: null }        a.next = b    b.next = c    c.next = d        // 尾部增加节点    let e = { val: 'e', next: null }    d.next = e        // 头部增加节点    let z = { val: 'z', next: null }    z.next = a    a = z        // 指定地位增加节点    let f = { val: 'f', next: null }    c.next = f    f.next = d        // 删除指定节点    d.next = null

通过类模仿实现

    /**    * 节点类    */    class Node {    constructor(value) {    this.value = value    this.next = null    }    }        /**    * 链表类    */    class Link {    constructor() {    this.head = null    this.count = 0    }        /**    * 尾部增加节点    */    addAtTail(item) {    if (this.count === 0) {    this.head = new Node(item)        this.count++        return this.head    }        let endNode = this.head        while (endNode.next) {    endNode = endNode.next    }        endNode.next = new Node(item)        this.count++        return item    }        /**    * 头部增加节点    */    addAtHead(item) {    if (this.head) {    const oldHead = this.head        this.head = new Node(item)    this.head.next = oldHead    } else {    this.head = new Node(item)    }        this.count++        return item    }        /**    * 指定地位增加节点    */    addAtIndex(index, item) {    if (this.isInvalidIndex(index) || !this.head) {    return -1    }        if (index === 0) {    this.addAtHead(item)        return item    }        let prev = this.head        while (index > 0) {    index--    }        const next = prev.next        const cur = new Node(item)        prev.next = cur    cur.next = next        this.count++        return item    }        /**    * 获取节点    */    get(index) {    if (this.isInvalidIndex(index) || !this.head) {    return -1    }        let cur = this.head        while (index > 0) {    cur = cur.next        index--    }        return cur    }        /**    * 删除指定节点    */    removeAtIndex(index) {    if (this.isInvalidIndex(index) || !this.head) {    return -1    }        if (index === 0) {    const oldHead = this.head    this.head = this.head.next        this.count--        return oldHead    }        let prev = this.head        while (index - 1 > 0) {    prev = prev.next        index--    }        const cur = prev.next        prev.next = cur.next        this.count--        return cur    }        /**    * 判断index是否为空，是否超出数据长度大小    */    isInvalidIndex(index) {    if (index === '' || index === null || index === undefined || index < 0 || index> this.count - 1) {      return true      }          return false      }      }          const link = new Link()          link.addAtTail('a')      link.addAtTail('b')      link.addAtTail('c')

原文链接：https://note.noxussj.top/?source=sifo