數(shù)組和鏈表的比較

數(shù)組

  • 概念
    數(shù)組就是相同數(shù)據(jù)類型的元素按照一定順序排列的集合
  • 特點
  1. 查詢簡單,插入和刪除比較復(fù)雜座哩。
  2. 需要占用一塊連續(xù)的內(nèi)存空間徒扶。
  • 優(yōu)點
    隨機訪問性強,查找速度快八回,時間復(fù)雜度是O(1)酷愧。因為數(shù)組的內(nèi)存空間是連續(xù)的驾诈,想訪問哪個元素缠诅,直接從數(shù)組的首地址向后偏移index個元素長度就可以得到。
  • 缺點
  1. 從頭部刪除/插入的效率低乍迄,時間復(fù)雜度是O(n)管引,因為需要把對應(yīng)的元素向前/向后搬移
  2. 空間利用率低,必須要有連續(xù)的內(nèi)存空間闯两。
  3. 擴容復(fù)雜褥伴。當(dāng)數(shù)組的長度達到設(shè)置的閾值后谅将,要想插入新的元素,必須進行擴容重慢,即將舊數(shù)組中的所有元素向新數(shù)組中拷貝饥臂。

鏈表

  • 概念
    鏈表是一種物理存儲單元上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)似踱。數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針連接次序?qū)崿F(xiàn)的隅熙。鏈表由一系列結(jié)點構(gòu)成,結(jié)點可以在運行時動態(tài)生成核芽,每個結(jié)點包括兩部分囚戚,一部分是存儲數(shù)據(jù)元素的數(shù)據(jù)域,一部分是存儲下一個結(jié)點地址的指針域轧简。
  • 特點
    鏈表存儲區(qū)間離散驰坊,占用內(nèi)存比較寬松,故空間復(fù)雜度很小哮独,但時間復(fù)雜度很大拳芙。
  • 優(yōu)點
  1. 任意位置插入元素和刪除元素的速度快,時間復(fù)雜度為O(1)
  2. 內(nèi)存利用率高借嗽,不會浪費內(nèi)存态鳖。
  3. 鏈表的空間大小不固定,可以動態(tài)擴展恶导。
  • 缺點
    隨機訪問效率低浆竭,時間復(fù)雜度為O(1)

總結(jié)

  1. 想要快速訪問數(shù)據(jù),不經(jīng)常插入和刪除元素的時候惨寿,選擇數(shù)組
  2. 對于需要經(jīng)常插入和刪除元素邦泄,而對訪問元素時的效率沒有很高要求的話,選擇鏈表裂垦。

擴展

數(shù)組的底層是ArrayList顺囊,鏈表的底層是HashMap

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市蕉拢,隨后出現(xiàn)的幾起案子特碳,更是在濱河造成了極大的恐慌,老刑警劉巖晕换,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件午乓,死亡現(xiàn)場離奇詭異,居然都是意外死亡闸准,警方通過查閱死者的電腦和手機益愈,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人蒸其,你說我怎么就攤上這事敏释。” “怎么了摸袁?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵钥顽,是天一觀的道長。 經(jīng)常有香客問我靠汁,道長耳鸯,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任膀曾,我火速辦了婚禮县爬,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘添谊。我一直安慰自己财喳,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布斩狱。 她就那樣靜靜地躺著耳高,像睡著了一般。 火紅的嫁衣襯著肌膚如雪所踊。 梳的紋絲不亂的頭發(fā)上泌枪,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天,我揣著相機與錄音秕岛,去河邊找鬼碌燕。 笑死,一個胖子當(dāng)著我的面吹牛继薛,可吹牛的內(nèi)容都是我干的修壕。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼遏考,長吁一口氣:“原來是場噩夢啊……” “哼慈鸠!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起灌具,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤青团,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后咖楣,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體督笆,經(jīng)...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年截歉,在試婚紗的時候發(fā)現(xiàn)自己被綠了胖腾。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片烟零。...
    茶點故事閱讀 40,928評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡瘪松,死狀恐怖咸作,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情宵睦,我是刑警寧澤记罚,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站壳嚎,受9級特大地震影響桐智,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜烟馅,卻給世界環(huán)境...
    茶點故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一说庭、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧郑趁,春花似錦刊驴、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至梭纹,卻和暖如春躲惰,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背变抽。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工础拨, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人绍载。 一個月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓太伊,卻偏偏與公主長得像,于是被迫代替她去往敵國和親逛钻。 傳聞我的和親對象是個殘疾皇子僚焦,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,937評論 2 361