目錄
一、順序表和鏈表的比較
順序表
優(yōu)點：
缺點：
鏈表
優(yōu)點
缺點
二、順序表和鏈表的區(qū)別
1.順序表和鏈表都具有增、刪、查、改功能，但算法復(fù)雜度卻不相同。
2、從數(shù)據(jù)元素存儲的內(nèi)存角度來看
三、順序表與鏈表選取方案
一、順序表和鏈表的比較
順序表
順序表的特點是邏輯上相鄰數(shù)據(jù)元素，物理存儲位置相鄰，并且順序表的存儲空間需要預(yù)先分配，存儲空間是靜態(tài)分配的。
?
優(yōu)點：
- 順序表具有按數(shù)組下標隨機訪問的特點。
- 不用為表示節(jié)點間的邏輯關(guān)系而增加額外的存儲開銷
缺點：
- 在順序表中做插入、刪除操作時，需要遍歷數(shù)組元素，當數(shù)組元素較大時，順序表效率低。
- 靜態(tài)分配，程序執(zhí)行之前必須明確規(guī)定存儲規(guī)模預(yù)先分配足夠大的存儲空間，估計過大，可能會導(dǎo)致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出。
鏈表
在鏈表中邏輯上相鄰的數(shù)據(jù)元素，物理存儲位置不一定相鄰，它使用指針實現(xiàn)元素之間的邏輯關(guān)系。并且鏈表的存儲空間是動態(tài)分配的。
優(yōu)點
- 插入、刪除運算方便。
缺點
- 鏈表不是一種隨機存儲結(jié)構(gòu)，不能隨機存取元素。
- 要占用額外的存儲空間存儲元素之間的關(guān)系，存儲密度降低。
?
二、順序表和鏈表的區(qū)別
1.順序表和鏈表都具有增、刪、查、改功能，但算法復(fù)雜度卻不相同。
- 增：
a) 順序表往指定位置，不覆蓋的添加一個值，后面的元素要往后移動，算法復(fù)雜度為O(n)；b) 鏈表往指定位置添加一個節(jié)點，需要從表頭遍歷到指定位置，算法復(fù)雜度為O(n)????????? ? ?注意：如果鏈表帶有索引的節(jié)點，算法復(fù)雜度為O(1) - 刪：
a) 順序表指定位置，刪除一個值時，需要將后面的值向前移動，算法復(fù)雜度為O(n);
b) 鏈表指定一個位置，刪除一個時，如果沒有對指定節(jié)點進行索引，需要從表頭遍歷到指定? 位置，然后將指定節(jié)點刪除，算法復(fù)雜度為O(n),? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?注意：如果對鏈表指定節(jié)點做索引，刪除節(jié)點的算法復(fù)雜度為O(1)。 - 查：
a) 順序表根據(jù)數(shù)組元素下標直接查詢指定元素，算法復(fù)雜度為O(1)；
b) 鏈表需要遍歷節(jié)點到指定位置，算法復(fù)雜度為O(n);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?注意：如果節(jié)點指定位置節(jié)點有索引，算法復(fù)雜度為O(1). - 改：修改其實就是查找修改值的位置，再對值進行修改。
a) 順序表的增和刪表數(shù)量規(guī)模比較大時平均移動一半的元素，效率不高，算法復(fù)雜度為O(n);
b) 對于有索引的鏈表，添加和刪除只需要O(1)算法復(fù)雜度，效率高。因此，鏈表用于頻繁的添加和刪除數(shù)據(jù)時，有優(yōu)勢。
2、從數(shù)據(jù)元素存儲的內(nèi)存角度來看
（1）順序表是由數(shù)組組成的線性表，數(shù)組是一組地址連續(xù)的單元存儲塊，分配于棧區(qū)，可以自動釋放。
（2）鏈表是由不連續(xù)的地址節(jié)點組成的線性表，每個節(jié)點可以是一個單元的地址塊或連續(xù)地址塊，分配于堆區(qū)，節(jié)點必須手動釋放。內(nèi)存管理比較不方便。
三、順序表與鏈表選取方案
（1）順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲規(guī)模，也就是說事先對“MaxSize”要有合適的設(shè)定，設(shè)定過大會造成存儲空間的浪費，過小造成溢出。
? ? ? ? 因此，當對線性表的長度或存儲規(guī)模難以估計時，不宜采用順序表。然而，鏈表的動態(tài)分配則可以克服這個缺點。鏈表不需要預(yù)留存儲空間，也不需要知道表長如何變化，只要內(nèi)存空間尚有空閑，就可以再程序運行時隨時地動態(tài)分配空間，不需要時還可以動態(tài)回收。
? ? ? ?
（2）順序存儲是一種隨機存取的結(jié)構(gòu)，而鏈表則是一種順序存取結(jié)構(gòu)，因此它們對各種操作有完全不同的算法和時間復(fù)雜度。例如，要查找線性表中的第i個元素，對于順序表可以直接計算出a(i)的的地址，不用去查找，其時間復(fù)雜度為0(1).而鏈表必須從鏈表頭開始，依次向后查找，平均需要0(n)的時間。所以，如果經(jīng)常做的運算是按序號訪問數(shù)據(jù)元素，顯然順表優(yōu)于鏈表。
???????查找操作的線性表，適于選擇順序存儲；而頻繁做插入刪除運算的線性表適宜選擇鏈式存儲。文章來源：http://www.zghlxwxcb.cn/news/detail-716277.html
（3）順序表容易實現(xiàn)，任何高級語言中都有數(shù)組類型；鏈表的操作是基于指針的。相對來講前者簡單些，也用戶考慮的一個因素。文章來源地址http://www.zghlxwxcb.cn/news/detail-716277.html
到了這里，關(guān)于順序表與鏈表的區(qū)別的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
