【数据结构与算法 - Swift实现】01 - 数组和字典

在学习其他更复杂的数据结构之前，我们先简单看看Swift标准库自带的数组和字典。

数组

数组是我们在开发中经常用到的，是一个有序的集合。可以通过索引来获取其中的元素。例如：

let persons = ["Lebron", "Love", "JR", "Korver"]
persons[0] // "Lebron"

从数组中取出元素所需时间为常量时间O(1)，因为数组是在一块连续的内存中保存的，索引就是他的位置，不管数组有多大，都可以直接取出来。

插入操作

最简单的是新的元素是在数组最后面插入；最坏的情况就是从数组的最前面插入。一般我们需要考虑最坏的情况，所以插入操作的时间是线程时间O(n)，n是元素的个数。可以想象一下我们在排队购买iPhone，有个流氓想要插到最前面，那么所有队伍中的人都后往后移。

另外一个影响插入时间的数组的容量。我们刚刚说到：数组是在一块连续的内存中保存的，当我们创建数组的时候，系统就会默认在内存中开一块连续空间来保存数组；如果后面发现这块内存不够用了，系统就必须在内存的另外一个位置，开辟一块更大的空间，然后把原有的元素复制到新的空间。所以，在开发中，如果我们知道数组需要存储多少个元素，可以调用array.reserveCapacity(100)告诉Swift在内存中预留出足够的空间。其实在Swift中，如果发现数组内存不够用的话，它会把数组的内存加1倍。

因为插入操作在数组中比较耗时，如果在开发中需要频繁的将新的元素插入到最前面，那么可以考虑用链表来代替数组。

字典

字典存储的是键值对，例如保存商品的库存：

let inventory = ["雪碧": 10, "可乐": 10]

// 插入新元素
inventory["薯片": 10]

字典的元素是无序的，也不能插入到指定的位置；字典中的键必须遵循Hashable。

因为是无序的，所有新元素插入到字典中所有的时间是常量时间O(1)。

完

这里简单总结了数组和字典的一些特性。我们可以利用这两个基本的数据结构来实现更复杂的数据结构。

欢迎加入我管理的Swift开发群：536353151。

下一篇文章：【数据结构与算法 - Swift实现】02 - 链表