Java面向對象基礎知識之數組和鏈表

Posted on by

數組的優點：

  • 隨機訪問性強
  • 查找速度快
    • 數組要求是一塊連續的內存空間來存儲，這就要求在物理上這一片空間是連續的，每個元素都有指定的索引index指向內存地址，因此查詢對時候，可根據index快速找到對應地址存儲的信息，此為查詢快.

數組的缺點：

  • 插入和刪除效率低
    • 數組進行增刪的時候，就必須將目標位置後的所有元素都整體移動，因此就比較耗時，此為增刪慢.
  • 可能浪費內存
  • 內存空間要求高，必須有足夠的連續內存空間。
  • 數組大小固定，不能動態拓展

鏈表的優點：

  • 插入刪除速度快
    • 鏈表在物理上是動態地分配儲存空間，不要求連續性，但是要求邏輯上的連續。它需要存儲每個元素在內存中的地址，以及它相鄰元素的地址，然後像鏈條一樣把各元素鏈起來，保證瞭在邏輯上的連續性。

比如:

單鏈表，每個元素除瞭存儲本身的值外，還存儲瞭前驅的引用，也就是存儲瞭前驅所在的內存地址信息。

雙鏈表就是不僅存儲瞭前驅的引用還存儲瞭後繼的引用.

  • 增加元素的時候，隻需給增加元素添加其前元素或後元素的地址；刪除元素的時候，修改目標元素前驅和後驅的首位連接地址. 故此為增刪快。
  • 內存利用率高，不會浪費內存大小沒有固定，拓展很靈活。

鏈表的缺點：

  • 不能隨機查找，必須從第一個開始遍歷，查找效率低
    • 由於沒有像數組那樣的索引，因此，查詢的時候需要遍歷整個鏈表所有元素的內存地址，然後才能確定目標元素，此為查詢慢。

內存中的存儲形式可以分為連續存儲和離散存儲兩種。因此，數據的物理存儲結構就有連續存儲和離散存儲兩種，它們對應瞭我們通常所說的數組和鏈表。

因為數組是連續存儲的，在操作數組中的數據時就可以根據離首地址的偏移量直接存取相應位置上的數據，但是如果要在數據組中任意位置上插入一個元素，就需要先把後面的元素集體向後移一位為其空出存儲空間。

與之相反，鏈表是離散存儲的，所以在插入一個數據時隻要申請一片新空間，然後將其中的連接關系做一個修改就可以，但是顯然在鏈表上查找一個數據時就要逐個遍歷瞭。

考慮以上的總結可見，數組和鏈表各有優缺點。在具體使用時要根據具體情況選擇。當查找數據操作比較多時最好用數組；當對數據集中的數據進行添加或刪除比較多時最好選擇鏈表。

數組就像身上編瞭號站成一排的人，要找第10個人很容易，根據人身上的編號很快就能找到。但插入、刪除慢，要望某個位置插入或刪除一個人時，後面的人身上的編號都要變。當然，加入或刪除的人始終末尾的也快

鏈表就像手牽著手站成一圈的人，要找第10個人不容易，必須從第一個人一個個數過去。但插入、刪除快。插入時隻要解開兩個人的手，並重新牽上新加進來的人的手就可以。刪除一樣的道理。

總結：

  • 數組靜態分配內存，鏈表動態分配內存;
  • 數組在內存中連續，鏈表不連續;
  • 數組元素在棧區，鏈表元素在堆區;
  • 數組利用下標定位，時間復雜度為O(1)，鏈表定位元素時間復雜度O(n);
  • 數組插入或刪除元素的時間復雜度O(n)，鏈表的時間復雜度O(1);

本篇文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!

推薦閱讀：