數(shù)組的優(yōu)點：

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

數(shù)組的缺點：

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

鏈表的優(yōu)點：

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

比如:

單鏈表，每個元素除了存儲本身的值外，還存儲了前驅(qū)的引用，也就是存儲了前驅(qū)所在的內(nèi)存地址信息。

雙鏈表就是不僅存儲了前驅(qū)的引用還存儲了后繼的引用.

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

鏈表的缺點：

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

內(nèi)存中的存儲形式可以分為連續(xù)存儲和離散存儲兩種。因此，數(shù)據(jù)的物理存儲結(jié)構(gòu)就有連續(xù)存儲和離散存儲兩種，它們對應(yīng)了我們通常所說的數(shù)組和鏈表。

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

與之相反，鏈表是離散存儲的，所以在插入一個數(shù)據(jù)時只要申請一片新空間，然后將其中的連接關(guān)系做一個修改就可以，但是顯然在鏈表上查找一個數(shù)據(jù)時就要逐個遍歷了。

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

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

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

總結(jié)：

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

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

最新評論