Java面向?qū)ο蠡A(chǔ)知識(shí)之?dāng)?shù)組和鏈表
數(shù)組的優(yōu)點(diǎn)：
- 隨機(jī)訪問性強(qiáng)
- 查找速度快
- 數(shù)組要求是一塊連續(xù)的內(nèi)存空間來存儲(chǔ)，這就要求在物理上這一片空間是連續(xù)的，每個(gè)元素都有指定的索引index指向內(nèi)存地址，因此查詢對(duì)時(shí)候，可根據(jù)index快速找到對(duì)應(yīng)地址存儲(chǔ)的信息，此為查詢快.
數(shù)組的缺點(diǎn)：
- 插入和刪除效率低
- 數(shù)組進(jìn)行增刪的時(shí)候，就必須將目標(biāo)位置后的所有元素都整體移動(dòng)，因此就比較耗時(shí)，此為增刪慢.
- 可能浪費(fèi)內(nèi)存
- 內(nèi)存空間要求高，必須有足夠的連續(xù)內(nèi)存空間。
- 數(shù)組大小固定，不能動(dòng)態(tài)拓展
鏈表的優(yōu)點(diǎn)：
- 插入刪除速度快
- 鏈表在物理上是動(dòng)態(tài)地分配儲(chǔ)存空間，不要求連續(xù)性，但是要求邏輯上的連續(xù)。它需要存儲(chǔ)每個(gè)元素在內(nèi)存中的地址，以及它相鄰元素的地址，然后像鏈條一樣把各元素鏈起來，保證了在邏輯上的連續(xù)性。
- 鏈表在物理上是動(dòng)態(tài)地分配儲(chǔ)存空間，不要求連續(xù)性，但是要求邏輯上的連續(xù)。它需要存儲(chǔ)每個(gè)元素在內(nèi)存中的地址，以及它相鄰元素的地址，然后像鏈條一樣把各元素鏈起來，保證了在邏輯上的連續(xù)性。
比如:
單鏈表，每個(gè)元素除了存儲(chǔ)本身的值外，還存儲(chǔ)了前驅(qū)的引用，也就是存儲(chǔ)了前驅(qū)所在的內(nèi)存地址信息。
雙鏈表就是不僅存儲(chǔ)了前驅(qū)的引用還存儲(chǔ)了后繼的引用.
- 增加元素的時(shí)候，只需給增加元素添加其前元素或后元素的地址；刪除元素的時(shí)候，修改目標(biāo)元素前驅(qū)和后驅(qū)的首位連接地址. 故此為增刪快。
- 內(nèi)存利用率高，不會(huì)浪費(fèi)內(nèi)存大小沒有固定，拓展很靈活。
鏈表的缺點(diǎn)：
- 不能隨機(jī)查找，必須從第一個(gè)開始遍歷，查找效率低
- 由于沒有像數(shù)組那樣的索引，因此，查詢的時(shí)候需要遍歷整個(gè)鏈表所有元素的內(nèi)存地址，然后才能確定目標(biāo)元素，此為查詢慢。
內(nèi)存中的存儲(chǔ)形式可以分為連續(xù)存儲(chǔ)和離散存儲(chǔ)兩種。因此，數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)就有連續(xù)存儲(chǔ)和離散存儲(chǔ)兩種，它們對(duì)應(yīng)了我們通常所說的數(shù)組和鏈表。
因?yàn)閿?shù)組是連續(xù)存儲(chǔ)的，在操作數(shù)組中的數(shù)據(jù)時(shí)就可以根據(jù)離首地址的偏移量直接存取相應(yīng)位置上的數(shù)據(jù)，但是如果要在數(shù)據(jù)組中任意位置上插入一個(gè)元素，就需要先把后面的元素集體向后移一位為其空出存儲(chǔ)空間。
與之相反，鏈表是離散存儲(chǔ)的，所以在插入一個(gè)數(shù)據(jù)時(shí)只要申請(qǐng)一片新空間，然后將其中的連接關(guān)系做一個(gè)修改就可以，但是顯然在鏈表上查找一個(gè)數(shù)據(jù)時(shí)就要逐個(gè)遍歷了。
考慮以上的總結(jié)可見，數(shù)組和鏈表各有優(yōu)缺點(diǎn)。在具體使用時(shí)要根據(jù)具體情況選擇。當(dāng)查找數(shù)據(jù)操作比較多時(shí)最好用數(shù)組；當(dāng)對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行添加或刪除比較多時(shí)最好選擇鏈表。
數(shù)組就像身上編了號(hào)站成一排的人，要找第10個(gè)人很容易，根據(jù)人身上的編號(hào)很快就能找到。但插入、刪除慢，要望某個(gè)位置插入或刪除一個(gè)人時(shí)，后面的人身上的編號(hào)都要變。當(dāng)然，加入或刪除的人始終末尾的也快
鏈表就像手牽著手站成一圈的人，要找第10個(gè)人不容易，必須從第一個(gè)人一個(gè)個(gè)數(shù)過去。但插入、刪除快。插入時(shí)只要解開兩個(gè)人的手，并重新牽上新加進(jìn)來的人的手就可以。刪除一樣的道理。
總結(jié)：
- 數(shù)組靜態(tài)分配內(nèi)存，鏈表動(dòng)態(tài)分配內(nèi)存;
- 數(shù)組在內(nèi)存中連續(xù)，鏈表不連續(xù);
- 數(shù)組元素在棧區(qū)，鏈表元素在堆區(qū);
- 數(shù)組利用下標(biāo)定位，時(shí)間復(fù)雜度為O(1)，鏈表定位元素時(shí)間復(fù)雜度O(n);
- 數(shù)組插入或刪除元素的時(shí)間復(fù)雜度O(n)，鏈表的時(shí)間復(fù)雜度O(1);
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
基于swagger測(cè)試List類型參數(shù)過程詳解
這篇文章主要介紹了基于swagger測(cè)試List類型參數(shù)過程詳解,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09
Java實(shí)現(xiàn)多個(gè)wav文件合成一個(gè)的方法示例
這篇文章主要介紹了Java實(shí)現(xiàn)多個(gè)wav文件合成一個(gè)的方法,涉及java文件流讀寫、編碼轉(zhuǎn)換、解析等相關(guān)操作技巧,需要的朋友可以參考下2019-05-05
Java 單鏈表數(shù)據(jù)結(jié)構(gòu)的增刪改查教程
這篇文章主要介紹了Java 單鏈表數(shù)據(jù)結(jié)構(gòu)的增刪改查教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-10-10
SSM(Spring+SpringMVC+MyBatis)框架集由Spring、MyBatis兩個(gè)開源框架整合而成(SpringMVC是Spring中的部分內(nèi)容),常作為數(shù)據(jù)源較簡單的web項(xiàng)目的框架,下面這篇文章主要給大家介紹了關(guān)于利用idea搭建SSM項(xiàng)目的相關(guān)資料,需要的朋友可以參考下2023-05-05
這篇文章主要介紹了如何在springboot中使用定時(shí)任務(wù)，幫助大家更好的理解和使用springboot框架，感興趣的朋友可以了解下2020-12-12
這篇文章主要介紹了shiro整合springboot前后端分離，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
這篇文章主要介紹了SpringBoot框架整合Mybatis的簡單攻略，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2021-10-10
Java設(shè)計(jì)模式之狀態(tài)模式（State模式）介紹
這篇文章主要介紹了Java設(shè)計(jì)模式之狀態(tài)模式（State模式）介紹,本文講解了何時(shí)使用狀態(tài)模式、如何使用狀態(tài)模式等內(nèi)容,需要的朋友可以參考下2015-03-03
MyBatis 動(dòng)態(tài)SQL和緩存機(jī)制實(shí)例詳解
這篇文章主要介紹了MyBatis 動(dòng)態(tài)SQL和緩存機(jī)制實(shí)例詳解，非常不錯(cuò)，具有參考借鑒價(jià)值,需要的朋友可以參考下2017-09-09
這篇文章主要為大家詳細(xì)介紹了JavaGUI模仿QQ聊天功能完整版，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-07-07