单向链表

huan_kong

650字约2分钟

2023-11-27

介绍

优点: 无需确定长度, 可以无限延伸, 而且在插入和删除数据时会比数组效率高很多

缺点: 读取时没有数组快, 需要从头一个一个访问, 直到找到对应的元素

类似火车的结构:

函数讲解

#getNode

这是我写的一个内部方法, 通过给定的索引, 找到 node 后返回, 如果越界了就跑出一个 RangeError 的错误

append

可能遇到的情况:

链表为空, 新添加的数据需要为头部
链表不为空, 取出最后一位设置插入节点为上一位的 next

insert

可能遇到的情况:

索引为0, 取出当前的头部, 把头部设置为当前节点的尾部, 然后把头部替换为当前的新节点
索引不为0, 取出上个节点 ( P ) , 还有当前节点 ( N ) , 因为需要插入到索引不为0的位置所以把这个当前位置的节点当做下个节点 ( N ) , 把上个节点 ( P ) 的下一个节点改为插入节点 ( I ) , 把插入节点 ( I ) 的下一个节点改为当前节点 ( N )

get

直接调用 #getNode 函数获取节点然后再调用 getValue 方法即可

indexOf

直接从 0 开始循环, 然后结束是到链表长度, 如果相等就返回当前的索引值, 如果循环结束还没找到那就返回 -1

update

直接取出传入的索引对应的节点, 然后调用 setValue 方法即可

remove

直接通过 indexOf 获取当前值的索引值, 判断是否为 -1 如果是那就返回 false 如果不为 -1 那么就调用 this.removeAt 方法, 把 indexOf 获得的索引值传给他

removeAt

可能遇到的情况:

如果索引是0, 那么就让头部等于头部的下一位
如果索引不是0, 那么找到索引值的上一位 ( A ) , 然后让上一位 ( A ) 的下一位变成上一位 ( A ) 的下一位 ( A.getNext() ) 的下一位( A.getNext().getNext() ) ( 可以不用重新去从头开始获取进度, 效率更高 )

toString

可能遇到的问题:

Q: 这里为什么判断 current 为什么是 真

A: 因为刚开始为 this.#head 但是到后面如果取到了最后一位那 current 就是 null 了, null 上没有 getNext 方法

    let current = this.#head
    while (current) {
      current = current.getNext()
    }

TS实现

namespace 单向链表 {
  class Node {
    #value: any
    #next: Node | null

    constructor(value: any, next: Node | null = null) {
      this.#value = value
      this.#next = next
    }

    setValue(value: any) {
      return (this.#value = value)
    }

    getValue() {
      return structuredClone(this.#value)
    }

    setNext(next: Node | null = null) {
      return (this.#next = next)
    }

    getNext() {
      return this.#next
    }
  }

  class LinkedList {
    #head: Node
    #length = 0

    #getNode(index: number) {
      // 越界判断
      if (index < 0 || index >= this.#length) {
        throw new RangeError(`Index ${index} is out of bounds!`)
      }

      let current: Node | null = this.#head
      for (let i = 0; i < index; i++) {
        if (current === null) return current
        current = current.getNext()
      }

      return current
    }

    append(value: any) {
      const newNode = new Node(value)

      if (!this.#head) {
        this.#head = newNode
      } else {
        const current = this.#getNode(this.#length - 1)
        if (current === null) return current
        current.setNext(newNode)
      }

      this.#length++

      return true
    }

    insert(index: number, value: any) {
      const newNode = new Node(value)

      if (index === 0) {
        newNode.setNext(this.#head)
        this.#head = newNode
      } else {
        const prev = this.#getNode(index - 1)
        if (prev === null) return prev
        const next = prev.getNext()
        prev.setNext(newNode)
        newNode.setNext(next)
      }

      this.#length++

      return true
    }

    get(index: number) {
      return this.#getNode(index)?.getValue()
    }

    indexOf(value: any) {
      let current: Node | null = this.#head

      for (let i = 0; i < this.#length; i++) {
        if (current === null) return current
        if (current.getValue() === value) return i
        current = current.getNext()
      }

      return -1
    }

    update(index: number, value: any) {
      return this.#getNode(index)?.setValue(value)
    }

    remove(value: any) {
      let index = this.indexOf(value)
      if (index === -1 || index === null) return false
      return this.removeAt(index)
    }

    removeAt(index: number) {
      if (index === 0) {
        if (this.#length >= 1) {
          const next = this.#head.getNext()
          if (next === null) return next
          this.#head = next
        } else {
          throw new RangeError(`Index ${index} is out of bounds!`)
        }
      } else {
        const prev = this.#getNode(index - 1)
        if (prev === null) return prev
        prev.setNext(prev.getNext()?.getNext())
      }

      this.#length--

      return true
    }

    isEmpty() {
      return this.#length === 0
    }

    size() {
      return this.#length
    }

    toString() {
      let result: any[] = []
      let current: Node | null = this.#head

      while (current) {
        result.push(current.getValue())
        current = current.getNext()
      }

      return result.join(' -> ')
    }
  }
}