這篇文章主要講解了“數(shù)組與鏈表的詳細(xì)介紹”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“數(shù)組與鏈表的詳細(xì)介紹”吧！
創(chuàng)新互聯(lián)建站主打移動(dòng)網(wǎng)站、做網(wǎng)站、成都網(wǎng)站制作、網(wǎng)站改版、網(wǎng)絡(luò)推廣、網(wǎng)站維護(hù)、國際域名空間、等互聯(lián)網(wǎng)信息服務(wù)，為各行業(yè)提供服務(wù)。在技術(shù)實(shí)力的保障下，我們?yōu)榭蛻舫兄Z穩(wěn)定，放心的服務(wù)，根據(jù)網(wǎng)站的內(nèi)容與功能再?zèng)Q定采用什么樣的設(shè)計(jì)。最后，要實(shí)現(xiàn)符合網(wǎng)站需求的內(nèi)容、功能與設(shè)計(jì)，我們還會(huì)規(guī)劃穩(wěn)定安全的技術(shù)方案做保障。
數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲(chǔ)一組具有相同類型的數(shù)據(jù)。
線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個(gè)線性表上的數(shù)據(jù)最多只有前和后兩個(gè)方向。其實(shí)除了數(shù)組，鏈表、隊(duì)列、棧等也是線性表結(jié)構(gòu)。
比如二叉樹、堆、圖等叫非線性表，因?yàn)樵诜蔷€性表中，數(shù)據(jù)之間并不是簡單的前后關(guān)系。
優(yōu)點(diǎn)：根據(jù)下標(biāo)實(shí)現(xiàn)隨機(jī)訪問元素。
缺點(diǎn)：數(shù)組中插入、刪除元素，可能需要遷移數(shù)據(jù)實(shí)現(xiàn)連續(xù)的內(nèi)存空間，效率較低。
計(jì)算機(jī)會(huì)給每個(gè)內(nèi)存單元分配一個(gè)地址，計(jì)算機(jī)通過地址來訪問內(nèi)存中的數(shù)據(jù)。當(dāng)計(jì)算機(jī)需要隨機(jī)訪問數(shù)組中的某個(gè)元素時(shí)，它會(huì)首先通過下面的尋址公式，計(jì)算出該元素存儲(chǔ)的內(nèi)存地址： a[i]_address = base_address + i * data_type_size
拓展：對于m*n的二維數(shù)組尋址公式： a[i][j]_address = base_address + ( i * n + j) * data_type_size
數(shù)組查找元素的時(shí)間復(fù)雜度為O(1)的表述是?的，因?yàn)榧词故峭ㄟ^二分查找排序好的數(shù)組時(shí)間復(fù)雜度也是O(logn)，正確的是數(shù)組支持隨機(jī)訪問，根據(jù)下標(biāo)隨機(jī)訪問的時(shí)間復(fù)雜度為O(1);
由于連續(xù)的內(nèi)存空間特點(diǎn)，我們在插入或刪除元素時(shí)需要將該元素之后的數(shù)據(jù)全部往后或者往前移動(dòng)。即最好時(shí)間復(fù)雜度為O(1)，最壞時(shí)間復(fù)雜度為O(n)；由于每個(gè)位置操作元素的概率是一樣的，所以平均時(shí)間復(fù)雜度為(1+2+…n)/n=O(n)。
如果存儲(chǔ)的數(shù)據(jù)不是有序的，我們可以在插入時(shí)將原位置的元素插入到數(shù)組尾部，在刪除時(shí)將數(shù)組尾部元素替換當(dāng)前的位置的元素；這樣插入或刪除操作的時(shí)間復(fù)雜度為O(1)：
很多語言提供了基于數(shù)組的容器類 比如Java的ArrayList或者C++的vector；下面以ArrayList為例來看容器相比數(shù)組的優(yōu)勢：
容器可以將很多數(shù)組操作的細(xì)節(jié)封裝起來，比如元素插入或者刪除時(shí)其它元素的遷移工作，另外相比數(shù)組來講，容器還可以動(dòng)態(tài)擴(kuò)容。
因?yàn)閿U(kuò)容操作涉及內(nèi)存申請和數(shù)據(jù)搬移是比較耗時(shí)的，所以在創(chuàng)建容器時(shí)最好指定數(shù)據(jù)的大小，盡量避免擴(kuò)容操作。
對于業(yè)務(wù)開發(fā)來講，使用容器就足夠了，省時(shí)省力；
對于網(wǎng)絡(luò)框架、性能優(yōu)化等底層開發(fā)，盡量使用數(shù)組。
鏈表也是線性表結(jié)構(gòu)，相比數(shù)組來講不需要連續(xù)的內(nèi)存空間，可通過“指針”將零散的內(nèi)存塊串聯(lián)起來，對內(nèi)存要求沒數(shù)組那么高。
每個(gè)鏈表的結(jié)點(diǎn)除了儲(chǔ)存數(shù)據(jù)外還需記錄下一個(gè)結(jié)點(diǎn)的位置，即后繼指針next。
在單鏈表中，第一個(gè)結(jié)點(diǎn)稱為頭結(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)叫做尾結(jié)點(diǎn)；頭結(jié)點(diǎn)記錄鏈表的開始地址，尾結(jié)點(diǎn)后繼指針指向空地址NULL。
在上面數(shù)組低效的插入與刪除中我們講過，數(shù)組為了保證內(nèi)存的連續(xù)需要搬移操作元素之后的元素，所以時(shí)間復(fù)雜度為O(n)，而在鏈表中我們只需考慮相鄰節(jié)點(diǎn)的后繼指針改變，所以對應(yīng)的時(shí)間復(fù)雜度為O(1)。
因?yàn)殒湵碇袃?nèi)存地址不是連續(xù)的，所以不能根據(jù)開始地址和下標(biāo)計(jì)算對應(yīng)元素的內(nèi)存地址，需要根據(jù)后繼指針一一遍歷找到指定節(jié)點(diǎn)。
循環(huán)鏈表跟單鏈表唯一的區(qū)別在于單鏈表尾結(jié)點(diǎn)后繼指針指向空地址NULL，而循環(huán)鏈表尾結(jié)點(diǎn)后繼指針指向頭結(jié)點(diǎn)，像環(huán)一樣首尾相連。
單向鏈表每個(gè)結(jié)點(diǎn)只有一個(gè)后繼指針next，而雙向鏈表結(jié)點(diǎn)除了next還有一個(gè)前驅(qū)指針prev。
存儲(chǔ)同樣多的數(shù)據(jù)時(shí)，雙向鏈表雖然比單鏈表占用更多內(nèi)存空間，但是比單鏈表更為靈活支持雙向遍歷，使其在某些情況下插入刪除操作比單鏈表更為簡單、高效。
其實(shí)在討論單鏈表時(shí)，我們說插入和刪除的時(shí)間復(fù)雜度為O(1)，其實(shí)這個(gè)描述是不準(zhǔn)確的，下面我們已刪除操作為例：
盡管刪除操作的時(shí)間復(fù)雜度為O(1)，但是我們要根據(jù)值從頭結(jié)點(diǎn)開始遍歷比較找到要?jiǎng)h除的結(jié)點(diǎn)，遍歷查詢對應(yīng)的時(shí)間復(fù)雜度為O(n)；根據(jù)加法法則，此種刪除的時(shí)間復(fù)雜度為O(n)。
這種情況我們已經(jīng)找到了要?jiǎng)h除的結(jié)點(diǎn)，但是如果是單鏈表，我們還需要遍歷單鏈表查詢其前驅(qū)結(jié)點(diǎn)信息，所以時(shí)間復(fù)雜度仍然為O(n)；
但雙向鏈表可以直接通過當(dāng)前結(jié)點(diǎn)prev找到其前驅(qū)結(jié)點(diǎn)信息，所以時(shí)間復(fù)雜度為O(1)。
雙鏈表的實(shí)現(xiàn)就是用空間換時(shí)間的設(shè)計(jì)思想；當(dāng)內(nèi)存空間充足的時(shí)候，如果我們更加追求代碼的執(zhí)行速度，我們就可以選擇空間復(fù)雜度相對較高、但時(shí)間復(fù)雜度相對很低的算法或者數(shù)據(jù)結(jié)構(gòu)。
相反，如果內(nèi)存比較緊缺，比如代碼跑在手機(jī)或者單片機(jī)上，這個(gè)時(shí)候，就要反過來用時(shí)間換空間的設(shè)計(jì)思路。
雙向循環(huán)鏈表就是整合了雙向鏈表和循環(huán)鏈表的新版本
數(shù)組訪問效率高；但是不支持動(dòng)態(tài)擴(kuò)容，需要整塊內(nèi)存空間。
鏈表天然支持動(dòng)態(tài)擴(kuò)容，插入刪除操作更快；但是占用更多內(nèi)存，頻繁插入刪除時(shí)容易造成內(nèi)存碎片，可能導(dǎo)致頻繁的GC。
感謝各位的閱讀，以上就是“數(shù)組與鏈表的詳細(xì)介紹”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對數(shù)組與鏈表的詳細(xì)介紹這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
重慶分公司
重慶分公司
