準備弄一個算法面試題系列。列舉下面試中常問的一些問題。
一、鏈表和數組的區別是什麼？插入和查詢的時間複雜度分別是多少？
1、從邏輯結構上來說，
這兩種數據結構都屬於線性表。
線性表，就是所有數據都排列在只有一個維度的“線”上，就像羊肉串一樣，把數據串成一串。對其中任意一個節點來說，除了頭尾，只有一個前趨，也只有一個後繼。
2、在內存中，
數組佔用的是一塊連續的內存區，而鏈表在內存中，是分散的。
數組，與生俱來具有“線性”的成分。
而鏈表比數組多了一個“串起來”的額外操作，這個操作就是加了個指向下個節點的指針。
數組在物理內存上是連續存儲的，硬件上支持“隨機訪問”，也就是你訪問一個a[3]的元素與訪問一個a[10000]，使用數組下標訪問時，這兩個元素的時間消耗是一樣的。
但是鏈表也沒有下標的概念，只能通過頭節點指針，從每一個節點，依次往下找，因為下個節點的位置信息只能通過上個節點知道（這裡只考慮單向鏈表），所以訪鏈表中的List(3)與List(10000)，時間就不一樣了，訪問List(3)，只要通過前兩個節點，但要想訪問List(10000)，不得不通過前面的9999個節點。
數組是一下子就跳到了a[10000]，無需逐個訪問a[10000]之前的這些個元素。所以對於訪問，數組和鏈表時間複雜度分別是O(1)與O(n)，方式一種是“隨機訪問”，一種是“順序訪問”。
3、插入：
數組在內存中是連續存儲的，要想在某個節點之前增加，必須要把此節點後的元素依次後移。
鏈表只需要改變節點中的“指針”，就可以。自身在內存中所佔據的位置不變，只是這個節點所佔據的這塊內存中數據（指針）改變了，
比如 A->B->C 變成A-A2->B->C。只是A的指針本來指向B，變成指向A2，然後A2的指針指向B，就可以。
數組插入或刪除元素的時間複雜度O(n)，鏈表的時間複雜度O(1)。
4、操作系統內存預讀：
內存管理會將連續的存儲空間提前讀入緩存，所以數組往往會被都讀入到緩存中，而鏈表由於在內存中分佈是分散的，往往不會都讀入到緩存中，這樣本來訪問效率就低，這樣效率反而更低了。
在實際中，因為鏈表帶來的動態擴容的便利性，在做為算法的容器方面，用的更普遍一點。
5、總結：
數組：
在內存中，數組是一塊連續的區域。
數組需要預留空間，在使用前要先申請佔內存的大小，可能會浪費內存空間。
隨機讀取效率很高。因為數組是連續的，知道每一個數據的內存地址，可以直接找到給地址的數據。
不利於擴展，數組定義的空間不夠時要重新定義數組。
鏈表：
內存中可以存在任何地方，不要求連續。
每一個數據都保存了下一個數據的內存地址。
增加數據和刪除數據很容易。
查找數據時效率低。
不指定大小，擴展方便。鏈表大小不用定義，數據隨意增刪。
6、優缺點對比
數組的優點
隨機訪問性強
查找速度快
數組的缺點
插入和刪除效率低
可能浪費內存
內存空間要求高，必須有足夠的連續內存空間。
數組大小固定，不能動態拓展
鏈表的優點
插入刪除速度快
內存利用率高，不會浪費內存
大小沒有固定，拓展很靈活。
學習很辛苦也很幸福，最後來張美圖。為了讓大家好好學習，我容易嗎。。。。。
