什么是线性数据结构（线性数据详解）

我为什么要在乎？

我们每天都在编程中使用这些数据结构。

即使您已经熟悉它们，偶尔回顾一下它们也会很有帮助。

在 5 分钟或更短时间内：

正如我们在介绍中所说，如果元素形成一个序列，则数据结构是“线性的”。

这意味着数据结构有一个第一个元素和最后一个元素，每个元素都连接到它的前一个元素和下一个元素。

• “数组”是一种线性数据结构；这些项目是按顺序存储的。
• “图”不是线性数据结构；任何节点都可以链接到图中的任何其他节点——没有固定的“顺序”。

（如果您不熟悉图表，请不要担心 – 即将发布的时事通讯会详细探讨它们）。

让我们来看看一些常见的线性数据结构……

数组

如果你做过任何编程，你几乎肯定熟悉数组的概念。

数组就像一个书柜；这些项目彼此相邻存储，但我们可以跳转到我们喜欢阅读的任何项目。

数组中的项目有一个“索引”，允许我们直接引用它们。

跳转到我们喜欢读取其值的任何项目的能力称为“随机访问”，这是数组的巨大优势。

我们认为这是理所当然的，但这不是许多其他“线性数据结构”所具有的属性，正如您将在下面看到的那样。

当我们分配一个数组时，我们必须预先确定我们需要多少空间。

如果我们填充我们的数组，我们必须停止并分配更多空间。这意味着虽然正常插入到数组中非常快，但有时我们必须暂停一小段时间以使数组更大 – 这需要一些时间。

链表

链表是一种数据结构，其中每个项目都指向下一个项目。我们不能像使用数组那样直接跳转到任何元素。相反，我们必须依次访问它们：

链表很有用，因为与数组不同，我们不需要预先决定需要多少空间。如果我们需要添加一个新项目，我们只需将其添加到末尾即可。

这意味着添加第 200 个项目与添加第 2 个项目的成本相同。这种可预测的性能是链表的一个优势。

通过简单地更改一些“下一个”指针，从链表中间添加或删除项目也很容易。

以下是我们如何从链接列表中删除项目：

这在数组中会更难做，因为我们必须移动所有剩余的项目来考虑新的或删除的项目。

链表的一种变体是“双向链表”，其中每个元素不仅指向下一个元素，还指向前一个元素。

这意味着我们可以按任意顺序遍历数据结构，但仍然具有链表的优点。

队列

队列是“先进先出”(FIFO) 数据结构。这意味着项目的读取顺序与插入的顺序相同。

这就像商店里的队列一样，第一个加入队列的人是第一个被服务的人。

打印机队列是使用这种数据结构的一个很好的例子。打印机将按照项目的排队顺序打印项目。如果您最后将文档发送到打印机，它将是最后一个要打印的东西。

队列也可用作“缓冲区”。

假设我们有两个独立的系统，一个读取消息，一个处理消息。我们不希望读取消息的系统必须等待每条消息都被处理后才能侦听另一条消息。

在它们之间放置一个队列可以让我们“分离”这些系统。读取过程可以继续将项目添加到队列中，在处理方将项目从队列中拉出并最终处理它们的情况下是安全的 – 无需等待。

堆栈

堆栈是一种“后进先出”的数据结构；要添加的最后一项是要读取的第一项。

你可以把它想象成一堆盘子，最后加入的盘子是我们要再次取出的第一个盘子：

例如，您可以使用堆栈来实现“撤消”功能。用户执行的最后一项任务是当他们单击“撤消”按钮时要撤消的第一个任务。

我们每天在运行代码时看到的“调用堆栈”也是堆栈的一个很好的例子，但这是未来时事通讯的主题！