概述 LinkedLIst和ArrayLIst一樣, 都實現了List介面, 但其內部的數據結構不同, LinkedList是基於鏈表實現的(從名字也能看出來), 隨機訪問效率要比ArrayList差. 它的插入和刪除操作比ArrayList更加高效, 但還是要遍歷部分鏈表的指針才能移動到下標所指的 ...
概述
LinkedLIst和ArrayLIst一樣, 都實現了List介面, 但其內部的數據結構不同, LinkedList是基於鏈表實現的(從名字也能看出來), 隨機訪問效率要比ArrayList差. 它的插入和刪除操作比ArrayList更加高效, 但還是要遍歷部分鏈表的指針才能移動到下標所指的位置, 只有在鏈表兩頭的操作能省掉移動, 如add(), addFirest(), removeLast()等.
LinkedList源碼分析
1.數據結構
LinkedList是基於鏈表結構實現的, 在類中定義了頭尾指針. 其內部維護了一個雙向鏈表
2.構造方法
預設構造函數很簡單, 啥也沒有
將集合的元素添加的LinkedList中:
3.存儲
(1)add(E)在鏈表的末尾添加元素
(2)add(int, E)在指定的位置插入元素
(3)addAll(Collection)將集合添加到鏈表末尾, 該方法在構造方法中介紹了, 在此不再贅述
(4)addAll(int, Collection)將集合添加到鏈表的指定位置, 該方法也在構造方法中介紹了
(5)addFirst(E)將元素添加到鏈表表頭位置
(6)addLast(E)將元素添加到表尾
4.獲取
5.刪除
刪除方法不在給出源碼, 基本大同小異. 有如下方法:
- remove(): 刪除第一個元素並返回, 調用 removeFirst 方法
- remove(int): 刪除鏈表指定位置的元素
- remove(Object): 從鏈表中刪除首次出現的元素
- removeFirst(): 刪除並返回第一個元素
- removeLast(): 刪除並返回最後一個元素
- removeFirstOccurrence(Object): 從鏈表中刪除第一次出現的指定元素
- removeLastOccurrence(Object): 從鏈表中刪除最後一個出現的指定元素
LinkedList是一個功能強大的類, 可以當作List集合、隊列和棧來使用.
