Java 中 List 的幾種實(shí)現(xiàn)

List 是 有序、可重復(fù) 的集合接口
常見(jiàn)實(shí)現(xiàn)：ArrayList、LinkedList、Vector、Stack、CopyOnWriteArrayList

ArrayList

底層結(jié)構(gòu)

• 動(dòng)態(tài)數(shù)組
• 初始容量：10
• 擴(kuò)容機(jī)制

新容量 = 舊容量 + 舊容量 / 2 （1.5 倍）

時(shí)間復(fù)雜度

線程安全

• 非線程安全

解決方案：Collections.synchronizedList；CopyOnWriteArrayList

LinkedList

底層結(jié)構(gòu)

• 雙向鏈表
• 每個(gè)節(jié)點(diǎn)：prev | item | next

時(shí)間復(fù)雜度

Vector

底層結(jié)構(gòu)

-動(dòng)態(tài)數(shù)組（和 ArrayList 類似）

關(guān)鍵區(qū)別

• 線程安全
• 方法都加了 synchronized

問(wèn)題

• 性能差（鎖太重）
• 已被淘汰

Stack

繼承關(guān)系

Stack extends Vector

特點(diǎn)

• 后進(jìn)先出（LIFO）
• 線程安全（繼承 Vector）

CopyOnWriteArrayList（并發(fā)重點(diǎn)）

底層思想

• 寫時(shí)復(fù)制

特點(diǎn)

對(duì)比總結(jié)

面試常見(jiàn)問(wèn)題

Q1：ArrayList 和 LinkedList 區(qū)別？

ArrayList：數(shù)組，查詢快，插入慢
LinkedList：鏈表，頭尾操作快，隨機(jī)訪問(wèn)慢

Q2：為什么 ArrayList 不是線程安全？

add / remove 過(guò)程中可能發(fā)生：
擴(kuò)容
覆蓋
數(shù)據(jù)丟失

Q3：CopyOnWriteArrayList 為什么讀快？

讀操作不加鎖
始終讀的是穩(wěn)定數(shù)組快照

Q4：為什么不推薦 Vector / Stack？

synchronized 粒度太大
性能差
有更好的并發(fā)方案

總結(jié)

ArrayList 查得快，LinkedList 插得快（頭尾），
并發(fā)讀多用 CopyOnWrite，Vector Stack 已淘汰

一、關(guān)于List和Set

List vs Set

一句話記憶：

List = 有順序 + 可重復(fù)
Set = 去重

二、List

什么是List？

• 像數(shù)組的升級(jí)版
• 能按順序存
• 能存重復(fù)元素
• 能通過(guò)下標(biāo)訪問(wèn)

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(10);
list.add(20);

System.out.println(list); // [10, 10, 20]
System.out.println(list.get(1)); // 10

三、Set

什么是Set？

• 天然去重
• 關(guān)心你插入順序
• 沒(méi)有下標(biāo)

Set<Integer> set = new HashSet<>();
set.add(10);
set.add(10);
set.add(20);

System.out.println(set); // [10, 20]

Set 是怎么判斷“重復(fù)”的？

靠 hashCode() + equals()

1. 先算 hashCode
2. 再用 equals 比較

四、List vs Set 核心區(qū)別

List 和 Set 都是 Collection 的子接口，主要區(qū)別在于是否允許重復(fù)和是否有順序。List 允許重復(fù)元素并且有下標(biāo)，適合順序存儲(chǔ)；Set 不允許重復(fù)元素，主要用于去重。

五、一句話總結(jié)

List：順序 + 重復(fù) + 下標(biāo)
Set：去重 + 無(wú)下標(biāo) + 基于 equals/hashCode

到此這篇關(guān)于Java中各種list有什么區(qū)別及l(fā)ist和set區(qū)別詳析的文章就介紹到這了,更多相關(guān)Java中l(wèi)ist和set內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論