## List接口
繼承Collection接口的一個接口,就是傳統的線性表的結構,實現該接口的結構存儲的數據不唯一(值不唯一,類型是唯一的),同時數據按照添加的順序進行排列。
其主要擴展Collection的方法有:
~~~
?public interface List<E> extends Collection<E> {
? ? ?// 元素進行排序
? ? ?default void sort(Comparator<? super E> c) {
? ? ? ? ?Object[] a = this.toArray();
? ? ? ? ?Arrays.sort(a, (Comparator) c);
? ? ? ? ?ListIterator<E> i = this.listIterator();
? ? ? ? ?for (Object e : a) {
? ? ? ? ? ? ?i.next();
? ? ? ? ? ? ?i.set((E) e);
? ? ? ? }
? ? }
? ? ?
? ? ?// 獲取某個下標的元素
? ? ?E get(int index);
? ? ?
? ? ?// 修改某個下標的元素
? ? ?E set(int index, E element);
? ? ?
? // 判斷元素是否存在
? ? ?// 從頭開始,并返回第一相同元素的索引
? ? ?int indexOf(Object o);
? ? ?// 從后面開始,并返回第一個相同元素的索引
? ? ?int lastIndexOf(Object o);
? ? ?
? ? ?// 快速創建List對象的靜態方法
? ? ?static <E> List<E> of() {
? ? ? ? ?return (List<E>) ImmutableCollections.ListN.EMPTY_LIST;
? ? }
? ? ?static <E> List<E> of(E e1) {
? ? ? ? ?return new ImmutableCollections.List12<>(e1);
? ? }
? ? ?// 還有好幾個重載的方法
? ? ?
?}
~~~
*****
下面是List的常見實現類:
### Vector
底層用數組存儲,里面的方法都是線程安全的,現版本基本別拋棄了,不建議使用。
~~~
?public class Vector<E> extends AbstractList<E>
? ? ?implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
? ? ?// 1. 重要的屬性
? ? ?// 用數組結構來保存數據
? ? ?protected Object[] elementData;
? ? ?// 數組中元素的個數
? ? ?protected int elementCount;
? ? ?// 擴容時數組增長的大小,如果該值小于等于0時會默認增長一倍
? ? ?protected int capacityIncrement;
? ? ?
? ? ?//-----------------------------------------------------
? ? ?// 2.構造函數
? ? ?public Vector() {
? ? ? ? ?// 無參構造默認數組初始化大小為10
? ? ? ? ?this(10);
? ? }
? ? ?public Vector(int initialCapacity) {
? ? ? ? ?// 默認擴容因子為0,因此在擴容的時候會增長數組長度的一倍
? ? ? ? ?this(initialCapacity, 0);
? ? }
? ? ?public Vector(int initialCapacity, int capacityIncrement) {
? ? ? ? ?// 最終都會調用這個
? ? ? ? ?super();
? ? ? ? ?if (initialCapacity < 0)
? ? ? ? ? ? ?throw new IllegalArgumentException("Illegal Capacity: "+
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? initialCapacity);
? ? ? ? ?this.elementData = new Object[initialCapacity];
? ? ? ? ?this.capacityIncrement = capacityIncrement;
? ? }
? ? ?
? ? ?// -------------------------------------------
? ? ?// 3. 常見操作
? ? ?// 添加元素,修改到底層數組結構內容的有如下兩個方法:
? ? ?// 私有的,供其他add方法調用,往s的位置添加
? ? ?private void add(E e, Object[] elementData, int s) {
? ? ? ? ?if (s == elementData.length)
? ? ? ? ? ? ?// 超出底層數組大小需要擴容
? ? ? ? ? ? ?elementData = grow();
? ? ? ? ?elementData[s] = e;
? ? ? ? ?elementCount = s + 1;
? ? }
? ? ?// 插入操作,往index位置插入
? ? ?public synchronized void insertElementAt(E obj, int index) {
? ? ? ? ?if (index > elementCount) {
? ? ? ? ? ? ?// 插入范圍在0~elementCount
? ? ? ? ? ? ?throw new ArrayIndexOutOfBoundsException(index
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? + " > " + elementCount);
? ? ? ? }
? ? ? ? ?// AbstractList中聲明的用來記錄結構被修改的次數,可以用于增強for循環中刪除數組元素報錯的情況。
? ? ? ? ?modCount++;
? ? ? ? ?final int s = elementCount;
? ? ? ? ?Object[] elementData = this.elementData;
? ? ? ? ?if (s == elementData.length)
? ? ? ? ? ? ?elementData = grow();
? ? ? ? ?// 將index開始的元素移動到index+1后,使用native方法,性能更高
? ? ? ? ?System.arraycopy(elementData, index,
? ? ? ? ? ? ? ? ? ? ? ? ? elementData, index + 1,
? ? ? ? ? ? ? ? ? ? ? ? ? s - index);
? ? ? ? ?elementData[index] = obj;
? ? ? ? ?elementCount = s + 1;
? ? }
? ? ?
? ? ?// 獲取元素
? ? ?public synchronized E get(int index) {
? ? ? ? ?if (index >= elementCount)
? ? ? ? ? ? ?throw new ArrayIndexOutOfBoundsException(index);
??
? ? ? ? ?return elementData(index);
? ? }
? ? ?E elementData(int index) {
? ? ? ? ?return (E) elementData[index];
? ? }
? ? ?
? ? ?// 移除元素
? ? ?public synchronized E remove(int index) {
? ? ? ? ?modCount++;
? ? ? ? ?if (index >= elementCount)
? ? ? ? ? ? ?throw new ArrayIndexOutOfBoundsException(index);
? ? ? ? ?E oldValue = elementData(index);
??
? // 要移動元素的數量,如果是index為最后一個元素則不用移除操作
? ? ? ? ?int numMoved = elementCount - index - 1;
? ? ? ? ?if (numMoved > 0)
? ? ? ? ? ? ?// 將index+1的位置往前移動即可刪除
? ? ? ? ? ? ?System.arraycopy(elementData, index+1, elementData, index,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? numMoved);
? ? ? ? ?elementData[--elementCount] = null; // Let gc do its work
??
? ? ? ? ?return oldValue;
? ? }
? ? ?
? ? ?// 移除所有元素
? ? ?public void clear() {
? ? ? ? ?removeAllElements();
? ? }
? ? ?public synchronized void removeAllElements() {
? ? ? ? ?final Object[] es = elementData;
? ? ? ? ?for (int to = elementCount, i = elementCount = 0; i < to; i++)
? ? ? ? ? ? ?es[i] = null;
? ? ? ? ?modCount++;
? ? }
? ? ?
? // --------------------------------------
? ? ?// 擴容操作
? ? ?private Object[] grow() {
? ? ? // 至少擴容大于1個元素
? ? ? ? ?return grow(elementCount + 1);
? ? }
? ? ?private Object[] grow(int minCapacity) {
? ? ? ? ?int oldCapacity = elementData.length;
? ? ? ? ?// 獲取新的數組長度,當擴容因子為0的時候擴展為原來的1倍大小
? ? ? ? ?int newCapacity = ArraysSupport.newLength(oldCapacity,
? ? ? ? ? ? ?minCapacity - oldCapacity, capacityIncrement > 0 ? capacityIncrement : oldCapacity);
? ? ? ? ?return elementData = Arrays.copyOf(elementData, newCapacity);
? ? }
?}
~~~
*****
### ArrayList
底層用數組存儲,與Vector相比,ArrayList的操作不是線程安全的,其他基本與Vector相同。
~~~
?public class ArrayList<E> extends AbstractList<E>
? ? ? ? ?implements List<E>, RandomAccess, Cloneable, java.io.Serializable
?{
??
? ? ?/**
? ? ? * 默認初始化數組元素的大小
? ? ? */
? ? ?private static final int DEFAULT_CAPACITY = 10;
??
? ? ?/**
? ? ? * 創建沒有元素的ArrayList的話所有ArrayList共享這個對象,節約空間
? ? ? */
? ? ?private static final Object[] EMPTY_ELEMENTDATA = {};
??
? ? ?/**
? * 沒有指定初始化容量時使用,可以用于標識在添加第一個元素的時候需要擴容的大小
? ? ? */
? ? ?private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
??
? ? ?/**
? ? ? * 底層數組結構,通過上面兩個全局靜態的常量可以發現,當初始化容量為0或者不指定的時候這是一個延遲創建的對象,知道真正添加元素的時候才創建
? ? ? */
? ? ?transient Object[] elementData;
??
? ? ?/**
? ? ? * 元素個數
? ? ? */
? ? ?private int size;
? ? ?
? ? ?// 構造方法
? ? ?public ArrayList(int initialCapacity) {
? ? ? ? ?if (initialCapacity > 0) {
? ? ? ? ? ? ?this.elementData = new Object[initialCapacity];
? ? ? ? } else if (initialCapacity == 0) {
? ? ? ? ? ? ?// 容量為0的時候不創建對象
? ? ? ? ? ? ?this.elementData = EMPTY_ELEMENTDATA;
? ? ? ? } else {
? ? ? ? ? ? ?throw new IllegalArgumentException("Illegal Capacity: "+
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? initialCapacity);
? ? ? ? }
? ? }
??
? ? ?/**
? ? ? * 不指定初始化容量的時候在第一次添加元素時會初始化10個元素大小的數組
? ? ? */
? ? ?public ArrayList() {
? ? ? ? ?this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
? ? }
? ? ?
? ? ?/** 其他操作和vector相比差不多,主要是擴容機制不太一樣,ArrayList沒有擴容因子,因此在一般情況都是擴容當前長度的1/2大小的;
? ? ?有個特殊的情況就是如果當初始化容量為0的時候第一次添加元素的時候只會擴容一個元素
? ? ?*/
? ? ?private Object[] grow(int minCapacity) {
? ? ? ? ?int oldCapacity = elementData.length;
? ? ? ? ?if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
? ? ? ? ? ? ?int newCapacity = ArraysSupport.newLength(oldCapacity,
? ? ? ? ? ? ? ? ?minCapacity - oldCapacity, oldCapacity >> 1);// 右移
? ? ? ? ? ? ?return elementData = Arrays.copyOf(elementData, newCapacity);
? ? ? ? } else {
? ? ? ? ? ? ?return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
? ? ? ? }
? ? }
?}
~~~
ArrayList的擴容機制有點特殊的點在于當沒有指定初始容量或者初始容量為0的時候在第一次添加數據的時候就會進入擴容邏輯,是延遲創建對象的:
1. 初始容量為0時第一次添加元素創建1個長度的底層數組。
2. 沒有指定初始容量時第一次添加元素創建默認長度為10的底層數組。
3. 初始化容量指定為0時,第一次添加元素的數組長度會擴容為1。
Vector和ArrayList的異同:
1. 正常情況下底層數組初始大小都為10。
2. Vector可以指定初始的擴容因子,并且在沒有指定的情況下默認擴容一倍大小;而ArrayList不能指定擴容因子的大小,正常情況下每次擴容原來的1/2。
3. Vector的操作都是同步的,使用synchronized關鍵字進行修飾,而ArrayList的操作并不是同步的。
4. ArrayList在初始化容量為0或者沒有指定初始化容量的時候做了一些優化,可以實現延遲創建對象的效果。
*****
### LinkedList
底層用雙向鏈表存儲數據
~~~
?public class LinkedList<E>
? ? ?extends AbstractSequentialList<E>
? ? ?implements List<E>, Deque<E>, Cloneable, java.io.Serializable
?{
? ? ?// 元素數量
? ? ?transient int size = 0;
? // 指向頭節點
? ? ?transient Node<E> first;
? ? ?// 指向尾節點
? ? ?transient Node<E> last;
? ? ?
? ? ?// 空構造
? ? ?public LinkedList() {
? ? }
? ? ?
? ? ?// Node結構如下
? ? ?private static class Node<E> {
? ? ? ? ?E item;
? ? ? ? ?// 指向下一個元素
? ? ? ? ?Node<E> next;
? ? ? ? ?// 指向上一個元素
? ? ? ? ?Node<E> prev;
??
? ? ? ? ?Node(Node<E> prev, E element, Node<E> next) {
? ? ? ? ? ? ?this.item = element;
? ? ? ? ? ? ?this.next = next;
? ? ? ? ? ? ?this.prev = prev;
? ? ? ? }
? ? }
? ? ?
? ? ?// ------------------------------------------
? ? ?// 常見操作
? ? ?// 1. 添加節點
? ? ?public void addFirst(E e) {
? ? ? ? ?// 頭插
? ? ? ? ?linkFirst(e);
? ? }
? ? ?private void linkFirst(E e) {
? ? ? ? ?final Node<E> f = first;
? ? ? ? ?// 創建節點并連接
? ? ? ? ?final Node<E> newNode = new Node<>(null, e, f);
? ? ? ? ?first = newNode;
? ? ? ? ?if (f == null)
? ? ? ? ? ? ?last = newNode;
? ? ? ? ?else
? ? ? ? ? ? ?f.prev = newNode;
? ? ? ? ?size++;
? ? ? ? ?modCount++;
? ? }
? ? ?
? ? ?public void addLast(E e) {
? ? ? ? ?// 尾插
? ? ? ? ?linkLast(e);
? ? }
? ? ?void linkLast(E e) {
? ? ? ? ?final Node<E> l = last;
? ? ? ? ?// 創建節點并連接
? ? ? ? ?final Node<E> newNode = new Node<>(l, e, null);
? ? ? ? ?last = newNode;
? ? ? ? ?if (l == null)
? ? ? ? ? ? ?first = newNode;
? ? ? ? ?else
? ? ? ? ? ? ?l.next = newNode;
? ? ? ? ?size++;
? ? ? ? ?modCount++;
? ? }
? ? ?
? ? ?public boolean add(E e) {
? ? ? ? ?// add默認使用尾插
? ? ? ? ?linkLast(e);
? ? ? ? ?return true;
? ? }
? ? ?
? ? ?
? ? ?// 查詢操作
? ? ?Node<E> node(int index) {
? ? ? ? ?// 前一半位置從頭開始查,
? ? ? ? ?if (index < (size >> 1)) {
? ? ? ? ? ? ?Node<E> x = first;
? ? ? ? ? ? ?for (int i = 0; i < index; i++)
? ? ? ? ? ? ? ? ?x = x.next;
? ? ? ? ? ? ?return x;
? ? ? ? } else {
? ? ? ? ? ? ?// 后一半位置從尾開始查
? ? ? ? ? ? ?Node<E> x = last;
? ? ? ? ? ? ?for (int i = size - 1; i > index; i--)
? ? ? ? ? ? ? ? ?x = x.prev;
? ? ? ? ? ? ?return x;
? ? ? ? }
? ? }
? ? ?
? ? ?// 算了...其他就需要再看吧,下面這些都是隊列的相關操作,注意其實現了Dequeu
? ? ?public E peek() {} // 獲取第一個元素
? ? ?public E poll() {} // 刪除第一個元素并返回
? ? ?public E remove() {} // 移除第一個元素
? ? ?public void push(E e) {} ?// 插入第一個元素的位置
? ? ?public E pop() {} // 彈出第一個元素
?}
~~~
從源代碼可以看出LinkedList是一個雙端鏈表,不僅可以作為鏈表使用,還可以作為隊列使用。
參考:
JDK1.8源碼
- 第一章 Java基礎
- ThreadLocal
- Java異常體系
- Java集合框架
- List接口及其實現類
- Queue接口及其實現類
- Set接口及其實現類
- Map接口及其實現類
- JDK1.8新特性
- Lambda表達式
- 常用函數式接口
- stream流
- 面試
- 第二章 Java虛擬機
- 第一節、運行時數據區
- 第二節、垃圾回收
- 第三節、類加載機制
- 第四節、類文件與字節碼指令
- 第五節、語法糖
- 第六節、運行期優化
- 面試常見問題
- 第三章 并發編程
- 第一節、Java中的線程
- 第二節、Java中的鎖
- 第三節、線程池
- 第四節、并發工具類
- AQS
- 第四章 網絡編程
- WebSocket協議
- Netty
- Netty入門
- Netty-自定義協議
- 面試題
- IO
- 網絡IO模型
- 第五章 操作系統
- IO
- 文件系統的相關概念
- Java幾種文件讀寫方式性能對比
- Socket
- 內存管理
- 進程、線程、協程
- IO模型的演化過程
- 第六章 計算機網絡
- 第七章 消息隊列
- RabbitMQ
- 第八章 開發框架
- Spring
- Spring事務
- Spring MVC
- Spring Boot
- Mybatis
- Mybatis-Plus
- Shiro
- 第九章 數據庫
- Mysql
- Mysql中的索引
- Mysql中的鎖
- 面試常見問題
- Mysql中的日志
- InnoDB存儲引擎
- 事務
- Redis
- redis的數據類型
- redis數據結構
- Redis主從復制
- 哨兵模式
- 面試題
- Spring Boot整合Lettuce+Redisson實現布隆過濾器
- 集群
- Redis網絡IO模型
- 第十章 設計模式
- 設計模式-七大原則
- 設計模式-單例模式
- 設計模式-備忘錄模式
- 設計模式-原型模式
- 設計模式-責任鏈模式
- 設計模式-過濾模式
- 設計模式-觀察者模式
- 設計模式-工廠方法模式
- 設計模式-抽象工廠模式
- 設計模式-代理模式
- 第十一章 后端開發常用工具、庫
- Docker
- Docker安裝Mysql
- 第十二章 中間件
- ZooKeeper