Java中鏈表和數組如何學

更新時間：2019-12-16 16:33:42 來源：動力節點瀏覽2667次

　　數組是有下標索引和data兩部分組成

　　鏈表是有data和指向下一個數據的指針地址兩部分組成

　　綜述：數組是線性結構，可以直接索引，即要去第i個元素，a[i]即可。鏈表也是線性結構，要取第i個元素，只需用指針往后遍歷i次就可。貌似鏈表比數組還要麻煩些，而且效率低些。

　　想到這些相同處中的一些細微的不同處，于是他們的真正不同處漸漸顯現了：鏈表的效率為何比數組低些?先從兩者的初始化開始。數組無需初始化，因為數組的元素在內存的棧區，系統自動申請空間。而鏈表的結點元素在內存的堆區，每個元素須手動申請空間，如malloc。也就是說數組是靜態分配內存，而鏈表是動態分配內存。鏈表如此麻煩為何還要用鏈表呢?數組不能完全代替鏈表嗎?為何那時候要用鏈表?因為管理系統中的插入，刪除等操作都很靈活，而數組則大小固定，也無法靈活高效的插入，刪除。因為堆操作靈活性更強。數組每次插入一個元素就需要移動已有元素，而鏈表元素在堆上，無需這么麻煩。

　　說了這么多，數組和鏈表的區別整理如下：

　　數組靜態分配內存，鏈表動態分配內存;

　　數組在內存中連續，鏈表不連續;

　　數組元素在棧區，鏈表元素在堆區;

　　數組利用下標定位，時間復雜度為O(1)，鏈表定位元素時間復雜度O(n);

　　數組插入或刪除元素的時間復雜度O(n)，鏈表的時間復雜度O(1)。

　　1.數組的特點：

　　在內存中，數組是一塊連續的區域。例如看電影來說，幾個去在電影院看電影必須坐在一起。

　　數組需要預留空間，在使用前要先申請占內存的大小，可能會浪費內存空間。比如看電影時，為了保證10個人能坐在一起，必須提前訂好10個連續的位置。這樣的好處就是能保證10個人可以在一起。但是這樣的缺點是，如果來的人不夠10個，那么剩下的位置就浪費了。如果臨時有多來了個人，那么10個就不夠用了，這時可能需要將第11個位置上的人挪走，或者是他們11個人重新去找一個11連坐的位置，效率都很低。如果沒有找到符合要求的作為，那么就沒法坐了。

　　插入數據和刪除數據效率低，插入數據時，這個位置后面的數據在內存中都要向后移。刪除數據時，這個數據后面的數據都要往前移動。比如原來去了5個人，然后后來又去了一個人要坐在第三個位置上，那么第三個到第五個都要往后移動一個位子，將第三個位置留給新來的人。當這個人走了的時候，因為他們要連在一起的，所以他后面幾個人要往前移動一個位置，把這個空位補上。

　　隨機讀取效率很高。因為數組是連續的，知道每一個數據的內存地址，可以直接找到給地址的數據。并且不利于擴展，數組定義的空間不夠時要重新定義數組。

　　2 .鏈表的特點

　　在內存中可以存在任何地方，不要求連續。在電影院幾個人可以隨便坐。

　　每一個數據都保存了下一個數據的內存地址，通過這個地址找到下一個數據。第一個人知道第二個人的座位號，第二個人知道第三個人的座位號……

　　增加數據和刪除數據很容易。再來個人可以隨便坐，比如來了個人要做到第三個位置，那他只需要把自己的位置告訴第二個人，然后問第二個人拿到原來第三個人的位置就行了。其他人都不用動。

　　查找數據時效率低，因為不具有隨機訪問性，所以訪問某個位置的數據都要從第一個數據開始訪問，然后根據第一個數據保存的下一個數據的地址找到第二個數據，以此類推。要找到第三個人，必須從第一個人開始問起。

　　不指定大小，擴展方便。鏈表大小不用定義，數據隨意增刪。

　　3.各自的優缺點：

　　(1)數組的優點：

　　隨機訪問性強

　　查詢速度快

　　(2)數組的缺點：