前端应该了解的数据结构 | 线性表


theme: smartblue

前言

小伙伴,你好!我是 嘟老板。之前发了一条沸点:程序 = 数据结构 + 算法,得到了很多小伙伴的认同,侧面凸显了 数据结构 在程序开发中的核心作用。今天,我们将重点探讨一个基础但极其重要的数据结构 —— 线性表。。

什么是线性表

定义线性表由 0 个或多个数据元素组成的有限序列。它具有两个关键特性:

  • 有限性:元素数量确定。
  • 序列性:元素按特定顺序排列。

线性表 是一种基础的数据结构,其特点是数据元素按照线性的方式进行组织。在这种结构中,头元素之后直接连接着一个元素,称为其后继;而尾元素之前直接连接着一个元素,称为其前驱。除了头尾元素之外,线性表中的每个数据元素都恰好有一个前驱和一个后继。

以下是线性表的直观表示,其中展示了元素之间的线性关系:

上图中,元素1元素2前驱,而 元素2元素1后继

为了更具体地理解线性表,我们借助现实生活中的类比:火车站窗口排队买票的队伍。在这个队伍中,每个人都按照到达的顺序排队,一次只能为一个人办理业务。这个队伍中的每个人前面只有一个人(前驱),后面也只有一个人(后继),这与线性表中元素的组织方式非常相似。

值得注意的是,并非所有的数据结构都是线性的。例如,公司的组织架构通常不是线性的,因为一个部门经理可能管理多个总监,每个总监又可能管理多个组长,这种结构更接近于树形结构。

在技术实现上,线性表可以通过多种方式存储,其中最常见的两种是 数组链表。数组是一种连续的存储结构,而链表则是一种非连续的存储结构,两者在内存中的表现和操作方式有着显著的差别。这些内容将在后续的讲解中详细展开。

线性表的抽象数据类型

线性表可以定义以下基础操作:

  • clearList():清空线性表中的所有元素。
  • getElem(i):获取线性表中第 i 个位置的元素。
  • locateElem(e):查找元素 e 在线性表中的位置,若找到则返回其下标;否则返回特定的失败标识(如 -1)。
  • insert(i, e):在线性表的第 i 个位置插入新元素 e
  • delete(i):删除线性表中第 i 个位置的元素,并返回被删除的元素。
  • length:获取线性表中元素的数量,即线性表的长度。

这些基础特性可以组合使用,以实现更高级的操作。例如两个线性表的合并、在指定位置批量删除元素后插入新元素等等。

基本类定义:

/**
 * 线性表
 */
class List {
  // 数据元素集合
  data = []
  // 线性表长度
  length = 0

constructor(data) {
this.data = data
this.length = data.length
}

// 清空线性表
clearList() {}

// 返回线性表中第 i 个位置的数据元素
getElem(i) {}

// 匹配线性表中与元素 e 相同的元素,若匹配成功,返回该元素在线性表中的位置序号;否则,返回 0。
locateElem(e) {}

// 在线性表中第 i 个位置插入元素 e
insert(i, e) {}

// 删除线性表第 i 个位置的元素
delete(i) {}
}

线性表的存储结构

线性表可以通过两种主要的存储结构实现:顺序结构链式结构

顺序结构

什么是顺序结构

线性表的顺序存储结构通过使用一组连续地址的存储单元来依次保存线性表中的每个元素。这种存储方式的特点在于其空间的连续性,每个元素都紧邻着前一个元素存储。

以下是顺序存储结构的直观表示,其中每个空格代表一个存储单元:

在编程实现中,我们通常使用数组来模拟这种结构,其中数组的下标 0 对应线性表的第一个元素。

基本类定义:

class SqList {
  // 线性表的最大容量
  maxSize
  // 存储数据元素的数组
  data = []
  // 线性表当前长度
  length = 0
  constructor(maxSize) {
    this.maxSize = maxSize
    this.data = new Array(maxSize)
    this.length = 0
  }

// 顺序存储结构的其他操作(如插入、删除等)将在这里定义
}

顺序存储结构的主要属性包括:

  • maxSize:线性表的最大存储容量,决定了线性表中最多可以存储多少个元素。
  • data:存储线性表数据元素的数组,数组的每个元素对应线性表中的一个数据项。
  • length:记录线性表当前的元素数量,即线性表的长度。

获取元素

在顺序存储结构的线性表中,读取元素 是一个直接的过程。由于数组下标与线性表位置之间的对应关系,访问特定位置的元素可以通过简单地 调整下标 来实现。

具体来说,要获取线性表中第 i 个位置的元素,我们只需访问数组中下标为 i - 1 的元素。因为数组的索引是从 0 开始的,而线性表的位置编号则是从 1 开始。因此,线性表中第 i 个位置的元素,在数组中对应的索引是 i - 1

具体实现如下:

/**
 * 返回线性表中第 i 个位置的数据元素
 * @param {number} i 线性表中指定元素的位置
 * @returns {any} 线性表中第 i 个位置的元素
 */
getElem(i) {
  // 确保请求的位置在有效范围内
  if (i < 1 || i > this.length) {
    return null;
  }
  // 返回数组中相应位置的元素
  return this.data[i - 1];
}

插入元素

在顺序存储结构的线性表中,插入元素 是指在特定位置插入一个新的数据元素。这一操作要求将插入点之后的所有元素后移以腾出空间。

以下是插入操作的详细步骤:

  1. 验证插入位置:确保要插入的位置 i 是合理的,即 1length + 1length 是当前线性表的长度)之间。如果位置不合理,抛出错误。
  2. 检查容量限制:如果线性表的当前长度已经达到数组的容量 maxSize,则需要抛出错误或动态扩展数组的容量。
  3. 移动元素:从数组的最后一个元素开始,向前遍历到插入位置 i,将每个元素后移一位以腾出插入点。
  4. 插入新元素:在位置 i 插入新元素 e
  5. 更新长度:增加线性表的长度 length

具体实现如下:

/**
 * 在线性表的第 i 个位置插入元素 e
 * @param {number} i - 要插入的位置
 * @param {object} e - 待插入的数据元素
 */
insert(i, e) {
  // 检查插入位置是否在有效范围内
  if (i < 1 || i > this.length + 1) {
    throw new Error('插入位置不合理');
  }
  // 检查是否需要扩展数组容量
  if (this.length >= this.maxSize) {
    throw new Error('超出数组容量限制');
  }
  // 从数组尾部开始向前遍历并移动元素
  for (let j = this.length; j >= i; j--) {
    this.data[j] = this.data[j - 1];
  }
  // 在位置 i 插入元素 e
  this.data[i - 1] = e;
  // 更新线性表的长度
  this.length++;
}

删除元素

在顺序存储结构的线性表中,删除元素 的操作涉及到将指定位置的元素移除,并让后续所有元素向前移动一位以填补空出的位置。

以下是删除操作的详细步骤:

  1. 检查删除位置:验证要删除的位置 i 是否在有效范围内,即 1lengthlength 是当前线性表的长度)之间。如果位置不合理,抛出错误。
  2. 保存待删除元素:取出线性表中第 i 个位置的元素,该元素将作为删除操作的返回值。
  3. 移动元素:从待删除元素的下一个位置 i + 1 开始,遍历到最后一个元素位置,将每个元素向前移动一位。
  4. 更新线性表长度:将线性表的长度 length1

具体实现如下:

/**
 * 删除线性表第 i 个位置的元素并返回被删除的元素
 * @param {number} i - 要删除的元素在线性表中的位置
 * @returns {any} 被删除的元素
 */
delete(i) {
  // 检查线性表是否为空或删除位置是否超出范围
  if (this.length === 0 || i < 1 || i > this.length) {
    throw new Error('删除位置不合理');
  }
  // 保存待删除的元素
  let e = this.data[i - 1];
  // 从待删除元素的下一个位置开始向前移动元素
  for (let j = i; j < this.length; j++) {
    this.data[j - 1] = this.data[j];
  }
  // 调整线性表长度
  this.length--;
  // 返回被删除的元素
  return e;
}

时间复杂度分析

在顺序存储的线性表中,执行 插入删除 操作的时间复杂度与目标位置密切相关。当操作定位在 表尾 时,无需调整任何其他元素,从而可以直接进行操作,此时的时间复杂度是 O(1)。然而,若操作发生在 表头,则需要将所有后续元素向前移动一位,导致时间复杂度增至 O(n)。对于表中其他位置的元素,随着目标位置沿序列向 移动,所需连续移动的元素数量也会随之增加。

如果对所有可能的插入或删除位置进行平均考量,平均所需的移动次数将是 (n + 1)/2,这为我们提供了对操作平均时间成本的估算。

综合上述分析,顺序存储的线性表中 插入删除 操作的总体时间复杂度被确定为 O(n)

关于时间复杂度的推导方法,可参考 前端应该了解的算法知识 | 如何度量算法的执行效率

链式结构

到目前为止,我们已经大致掌握了线性表的 顺序存储结构。细心的小伙伴可能已经注意到,在执行 插入删除 操作时,顺序存储结构需要逐个移动所有后续的数据元素,这一过程可能相当耗时。那么,是否存在一种更高效的解决方案呢?答案是肯定的,它就是线性表的另一种存储方式 —— 链式结构

什么是链式存储结构

链式结构使用 任意 的存储单元,是否连续都可,并通过 指针 连接元素。

顺序结构 相比,链式结构 在存储线性表时有其独特之处。在 顺序结构 中,每个数据元素仅存储其 数据信息。而在 链式结构 中,除了数据信息,每个元素还存储了指向其后继元素的地址。

存储数据的部分称为 数据域,存储后继地址的部分称为 指针域。指针域中存储的地址信息被称为 指针。一个完整的数据元素,包含数据域和指针域,称为 节点

线性表的这种链式存储方式通常被称为 链表。特别地,如果链表的每个节点只包含一个指向下一个节点的指针域,这种链表被称为 单链表

在单链表中,第一个节点的位置被称为 头指针,它是链表的起始点。链表的遍历从 头指针 开始,并通过节点的后继指针逐个访问后续节点,直至链表的末尾。链表的最后一个节点,也就是尾部节点,其后继指针通常设置为 null,表示没有后续节点。

基本类定义:

// 链表节点类
class Node {
  constructor(data) {
    this.data = data;  // 数据域
    this.next = null;   // 指针域,指向下一个节点
  }
}

// 单链表类
class SLinkList {
constructor() {
this.head = new Node(null); // 头节点,其next指针指向第一个数据节点
this.length = 0; // 链表长度
}

// 链表的其他操作(如添加、删除等)将在这里定义
}

在单链表的实现中,每个节点由 Node 类创建,包含数据域和指针域。链表类 SLinkList 包含一个 头节点,该节点的指针域指向链表的第一个数据节点,数据域通常不存储数据,仅作为链表的起始标识。

以下是链表结构示意图:

获取元素

如何获取单链表中第 i 个位置的元素?

顺序结构 直接访问特定位置的元素不同,在单链表中,由于元素不是连续存储的,我们无法直接定位到第 i 个元素。我们必须从链表的 头结点 开始,逐个节点地进行搜索。

获取元素的步骤如下:

  1. 初始化节点 p 指向链表的 头结点,并设置索引变量 j 为 1。
  2. j 小于 i 时,依次将 p 移动到下一个节点,并将 j 增加 1。
  3. 如果遍历完成后 p 未匹配到任何节点,这意味着所查找的元素不存在。
  4. 如果匹配成功,则返回节点 p 存储的数据。

具体实现如下:

/**
   * 返回单链表中第 i 个位置的数据元素
   * @param {number} i 指定元素的位置
   */
  getElem(i) {
    // 获取头结点
    const p = this.head
    // 元素从第 1 个位置开始查找
    let j = 1
    // 遍历位置在 i 之前的节点
    while(j < i) {
      p = p.next
      j++
    }
    // 若第 i 个位置无节点 返回 空
    if (!p || j > i) return null
    // 匹配成功,返回节点 p 的数据
    return p.data
  }

查找过程体现了单链表在元素访问方面的主要特点:缺乏直接的索引,必须进行线性搜索,在效率上不如顺序存储结构。

插入元素

在单链表中插入元素的过程相对简单,尤其是当我们想要在特定位置插入一个新节点时。由于单链表通过指针连接各个节点,我们不需要像在顺序结构中那样移动其他元素。插入操作的关键在于调整指针,而非移动节点本身。

假设我们要将一个新节点 s插入到单链表中第 i 个节点和第 i+1 个节点之间。

以下是插入操作的详细步骤:

  1. 定位到单链表的第 i 个节点,记为 p
  2. 如果节点 p 不存在,表示链表中没有第 i 个节点,此时无法执行插入。
  3. 如果节点 p 存在,创建一个新节点 s,其数据域为 e
  4. 将新节点 s后继指针 设置为节点 p 原来指向的节点,即 s.next = p.next
  5. 更新节点 p后继指针 以指向新节点 s,即 p.next = s
  6. 返回成功。

以下为插入操作的示意图:

具体实现如下:

/**
   * 在链表位置 i 插入数据 e
   * @param {object} e 需要插入的节点数据
   * @param {number} i 要插入的链表位置
   */
  insert(e, i) {
    // 获取链表第 i 个节点
    const p = this.getElem(i);
    // 若不存在节点 p,返回 false 或报错
    if (!p) return false
    // 生成数据为 e 的节点 s
    const s = new Node(e)
    // 将 s.next 指针指向 i+1 位置的节点,将 p.next 指向 s
    s.next = p.next
    p.next = s
    // 链表长度 +1
    this.length++
    return true
  }

删除元素

在单链表中删除特定节点的操作涉及重新配置指针,而非移动节点本身。

假如我们要删除第 i 个节点,关键在于将其前一个节点的指针直接指向第 i+1 个节点,从而绕过要删除的节点。

以下是删除操作的具体步骤:

  1. 定位到单链表中第 i 个节点 s 的前一个节点,即第 i - 1 个节点,记为 p
  2. 如果节点 p 不存在,表明链表中没有第 i - 1 个节点,无法执行删除操作。
  3. 如果节点 p 存在,获取 p 的后继节点,即要删除的节点 q,其中 qp.next 所指向的节点。
  4. 更新 p 的后继指针,使其指向 q 的后继节点,即 p.next = q.next。这样,节点 q 就被从链表中移除了。
  5. 返回被删除节点 q 的数据。

以下为删除操作的示意图:

具体实现如下:

/**
   * 删除链表中第 i 个节点
   * @param {number} i 要删除的节点位置
   */
  delete(i) {
    // 获取位置 i 前面的节点 p
    const p = this.getElem(i - 1)
    // 若不存在节点 p,返回 false 或报错
    if (!p) return false
    // 要删除的节点 q
    const q = p.next
    p.next = q.next
return q.data

}

时间复杂度分析

在单链表中,进行 插入删除 操作之前,通常需要先执行一个 查询 操作以定位目标节点。由于查询操作的时间复杂度为 O(n),这自然也决定了 插入删除 操作的时间复杂度同样为 O(n)。从这个角度看,链式结构 在处理单个元素时似乎并没有展现出明显的优势。

然而,在实际应用场景中,经常会遇到需要批量处理的需求。例如,若需在线性表的第 i 个位置插入10个元素,使用线性结构将不得不执行10次移动操作。而 链式结构 则不然,在确定了第 i 个位置的节点之后,我们无需重复查找过程,仅需进行简单的指针赋值操作即可完成插入,这时的时间复杂度降低到了 O(1)

两种存储结构对比

我们已经详细探讨了线性表的 顺序存储结构链式存储结构 以及它们的一些基本操作。现在,我们简要的对比这两种存储结构。

特性 顺序存储结构 链式存储结构
优势 - 查找元素速度快,时间复杂度为 O(1)
- 不需要额外的存储空间来维护节点间的关联。
- 批量操作节点时效率高,尽管单个节点的操作时间复杂度为 O(n),但在进行批量操作时,除首次定位外,其余操作的时间复杂度为 O(1)
- 不需预先定义存储空间大小,理论上受内存限制,节点数量可以无限扩展。
劣势 - 元素的 插入删除 操作需要移动其他元素,时间复杂度为 O(n),这对单个操作和批量操作均适用。
- 需要预先分配存储空间,这可能导致空间的浪费或不足。
- 查找元素速度相对较慢,时间复杂度为 O(n)
- 每个节点需要额外的存储空间来存储指向下一个节点的指针。

通过上表,我们可以看到,顺序存储结构在元素查找方面具有优势,但在执行插入和删除操作时效率较低。而链式存储结构虽然查找效率较低,但在批量操作和动态内存管理方面更加灵活高效。

结语

本文重点介绍了一个基础而重要的数据结构 —— 线性表,并详细探讨了它的两种实现方式:线性存储结构链式存储结构。通过辅助的代码示例,旨在帮助小伙伴快速掌握不同存储结构的特点及差异。

如果您对文章内容有任何疑问或想深入讨论,欢迎评论区留下您的问题和见解。

技术简而不凡,创新生生不息。我是 嘟老板,咱们下期再会。


往期推荐


这是一个从 https://juejin.cn/post/7368662916152311847 下的原始话题分离的讨论话题