单向链表

huan_kong

650字约2分钟

2023-11-27

介绍

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

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

类似火车的结构:

image-20231128093417262

image-20231128095456585

函数讲解

#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实现

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 = null
  #length = 0

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

    let current = this.#head
    for (let i = 0; i < index; i++) {
      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)
      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)
      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 = this.#head

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

    return -1
  }

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

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

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

    this.#length--

    return true
  }

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

  size() {
    return this.#length
  }

  toString() {
    let result = []
    let current = this.#head

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

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