乐趣区

关于前端:什么是链表

jiezi

链表

原文链接：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

退出移动版