數(shù)組
- 概念
數(shù)組就是相同數(shù)據(jù)類型的元素按照一定順序排列的集合 - 特點
- 查詢簡單，插入和刪除比較復(fù)雜座哩。
- 需要占用一塊連續(xù)的內(nèi)存空間徒扶。
- 優(yōu)點
隨機訪問性強，查找速度快八回，時間復(fù)雜度是O(1)酷愧。因為數(shù)組的內(nèi)存空間是連續(xù)的驾诈，想訪問哪個元素缠诅，直接從數(shù)組的首地址向后偏移index個元素長度就可以得到。 - 缺點
- 從頭部刪除/插入的效率低乍迄，時間復(fù)雜度是O(n)管引，因為需要把對應(yīng)的元素向前/向后搬移
- 空間利用率低，必須要有連續(xù)的內(nèi)存空間闯两。
- 擴容復(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)點
- 任意位置插入元素和刪除元素的速度快，時間復(fù)雜度為O(1)
- 內(nèi)存利用率高借嗽，不會浪費內(nèi)存态鳖。
- 鏈表的空間大小不固定，可以動態(tài)擴展恶导。
- 缺點
隨機訪問效率低浆竭，時間復(fù)雜度為O(1)
總結(jié)
- 想要快速訪問數(shù)據(jù)，不經(jīng)常插入和刪除元素的時候惨寿，選擇數(shù)組
- 對于需要經(jīng)常插入和刪除元素邦泄，而對訪問元素時的效率沒有很高要求的話，選擇鏈表裂垦。
擴展
數(shù)組的底層是ArrayList顺囊，鏈表的底層是HashMap
