Java中List接口常见的实现类

目录

ArrayList实现类

数据存储

构造器

成员方法：CRUD

Vector实现类

数据存储

构造器方法

成员方法

LinkedList实现类

数据存储

构造器方法

成员方法CRUD

List总结

---

ArrayList：数组实现，随机访问速度快，增删慢，轻量级；(线程不安全)

LinkedList：双向链表实现，增删快，随机访问慢 (线程不安全)

Vector：数组实现，重量级 (线程安全、使用少)

ArrayList实现类

 List list=new ArrayList();

类定义：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, 
Cloneable, java.io.Serializable

数据存储

transient Object[] elementData; //底层存储实现采用的是数组，当存储数据元素超过数组长度时会进行扩容处理。

构造器

1、public ArrayList() {  //ArrayList默认实现中,针对元素存储的数组赋值为空数组，实际上这是一种优化策略，避免饿汉模式的缺陷，避免额外的空间浪费。
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

其中常量定义为

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //空数组

2、public ArrayList(int initialCapacity) {  //参数为初始化容积，不是元素个数size。
    if (initialCapacity > 0) { 
        this.elementData = new Object[initialCapacity];  //构建指定长度的数组
    } else if (initialCapacity == 0) {  //如果初始化容积为0则为空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {  //否则抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

成员方法：CRUD

1、public boolean add(E e)

public boolean add(E e) {modCount++;  
//一个用于实现fail-fast异常的参数，记录的是修改次数，在迭代器中需要使用这个值，只要修改了结构则+1add(e, elementData, size); 
//参数1为需要插入的数据，参数2为正在使用的数组，参数3为当前元素个数return true;   
//除非上一步出现异常，否则返回true表示插入成功
}

private void add(E e, Object[] elementData, int s) {if (s == elementData.length)  //如果当前数组长度等于元素个数则扩容处理elementData = grow();elementData[s] = e;  //在指定位置存储元素size = s + 1;  //元素个数+1
}

private Object[] grow() {return grow(size + 1);  //新容器为元素个数+1
}

private Object[] grow(int minCapacity) {  
//参数size+1实际上是所需要的最小容积，不是扩容的目标大小int oldCapacity = elementData.length;  
//获取当前数组的长度if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, oldCapacity >> 1 );  
//获取最新容积大小值，参数1为当前容积值，参数2为最小扩容值【size+1-数组长度】，参数3为老容积值的1/2整除return elementData = Arrays.copyOf(elementData, newCapacity); 
//执行老数组的元素数据拷贝，并将扩容后的新数组赋值给属性以替换老数组} else { //如果容积值<=0则创建10个长的数组用于存储元素return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}
}

ArraySupport工具类

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow  
//新容器=老容积+max(最小扩容值1，老容积的1/2),扩容为+50%*原始容积if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {return prefLength;  
//扩容值在0到Integer.MAX_VALUE - 8则正常使用该扩容值} else {  
//如果扩容目标长度值大于Integer.MAX_VALUE - 8：如果原始长度+1小于0 越int界则异常中断；如果原始长度+1在Integer.MAX_VALUE - 8范围内则每次扩容到Integer.MAX_VALUE - 8;如果原始长度+1大于Integer.MAX_VALUE - 8时，则每次扩容目标值为原始长度+1return hugeLength(oldLength, minGrowth);  //原始容积 最小增长值1}
}

private static int hugeLength(int oldLength, int minGrowth) {int minLength = oldLength + minGrowth;  //原始长度+1if (minLength < 0) {  //最小长度值<0 则数据溢出，抛出异常Error中断运行throw new OutOfMemoryError("Required array length " + oldLength + " + " + minGrowth + " is too large");} else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {return SOFT_MAX_ARRAY_LENGTH;} else {return minLength;}
}

结论：添加数据时当存储数据的数组长度不足时，数组会自动变长，变长的比例为50%

2、remove方法定义

2.1 public boolean remove(Object o)  //按照元素进行删除

2.2 public E remove(int index) //按照指定下表进行删除，并返回被删除的元素

public E remove(int index) {Objects.checkIndex(index, size); 
//调用工具类Objects中的方法进行索引需要的合法性检查，如果不合法[0,size)之间，否则IndexOutOfBoundsExceptionfinal Object[] es = elementData;  
//缓存数组变量,如果需要2个不同对象但是内容相同的数组则需要clone处理，=只是将存放数据的数组地址赋值给新变量，不管使用elementData变量还是使用es变量都是在操作同一个数组E oldValue = (E) es[index];  
//从数组中获取指定index位置上的数据fastRemove(es, index);  
//采用System.arraycopy将指定位置上的数据进行覆盖return oldValue;
}

private void fastRemove(Object[] es, int i) {modCount++;  //修改次数+1final int newSize;if ((newSize = size - 1) > i)  System.arraycopy(es, i + 1, es, i, newSize - i);es[size = newSize] = null;
}

结论：使用数组元素移动的方式实现元素的删除  System.arraycopy(es, i + 1, es, i, newSize - i);

注意：这里没有变小容积

修改元素个数时会有modCount的修改--快速失败

修改次数定义在AbstractList抽象类中

protected transient int modCount = 0;

public Iterator<E> iterator() {return listIterator();  // ---new 迭代器
}

//在抽象类中采用内部类的方式提供了迭代器的实现类

private class Itr implements Iterator<E>

属性int expectedModCount = modCount;  //当创建迭代器对象时会记录当前的修改次数

public E next() {  
//调用迭代的next方法获取下一个元素时，会针对当前集合的修改次数和缓存的修改次数进行比较，如果不相等则抛出ConcurrentModificationException异常checkForComodification();//    ... ...}

final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
}

3、get方法的实现

结论：首先要求index应该在[0,size-1]的范围内，否则异常

如果index正确则按照下标从数组中获取元素

public E get(int index) {Objects.checkIndex(index, size);return elementData(index);
}

E elementData(int index) {return (E) elementData[index];
}

Vector实现类

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess,Cloneable, java.io.Serializable

从JDK1.0开始就提供的一个List的实现类，属于较老的不推荐使用的实现类，建议优先考虑ArrayList，因为两者的实现方式基本一致，而且ArrayList性能优于Vector.

数据存储

protected Object[] elementData;  //底层实现仍旧采用的是数组

构造器方法

1、public Vector()

public Vector() {this(10);  //无参构建Vector对象时默认初始化容积为10，默认容积增长的步长值为0
}

2、public Vector(int initialCapacity)

public Vector(int initialCapacity) {this(initialCapacity, 0);
}

3、public Vector(int initialCapacity, int capacityIncrement)

public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);this.elementData = new Object[initialCapacity];  
//直接创建的就是指定长度的数组，并没有支持延迟创建数组的操作this.capacityIncrement = capacityIncrement;
}

成员方法

绝大部分的成员方法前有synchronized关键字，线程安全，属于重量级

1、public synchronized boolean add(E e)

public synchronized boolean add(E e) {modCount++;  //修改次数+1，快死异常add(e, elementData, elementCount);  
//参数1为需要添加的数据，参数2为原始数组，参数3为当前元素个数sizereturn true;
}

private void add(E e, Object[] elementData, int s) {if (s == elementData.length)  //当元素个数和数组长度一致时进行扩容处理growelementData = grow();elementData[s] = e;  //扩容后的数组存储元素elementCount = s + 1;  //元素个数+1
}

private Object[] grow() {return grow(elementCount + 1);   //参数为当前元素个数+1作为所需要的最小容积值
}

private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;  //获取当前数组长度int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, capacityIncrement > 0 ? capacityIncrement : oldCapacity);  
//获取扩容后的新数组最佳长度值。如果设定了扩容步长值，则使用构建Vector对象时所设置的扩容步长值进行长度的递增【定值】；如果没有设置，则扩容步长值默认为0则新长度为原始长度的2倍，扩容+100%原始长度return elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList实现类

public class LinkedList<E> extends AbstialLtractSequenist<E> implements List<E>, 
Deque<E>, Cloneable, java.io.Serializable  

实现了Deque双向队列接口

数据存储

transient Node<E> first;  //头指针
transient Node<E> last;  //尾指针

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;}
}

构造器方法

public LinkedList() {}public LinkedList(Collection<? extends E> c) {this();addAll(c);}

成员方法CRUD

1、public boolean add(E e)

public boolean add(E e) {linkLast(e);   //在链表的默认添加新元素Node类型，其中包含存储的数据ereturn true;
}

void linkLast(E e) {final Node<E> l = last; //获取尾指针final Node<E> newNode = new Node<>(l, e, null); //构建链表中的元素对象Node，其中包含数据elast = newNode;  //原始尾指针指向新元素if (l == null)  //如果尾指针为null则表示链表中没有数据，则将头和尾指向同一个元素first = newNode;else  //如果尾指针不为null，则将新元素添加到尾指针(Node元素的后续指针)之后l.next = newNode;size++;  //元素个数+1modCount++;  //修改次数+1
}

2、指定位置index序号添加元素

public void add(int index, E element) {checkPositionIndex(index);   index >= 0 && index <= sizeif (index == size)  //如果插入元素的位置等于元素个数则插入到末尾linkLast(element);else  //否则在指定位置之前插入元素linkBefore(element, node(index));  //node()用于获取指定位置的节点元素
}

Node<E> node(int index) {  
//按照索引序号查找指定位置上的元素时，首先判断序号距离头部近还是尾部近，如果距离头部近则从头指针指向的元素开始查找，如果距离尾部较劲则从后向前查找元素。可以减少1/2个数的元素查找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;}
}

3、public boolean remove(Object o)

public boolean remove(Object o) { 
//删除定义元素。如果需要删除的元素o则从头指针开始遍历整个链表，如果Node节点对象中的数据为o【equals】则执行删除操作。删除第一个值为o的元素节点if (o == null) { for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {  unlink(x);  //删除指定的节点return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}

4、public E remove(int index)

public E remove(int index) {  
//按照序号删除指定位置上的节点checkElementIndex(index);  
// index >= 0 && index < sizereturn unlink(node(index));  
//首先调用node()方法获取指定位置上的Node对象，然后删除指定的节点
}

总结：双向链表实现，由于没有数据移动的问题所以号称增删快【增删时还需要查找元素，所以实际上差不多O(n)】，随机访问慢 (线程不安全)。没有扩容问题，按需开辟空间，没有空间浪费。

List总结

	ArrayList	LinkedList	Vector
实现方式	数组，按照索引下标访问速度快O(1),但是当删除添加元素时会导致元素的移动，速度慢O(n)	双向链表，按照索引下标访问速度慢O(n)，但是删除添加元素速度快O(1)	数组，按照索引下标访问速度快O(1),但是当删除添加元素时会导致元素的移动，速度慢O(n)
是否同步	不同步,线程不安全，但是并发高,访问效率高	不同步,线程不安全，但是并发高,访问效率高	同步,所以线程安全，但是并发低,访问效率低
如何选择	经常需要快速访问，较少在中间增加删除元素时使用;如果多线程访问，则需要自行编程解决线程安全问题	经常需要在内部增删元素，但是很少需要通过索引快速访问时使用;如果多线程访问，则需要自行编程解决线程安全问题	一般不使用，如果在多线程访问时可以考虑使用