通过这篇文章了解你每天使用的数据结构

👋 你好,让我们从一些重要的背景开始。让我问你几个问题:
✅ 你在智能手机上听音乐吗?
✅ 你在手机上保存联系人列表吗?
✅ 你在比赛中见过排行榜吗?

如果你对这些问题中的任何一个的回答是肯定的,那么几乎可以肯定你已经使用过数组,而你甚至不知道它!😃 数组是非常强大的数据结构,用于存储元素列表。它们有无穷无尽的应用,在计算机科学领域非常重要。

在本文中,你将了解数组的优缺点、结构、操作和用例。

我们开始吧! 👍

🔎 深入了解基本的数组结构

要了解它们的工作原理,将计算机的内存可视化为网格非常有帮助,如下所示。每条信息都存储在构成网格的其中一个小元素(正方形)中。

uxNDqnrhHuS197WjrTeak8WQq2QZKAJD5xp4

数组利用这种“网格”结构在相邻的内存位置存储相关信息的列表,以保证极高效率地找到这些值。🔳🔳🔳🔳

你可以将数组视为

HjKZtf6JKxcrH8t51iRrId-4lTqjOlGtICip

它们的元素在内存中彼此相邻。如果你需要访问其中多个数组,该过程会得到极大的优化,因为你的计算机已经知道该值的位置。

很棒,对吧? 让我们来了解一下这在幕后是如何运行的!😃

📚 归类

数组被归类为同构数据结构,因为它们存储相同类型的元素

它们可以存储数字、字符串、布尔值(真和假)、字符、对象等。但是一旦定义了数组将存储的值的类型,它的所有元素都必须是相同的类型。你不能“混合”不同类型的数据。

sbk9-CGxQ5VKddqpz9S12GxpR26I8f8e0hj6
oS1i6uyY71HPvrPCVEqEVDpscFgyeUCAwlPN

👀 读取值——魔法开始啦

数组的惊人力量来自于它们访问值的效率。这是由于其网格状结构而实现的。让我们更详细地了解一下。🔍

当你创建一个数组,你:
- 将它赋值给一个变量 👈
- 定义它存储元素的类型 🎈
- 定义它的大小(最多有多少个元素)📚

xzGLFN8ymKFdxyZWHk4YInJ6cyQQHxUJiJQX

💡 注意你分配给该变量的名称非常重要,因为稍后你将在代码中使用它来访问值和修改数组。

但是你怎么能告诉计算机你想访问哪个特定的值呢?这就是索引发挥重要作用的地方!

1️⃣ 索引

通过索引来读取数组中的某个值。这是一个数字,指的是存储值的位置。

正如你在下图中所看到的,数组中的第一个元素的索引是 0。当你向右移动时,内存中每个空间的索引都会增加 1。

TuWNHRYkAgpBEjuszG9DElXUIAf8Osw2z--7

💡 注意:我知道从 0 而不是 1 开始计数,起初看起来很奇怪,但这被称为基于零的编号。这在计算机科学中很常见。

读取一个元素的通用语法是<ArrayVariable>[<index>]

例如
如果你的数组存储在变量 myArray 中,并且你想访问第一个元素(在索引 0 处),那么你将使用 myArray[0]

Yu9nSlzmHkZV4e7f7sulFIamSwWONw4wNcpg

2️⃣ 内存

现在你知道如何读取值了,让我们看看数组是如何存储在计算机内存中的。当你定义数组的大小时,从那一刻起,内存中的所有空间都将被“保留”以供将来可能要插入的值使用。

💡 注意如果你没有用值填充数组,则该空间将被保留并为空,直到你填充数组为止。

例如
假设你定义了一个大小为 5 的数组,但只插入了一个值,所有剩余的空间都将是空的并被“保留”在内存中,等待未来的分配。

7Hoys8sq0RuDF4-Rgr4WRD4RrImGhtQmzR9P

这是关键,数组在访问值方面非常有效。因为所有元素都存储在内存中的连续空间中,这样,计算机就知道在哪里可以找到你请求的信息。

但是......它有一个缺点😞,因为这对内存来说不是高效的。你正在为将来可能不会发生的操作保留内存。这就是为什么在你事先知道要存储多少个元素的情况下,推荐使用数组的原因。

🔧 幕后操作

现在你知道什么是数组,什么时候使用它们,以及它们如何存储元素,我们将深入研究关于数组的操作,如插入和删除元素。

1️⃣ 插入元素

假设我们有一个大小为 6 的数组,但仍有一个空白空间。我们想在数组的开头(索引  0)插入一个元素 “e”,但是这个位置已经被元素 “a” 占据了。我们应该怎么做?

JX8sviJCpwXkWT6mZ4fDIwzSNFDUZ0C8LfrP

要在数组中插入元素,我们将位于插入点右侧的所有元素向右移动一个索引。元素 “a” 现在将位于索引 1,元素 “b” 将位于索引 2,依此类推……

8KFz74m1v5dPBzXGr5IXAvt3a5XFbzL78gVs

💡 注意你将需要创建一个变量来跟踪包含元素的最后一个索引。在上图中,数组在插入之前被填充到索引 4。这样,你可以确定数组是否已满,以及应该使用什么索引在末尾插入元素。

这样操作之后,我们就成功插入元素啦。👏

VqmOSyTnIvPWbkw9p1PIhenPthaxd3bHxzvS

⚠️ 等等如果数组是满的呢

如果数组已满,并且你尝试插入一个元素,会发生什么? 😱

IlI473xQSRYYCMjlcF0YMSOs-Kca2hqqupGk

在这种情况下,你需要创建一个新的更大的数组,并手动将所有元素复制到这个新数组中。此操作非常麻烦,而且非常耗时。 想象一下,如果你有一个包含数百万个元素的数组会发生什么?这可能需要很长时间才能完成。⏳

P2q2OaohnsEPDa3KMu3e6eOJaPpw-bpufH95

💡 注意当插入元素非常快时,此规则的唯一例外是,当你在数组末尾(位于最后一个元素右侧的索引处)插入一个元素,并且仍有可用空间时。这是在恒定时间 O(1) 内完成的。

2️⃣ 删除元素

现在假设你要从数组中删除一个元素。

yG5HNXTX7Xj7aXAstjEMU2VNWHkEZXtG9q5z

为了保持随机访问的效率(能够极快地通过索引访问数组),元素必须存储在连续的内存空间中。你不能只是删除元素,并将该空间留空。

bd9KRk22FyVVrW3RJEKvCd8y-VAJQodeABOD

你应该将要删除的元素之后的元素向左移动一个索引。

G13PaxPTyIQRCBJdh2Ioup-4jM-qlDMnTVd7

最后,你会得到这个数组👇。如你所见,“b” 已被成功删除。

85yhQ9XK19hJ2paBhkb9Cf0-8v52DO0igncc

💡 注意由于你需要创建一个变量来跟踪包含元素的最后一个索引(在上图中,是索引 3),你可以使用索引直接删除该元素。

3️⃣ 查找一个元素

你可以通过三种方式在数组中查找一个元素:

  • 如果你知道元素的位置就使用索引。
  • 如果你不知道元素的位置以及数据储存在哪里你可以使用算法来优化搜索,例如二分查找。
  • 如果你不知道元素的位置以及数据储存在哪里你需要搜索数组中的每个元素,并检查当前元素是否是你要查找的(请参见下面的图表序列)。
hlrl4kdBl3eM8cT7DXJX7rItWeHzTvrretfG
nFz0jZQu4dtAqv4fauEE-7zVqxtGlKVVfKew
hxcwNp-VfOem0psPkl26HCLrILCR1mlrdpku
dEd3ArmSERT63fk95KSlKwwCqdwjvUBAOQen

👋 总结

  • 数组是非常强大的数据结构,可以存储相同类型的元素。元素的类型和数组的大小是在创建时确定和定义的。
  • 内存在数组创建后立即分配的,在你分配值之前它是空的。
  • 它们的元素位于内存中的连续位置,因此可以使用索引非常有效地访问它们(随机访问,O(1) = 常数时间)。
  • 索引是从 0 开始,不像我们习惯的从 1 开始。
  • 在数组的开头或中间插入元素涉及向右移动元素。如果数组已满,则创建一个新的更大的数组(效率不高)。在数组末尾插入非常高效,恒定时间 O(1)。
  • 从数组的开头或中间删除元素涉及将所有元素向左移动,以避免在内存中留下空白空间。这保证了元素存储在内存中的连续空间中。在数组末尾删除元素的效率非常高,因为你只删除最后一个元素。
  • 要查找元素,你需要检查整个数组,直到找到它为止。如果对数据进行排序,则可以使用二分查找等算法来优化流程。
总结昨天的经验,努力过好今天,对明天充满希望。最重要的是不要停止思考。”

阿尔伯特·爱因斯坦

👋 谢谢你

我希望你喜欢我的文章。❤️
Twitter 关注我,阅读更多文章。😃

原文:Data Structures 101: Arrays — A Visual Introduction for Beginners,作者:Estefania Cassingena Navone