CcbeanBlog
ccbean
2021-12-17
目录

数据结构与算法-链表

# 数据结构与算法-链表

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。

# 数组和链表

# 数组

我们先来回顾下数组的特点：

  • 存储多个元素，数组（或列表）可能是最常用的数据结构。
  • 几乎每一种编程语言都有默认实现数组结构，提供了一个便利的 [] 语法来访问数组元素。

但是数组存在一些缺点：

  • 数组的创建需要申请一段连续的内存空间即一整块内存，并且大小是固定的，当前数组不能满足容量需求时，需要扩容。 一般情况下是申请一个更大的数组，比如 2 倍，然后将原数组中的元素复制过去，再添加新的元素。
  • 在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移。尽管我们已经学过的JavaScript的Array类方法可以帮我们做这些事，但背后的原理也是这样的。

# 链表

存储多个元素，另外一个选择就是使用链表。接下来我们来看下链表。

不同于数组，链表中的元素在内存中不必是连续的空间。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或连接)组成。

链表的优点：

  • 内存空间不必是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。
  • 链表不必在创建时就确定大小，并且大小可以无限延伸下去。
  • 链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多。

链表的缺点：

  • 访问任何一个位置的元素时，需要从头开始访问。无法跳过第一个元素访问任何一个元素。那么也就无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素。
  • 虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的。

# 单向链表

单向链表类似于火车，有一个火车头，火车头会连接一个节点，节点上有乘客，并且这个节点会连接下一个节点，以此类推。

如下图所示

链表01

那么，链表的数据结构会有一个head属性指向链表的第一个节点。链表中的最后一个节点指向null；当链表中一个节点也没有的时候，head就直接指向null。

如下图所示

链表02

加上数据后

链表03

# 常见操作

  • append(element) 向链表尾部添加一个新的元素。
  • insert(position, element) 向链表的特定位置插入一个新的元素。
  • get(position) 获取对应位置的元素。
  • indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素就返回-1。
  • update(position, element) 修改某个位置的元素。
  • removeAt(position) 从链表的特定位置移除一项。
  • remove(element) 从链表中移除指定元素。
  • isEmpty() 如果链表中不包含任何元素，返回 trun，如果链表长度大于 0 则返回 false。
  • size() 返回链表包含的元素个数，与数组的 length 属性类似。
  • toString() 由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。

整体操作方法和数组类似，因为链表本身就是一种可以代替数组的结构。

# 封装

创建一个链表类，和链表中的节点类。

// 链表节点
class Node {
  constructor (element) {
    this.data = element
    this.next = null
  }
}

/**
 * 链表
 */
class LinkedList {
  constructor () {
    // head指向链表的第一个节点 初始为null
    this.head = null
    // 初始链表的长度
    this.length = 0
  }
}

接下来向LinkedList中扩展相关操作方法

# append - 尾部添加节点

向链表尾部添加一个新的节点

// 向链表尾部添加一个节点
append (element) {
  const newNode = new Node(element)

  if (this.length === 0) { // 空链表
    this.head = newNode
  } else { // 链表非空
    // 保存找到的节点 从head开始
    let currentNode = this.head

    // 遍历到最后一个节点
    while (currentNode.next) {
      currentNode = currentNode.next
    }

    // 最后一个节点 next 指向新增节点
    currentNode.next = newNode
  }

  // 链表长度加1
  this.length++
}

分析：

  1. 将传入element包装成一个Node

  2. 判断链表，链表本身为空。如这种情况下我们插入了一个15作为元素。

    链表4

  3. 链表中已经有元素，需要向最后的节点的next中添加节点。

    • 这个时候要向链表的尾部添加一个元素，首先我们需要找到这个尾部元素。
    • 我们只有第一个元素的引用，因此需要循环访问链表，直接找到最后一个项。
    • 找到最后一项后，最后一项的next为null，这时将其next指向新创建的节点即可。
    • 如再插入一个10作为元素，那么会线从head即15的节点开始查找，循环找到结尾，添加10到链尾。

    链表5

# insert - 任意位置插入节点

// 向链表的特定位置插入一个节点 返回Boolean标识添加是否成功
insert (position, element) {
  // 越界处理
  if (position < 0 || position > this.length) return false
  // 新节点
  const newNode = new Node(element)

  if (position === 0) {
    // 首位插入
    newNode.next = this.head
    this.head = newNode
  } else {
    // 0 < position <= this.length 插入
    let currentNode = this.head
    let previousNode = null
    let index = 0

    while (position > index++) {
      previousNode = currentNode // 原position -1位置节点
      currentNode = currentNode.next // 原position位置节点
    }
    // 插入新的节点到position 即 改变原节点指向
    previousNode.next = newNode
    newNode.next = currentNode
  }

  // 链表长度加1
  this.length++
  return true
}

分析：

  1. 越界处理，如果越界则返回false，即添加失败。

  2. 接着创建新节点newNode，如果是添加到首位，表示新添加的节点是head，就需要将原来的头节点作为新节点的next，然后head应该指向新节点

    链表06

  3. 如果新节点添加位置0 < position <= length，则遍历查找需要添加的节点位置，循环找到position位置的原节点currentNode以及原节点的上一个节点previousNode，将新节点的next指向下一个节点，将上一个节点的next指向新的节点。

    添加到末尾：

    链表07

    添加到中间位置：

    链表08

  4. 最后链表长度加1，再返回true添加成功

# removeAt - 位置移除节点

根据位置移除对应的节点，并返回移除节点的元素data

// 根据位置移除对应的节点 并返回被移除节点的数据
removeAt (position) {
  if (position < 0 || position >= this.length) return null

  let currentNode = this.head

  if (position === 0) {
    // 移除第一个节点
    this.head = currentNode.next
  } else {
    let previousNode = null

    let i = 0
    while (position > i++) {
      previousNode = currentNode // 原position -1位置节点
      currentNode = currentNode.next // 原position位置节点
    }
    // 将previousNode.next指向position + 1位置的Node
    previousNode.next = currentNode.next
  }
  // 链表长度减1
  this.length--
  return currentNode.element
}

分析：

  1. 越界处理，如果越界则返回null，即移除失败。 这里越界判断中的等于length也是越界的，因为下标值是从0开始的

  2. 第一个节点移除，直接让head指向第二个节点即可；第一个节点没有引用指向，就在链表中不再有效，后面会被回收掉

    链表09

  3. 移除其它节点，与插入节点操作确定position逻辑相同，遍历查找需要添加的节点位置，循环找到position位置的原节点currentNode以及原节点的上一个节点previousNode，将上一项的next指向current项的next，这样中间的项就没有引用指向它，也就不再存在于链表后，会面会被回收掉。

    移除末尾节点

    链表10

    移除中间节点

    链表11

  4. 最后链表长度减1，再返回被移除的节点数据。

# indexOf - 获取节点位置

获取节点在链表中的位置

// 获取节点在链表中的位置
indexOf (data) {
  let currentNode = this.head

  let index = 0

  while (currentNode) {
    if (currentNode.data === data) {
      // 找到节点 返回index
      return index
    }

    currentNode = currentNode.next
    i++
  }
  // 未找到 返回-1
  return -1
}

分析：

  1. 通过while循环获取节点，通过节点获取data和传入data进行对比，如果和传入data相同，表示找到，直接返回index即可。
  2. 如果没有找到，指向下一个节点，且index++
  3. 最后都没有找到，说明链表中没有对应的元素，那么返回-1即可

# remove - 根据元素删除节点

根据数据移除对应的节点，并返回节点对应的元素data

// 根据元素删除节点
remove (data) {
  const index = this.indexOf(data)
  return this.removeAt(index)
}

分析：

  1. indexOf(data) 获取元素所在位置
  2. removeAt 根据位置移除元素

# get - 位置获取元素

根据位置获取元素

// 根据位置获取元素
get (position) {
  // 越界处理
  if (position < 0 || position >= this.length) return null

  let currentNode = this.head
  let index = 0
  while (position > index++) {
    currentNode = currentNode.next
  }
  return currentNode.data
}

# update - 更新位置节点

更新链表对应位置的节点，并返回更新后的节点

// 更新节点 并返回更新后的节点
update (position, element) {
  // 越界处理
  if (position < 0 || position >= this.length) return false

  let currentNode = this.head

  let index = 0
  while (position > index++) {
    currentNode = currentNode.next
  }
  // 更新position位置的element
  currentNode.element = element

  return currentNode
}

# 其它 - isEmpty size toString

// 判断链表是否为空
isEmpty() {
  return this.length === 0
}

// 获取链表的长度
size() {
  return this.length
}

// 以字符串形式返回链表内元素节点
toString () {
  let currentNode = this.head
  let result = ''
  // 遍历所有节点
  while (currentNode) {
    result += `${currentNode.element} `

    currentNode = currentNode.next
  }

  return result
}

分析：

  1. toString()从head开始，因为获取链表的任何元素都必须从第一个节点开头，循环遍历每一个节点，并且取出其中的element，拼接成字符串。

# 完整实现

// 链表节点
class Node {
  constructor (element) {
    this.element = element
    this.next = null
  }
}

/**
 * 链表
 */
module.exports = class LinkedList {
  constructor () {
    // head指向链表的第一个节点 初始为null
    this.head = null
    // 初始链表的长度
    this.length = 0
  }

  // 向链表尾部添加一个节点
  append (element) {
    const newNode = new Node(element)

    if (this.length === 0) { // 空链表
      this.head = newNode
    } else { // 链表非空
      // 保存找到的节点 从head开始
      let currentNode = this.head

      // 遍历到最后一个节点
      while (currentNode.next) {
        currentNode = currentNode.next
      }

      // 最后一个节点 next 指向新增节点
      currentNode.next = newNode
    }

    // 链表长度加1
    this.length++
  }

  // 向链表的特定位置插入一个节点 返回Boolean标识添加是否成功
  insert (position, element) {
    // 越界处理
    if (position < 0 || position > this.length) return false
    // 新节点
    const newNode = new Node(element)

    if (position === 0) {
      // 首位插入
      newNode.next = this.head
      this.head = newNode
    } else {
      // 0 < position <= this.length 插入
      let currentNode = this.head
      let previousNode = null
      let index = 0

      while (position > index++) {
        previousNode = currentNode // 原position -1位置节点
        currentNode = currentNode.next // 原position位置节点
      }
      // 插入新的节点到position 即 改变原节点指向
      previousNode.next = newNode
      newNode.next = currentNode
    }

    // 链表长度加1
    this.length++
    return true
  }

  // 根据位置获取元素
  get (position) {
    // 越界处理
    if (position < 0 || position >= this.length) return null

    let currentNode = this.head
    let index = 0
    while (position > index++) {
      currentNode = currentNode.next
    }

    return currentNode.element
  }

  // 根据位置移除对应的节点 并返回被移除节点的数据
  removeAt (position) {
    if (position < 0 || position >= this.length) return null

    let currentNode = this.head

    if (position === 0) {
      // 移除第一个节点
      this.head = currentNode.next
    } else {
      let previousNode = null

      let i = 0
      while (position > i++) {
        previousNode = currentNode // 原position -1位置节点
        currentNode = currentNode.next // 原position位置节点
      }
      // 将previousNode.next指向position + 1位置的Node
      previousNode.next = currentNode.next
    }
    // 链表长度减1
    this.length--
    return currentNode.element
  }

  // 获取节点在链表中的位置
  indexOf (element) {
    let currentNode = this.head

    let index = 0

    while (currentNode) {
      if (currentNode.element === element) {
        // 找到节点 返回index
        return index
      }

      currentNode = currentNode.next
      index++
    }
    // 未找到 返回-1
    return -1
  }

  // 根据元素删除节点
  remove (element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }

  // 更新节点 并返回更新后的节点
  update (position, element) {
    // 越界处理
    if (position < 0 || position >= this.length) return false

    let currentNode = this.head

    let index = 0
    while (position > index++) {
      currentNode = currentNode.next
    }
    // 更新position位置的element
    currentNode.element = element

    return currentNode
  }

  // 判断链表是否为空
  isEmpty() {
    return this.length === 0
  }

  // 获取链表的长度
  size() {
    return this.length
  }

  // 以字符串形式返回链表内元素节点
  toString () {
    let currentNode = this.head
    let result = ''
    // 遍历所有节点
    while (currentNode) {
      result += `${currentNode.element} `

      currentNode = currentNode.next
    }

    return result
  }
}

测试

const LinkedList = require('../../lib/LinkedList')

const linkedList = new LinkedList()

// append
linkedList.append('15')
linkedList.append('10')
linkedList.append('5')
console.log('linkedList', linkedList)
// linkedList LinkedList {
//   head: Node {
//     data: '15',
//     next: Node {
//       data: '10',
//       next: Node {
//         data: '5',
//         next: null
//       } 
//     } 
//   },
//   length: 3
// }

// insert
console.log('insert', linkedList.insert(1, '14'))
console.log('insert', linkedList.insert(3, '9'))
console.log('insert', linkedList.insert(5, '4'))
console.log('insert', linkedList.insert(-1, '-1'))
console.log('toString', linkedList.toString())

// indexOf
console.log('indexOf', linkedList.indexOf('5'))
console.log('indexOf', linkedList.indexOf('100'))

// get
console.log('get', linkedList.get(0))
console.log('get', linkedList.get(1))

// 测试 update 方法
console.log('update', linkedList.update(0, '100'))
console.log('toString', linkedList.toString())
console.log('update', linkedList.update(1, '90'))
console.log('toString', linkedList.toString())

// removeAt
console.log('removeAt', linkedList.removeAt(1))
console.log('removeAt', linkedList.removeAt(2))
console.log('removeAt', linkedList.removeAt(3))
console.log('removeAt', linkedList.removeAt(4))
console.log('toString', linkedList.toString())

// remove
console.log('remove', linkedList.remove('5'))
console.log('remove', linkedList.remove('0'))

// 测试 isEmpty 方法
console.log('isEmpty', linkedList.isEmpty())

// 测试 size 方法
console.log('size', linkedList.size())
编辑 (opens new window)
上次更新: 2021/12/21, 17:36:40
数据结构与算法-队列
数据结构与算法-双向链表

← 数据结构与算法-双向链表→

最近更新
01
阅读精通正则表达式总结
09-29
02
项目搭建规范的配置
07-15
03
Vite的使用
07-03
更多文章>
Theme by Vdoing | Copyright © 2018-2023 Ccbeango