1. 数组
Array
一个数组有序的组织元素，一个接一个放在内存中。
每一个数组都有一个从0开始的索引值index。
reference
优点：
- 快速查找。无论数组的长度，检索有index值的元素都是耗时O(1)。
- 快速appends。在数组尾部添加一个新元素耗时O(1)。
缺点
- 固定大小。在使用数组之前你需要先定义数组大小（除非你使用动态数组）。
- inserts and deletes耗时。你不得不遍历一遍数组来插入或者删除元素，最多耗时O(n)。
2. 动态数组
Other names:
array list, growable array, resizable array, mutable array
Dynamic Array
动态数组相对于数组有了一个大的提升：自动调整大小。
数组的一个限制是固定大小，意味着你需要提前定义数组元素的数量。
动态数组可以随着你增加元素而扩大。所以你无需提前决定数组大小。
reference
优点：
- 快速查找。同数组。
- 大小可变。You can add as many items as you want, and the dynamic array will expand to hold them.
Weaknesses:
- Slow worst-case appends. Usually, adding a new element at the end of the dynamic array takes O(1) time. But if the dynamic array doesn't have any room for the new item, it'll need to expand, which takes O(n) time.
- Costly inserts and deletes. Just like arrays, elements are stored adjacent to each other. So adding or removing an item in the middle of the array requires "scooting over" other elements, which takes O(n) time.
2. 链表
Linked List
链表顺序地组织元素，每一个元素存储下一个元素的指针。
链表像一连串纸夹一样连在一起。它可以很快在顶部或底部再加一个纸夹。 It's even quick to insert one in the middle—just disconnect the chain at the middle link, add the new paperclip, then reconnect the other half.
An item in a linked list is called a node. The first node is called the head. The last node is called the tail.
Linked List
优点：
- Fast operations on the ends. Adding elements at either end of a linked list is O(1). Removing the first element is also O(1).
- Flexible size.There's no need to specify how many elements you're going to store ahead of time. You can keep adding elements as long as there's enough space on the machine.
缺点：
-
Costly lookups. To access or edit an item in a linked list, you have to take O(i) time to walk from the head of the list to the ith item.
参考文章：Data Structures Reference
网友评论