1. 數(shù)組
Array
一個數(shù)組有序的組織元素，一個接一個放在內(nèi)存中。
每一個數(shù)組都有一個從0開始的索引值index。
reference
優(yōu)點：
- 快速查找椭坚。無論數(shù)組的長度，檢索有index值的元素都是耗時O(1)搏色。
- 快速appends藕溅。在數(shù)組尾部添加一個新元素耗時O(1)。
缺點
- 固定大小继榆。在使用數(shù)組之前你需要先定義數(shù)組大薪肀怼（除非你使用動態(tài)數(shù)組）。
- inserts and deletes耗時略吨。你不得不遍歷一遍數(shù)組來插入或者刪除元素集币，最多耗時O(n)。
2. 動態(tài)數(shù)組
Other names:
array list, growable array, resizable array, mutable array
Dynamic Array
動態(tài)數(shù)組相對于數(shù)組有了一個大的提升：自動調(diào)整大小翠忠。
數(shù)組的一個限制是固定大小鞠苟，意味著你需要提前定義數(shù)組元素的數(shù)量。
動態(tài)數(shù)組可以隨著你增加元素而擴大秽之。所以你無需提前決定數(shù)組大小当娱。
reference
優(yōu)點：
- 快速查找。同數(shù)組考榨。
- 大小可變跨细。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
優(yōu)點：
- 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
