My Muri Life

切换主题

本页目录

单向链表 ​

本篇来手动实现JavaScript中没有的数据结构：单向链表。

定义节点 ​

首先定义单向链表节点结构：

JavaScript
class ListNode {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

通过值获取下标 ​

JavaScript
class LinkedList {
  constructor() {
    this.head = null
    this.len = 0  // 统计链表节点数
  }
  size() {
    return this.len
  }

  getIdx(val) {
    let cur = this.head
    for (let idx = 0; idx < this.len && cur != null; idx++) {
      if (val === cur.val) return idx
      cur = cur.next
    }
  }
}

通过下标获取值 ​

JavaScript
class LinkedList {
  // 其它逻辑代码...
  getAt(idx) {  // 获取idx处的节点
    if (idx >= 0 && idx < this.len) {
      let cur = this.head
      for (let i = 0; i < idx && cur != null; i++) {
        cur = cur.next
      }
      return cur
    }
    return undefined
  }
  getValAt(idx) {
    const cur = this.getAt(idx)
    return cur === undefined ? -1 : cur.val
  }
}

任意位置添加节点 ​

JavaScript
class LinkedList {
  // 其它逻辑代码...
  addAt(val, idx) {
    if (idx >= 0 && idx < this.len) {
      const node = new ListNode(val)
      if (idx === 0) {
        const cur = this.head
        node.next = cur
        this.head = node
      } else {
        const prev = this.getAt(idx - 1)
        const cur = prev.next
        node.next = cur
        prev.next = node
      }
      this.len++
      return true
    }
    return false
  }
}

任意位置移除节点 ​

JavaScript
class LinkedList {
  // 其它逻辑代码...
  removeAt(idx) {
    if (idx >= 0 && idx < this.len) {
      let cur = this.head
      if (idx === 0) {
        this.head = cur.next
      } else {
        const prev = this.getAt(idx - 1)
        cur = prev.next
        prev.next = cur.next
      }
      this.len--
      return cur.val
    }
    return undefined
  }
}

通过值移除节点 ​

JavaScript
class LinkedList {
  // 其它逻辑代码...
  remove(val) {
    const idx = this.getIdx(val)
    return this.removeAt(idx)
  }
}

整表表字符串化 ​

JavaScript
class LinkedList {
  // 其它逻辑代码...
  toString() {
    if (this.head == null) return ''
    let valStr = `${this.head.val}`
    let cur = this.head
    for (let i = 1; i < this.len && cur != null; i++) {
      valStr = `${valStr},${cur.val}`
      cur = cur.next
    }
    return valStr
  }
}

完整代码 ​

查看
JavaScript
class LinkedList {
  constructor() {
    this.head = null
    this.len = 0  // 统计链表节点数
  }
  size() {
    return this.len
  }
  // 获取val的下标idx
  getIdx(val) {
    let cur = this.head
    for (let idx = 0; idx < this.len && cur != null; idx++) {
      if (val === cur.val) return idx
      cur = cur.next
    }
  }
  // 获取idx处的节点
  getAt(idx) {
    if (idx >= 0 && idx < this.len) {
      let cur = this.head
      for (let i = 0; i < idx && cur != null; i++) {
        cur = cur.next
      }
      return cur
    }
    return undefined
  }
  // 获取idx处的节点值
  getValAt(idx) {
    const cur = this.getAt(idx)
    return cur === undefined ? -1 : cur.val
  }
  // 添加节点
  addAt(val, idx) {
    if (idx >= 0 && idx < this.len) {
      const node = new ListNode(val)
      if (idx === 0) {
        const cur = this.head
        node.next = cur
        this.head = node
      } else {
        const prev = this.getAt(idx - 1)
        const cur = prev.next
        node.next = cur
        prev.next = node
      }
      this.len++
      return true
    }
    return false
  }
  // 移除idx处节点
  removeAt(idx) {
    if (idx >= 0 && idx < this.len) {
      let cur = this.head
      if (idx === 0) {
        this.head = cur.next
      } else {
        const prev = this.getAt(idx - 1)
        cur = prev.next
        prev.next = cur.next
      }
      this.len--
      return cur.val
    }
    return undefined
  }
  // 移除节点--值
  remove(val) {
    const idx = this.getIdx(val)
    return this.removeAt(idx)
  }
  // 字符串化
  toString() {
    if (this.head == null) return ''
    let valStr = `${this.head.val}`
    let cur = this.head
    for (let i = 1; i < this.len && cur != null; i++) {
      valStr = `${valStr},${cur.val}`
      cur = cur.next
    }
    return valStr
  }
}

数据结构应用 ​

leetcode
  1. 707. 设计链表