Java中的List集合
Faith_xzc 人气:01.概述
List是一个有序集合（也被称为序列）。此接口的用户在列表中的每个元素都被插入的地方有精确的控制。用户可以通过它们的整数索引（在列表中的位置）访问元素，并在列表中搜索元素。 说是List集合，其实只是习惯说法，因为它是Collection接口的一个子接口（Collection有很多的子接口，这是其中三个主要的子接口之一，另外两个后面都会说到），所以Collection接口中定义的方法在List接口中也是可以使用的，另外还根据List的特点，又引入了其他的方法。
List接口的特点：
- 元素是以一种线性方式进行存储的
- 元素存取有序，即元素的存入顺序和取出顺序一致。
- 元素带有索引，通过索引就可以精确的操作集合中的元素（与数组类似）
- 元素可以重复，通过元素的equals方法，来比较是否为重复的元素
2.List的使用
2.1List的常用方法
基本介绍：
这里说的常用方法是指除了实现Collection接口之外的。前面说到List集合中的元素是可以通过索引来操作集合中的元素的，所以List 集合里添加了一些根据索引来操作集合元素的方法。下面对这些方法进行简单
介绍：
void add(iint index, E element)： 在列表中指定的位置上插入指定的元素boolean addAll(int index, Collection c)： 将指定的集合中的所有元素插入到指定位置的列表中E get(int index)：返回此列表中指定位置的元素List subList(int fromIndex, int toIndex)：返回List中一部分对象的集合，即返回的集合是List的子集合，并是以下标索引取值。父集合List以fromIndex开始(包含)，到toIndex结束(不包含)的 部分为返回的子集合int indexOf(Object obj)：返回此列表中指定元素的第一个出现的索引，如果此列表不包含元素，返回- 1int lastIndexOf(Object obj)：返回此列表中指定元素的最后一个发生的索引，如果此列表不包含元素，返回- 1E remove(int index)：移除此列表中指定位置的元素E set(int index, E element)：用指定元素替换此列表中指定位置的元素
代码示例:
public class ListDemo {
public static void main(String[] args) {
// 通过List的实现类ArrayList创建List集合对象
List<String> list = new ArrayList<String>();
// 指定位置添加元素
list.add(0,"jack");
list.add(1,"rose");
list.add(2,"marry");
System.out.println(list);
// 删除索引位置为2的元素
list.remove(2);
System.out.println(list);
// 指定元素替换此列表中指定位置的元素
list.set(0, "老王");
System.out.println(list);
// 获取指定位置元素(也遍历输出下)
for(int i = 0;i<list.size();i++){
System.out.println(list.get(i));
}
//还可以使用增强for
for (String string : list) {
System.out.println(string);
}
}
}3.List的实现类
作为一个接口，List的实现类才是我们创建对象时候使用的（上面代码示例里面用到了ArrayList实现类）。在List接口里，有三个常用的实现类：ArrayList、Vector、LinkedList。下面从源码中分析和介绍它们。
3.1ArrayList
ArrayList底层通过数组实现，ArrayList可以随着元素的增加而动态扩容。它是一个数组队列，是Java集合框架中使用最多的一个类，但是它是线程不安全的。
- 特点：以数组的形式进行存储，因此随机访问速度较快，所有它适用于查询
- 缺点：不适用于插入和删除的操作 因为每次操作都需要移动数组中的元素；线程不安全
下面看下ArrayList的源码：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
/**
* Default initial capacity. 初始化的时候如果没有指定长度的话，使用默认长度10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances. 空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added. 空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.构造一个初始容量为10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//初始化为空数组
}
public boolean add(E e) {
//查看当前数组是否够多存一个元素
ensureCapacityInternal(size + 1); // Increments modCount!!
//存入新元素到[size]位置，然后size自增1
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果当前数组还是空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//那么minCapacity取DEFAULT_CAPACITY与minCapacity的最大值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//查看是否需要扩容
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//修改次数加1
// 如果需要的最小容量比当前数组的长度大，即当前数组不够存，就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//当前数组容量
int newCapacity = oldCapacity + (oldCapacity >> 1);//新数组容量是旧数组容量的1.5倍
//看旧数组的1.5倍是否够
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//看旧数组的1.5倍是否超过最大数组限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//复制一个新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
public boolean remove(Object o) {
//先找到o在当前ArrayList的数组中的下标
//分o是否为空两种情况讨论
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {//null值用==比较
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {//非null值用equals比较
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;//修改次数加1
//需要移动的元素个数
int numMoved = size - index - 1;
//如果需要移动元素，就用System.arraycopy移动元素
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将elementData[size-1]位置置空，让GC回收空间，元素个数减少
elementData[--size] = null; // clear to let GC do its work
}
public E remove(int index) {
rangeCheck(index);//检验index是否合法
modCount++;//修改次数加1
//取出[index]位置的元素，[index]位置的元素就是要被删除的元素，用于最后返回被删除的元素
E oldValue = elementData(index);
//需要移动的元素个数
int numMoved = size - index - 1;
//如果需要移动元素，就用System.arraycopy移动元素
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将elementData[size-1]位置置空，让GC回收空间，元素个数减少
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public E set(int index, E element) {
rangeCheck(index);//检验index是否合法
//取出[index]位置的元素，[index]位置的元素就是要被替换的元素，用于最后返回被替换的元素
E oldValue = elementData(index);
//用element替换[index]位置的元素
elementData[index] = element;
return oldValue;
}
public E get(int index) {
rangeCheck(index);//检验index是否合法
return elementData(index);//返回[index]位置的元素
}
public int indexOf(Object o) {
//分为o是否为空两种情况
if (o == null) {
//从前往后找
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public int lastIndexOf(Object o) {
//分为o是否为空两种情况
if (o == null) {
//从后往前找
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}从上面的源码中我们可以看到：
- ArrayList 在初始化的时候如果我们没有指定长度的话，它会有一个默认长度10，每次扩容的时候为增加1.5倍
- 然后是ArrayList 的一些常见的方法的源码介绍
3.2Vector
Vector的底层也是通过数组实现，方法与ArrayList基本一致,。但是Vector是线程安全的. 这是因为其加上了 synchronized 关键字, 用来保证线程安全。
- 优点: 以数组的形式进行存储，因此随机访问速度较快，所有它适用于查询；线程安全
- 缺点: 不适用于插入和删除的操作 因为每次操作都需要移动数组中的元素
下面看下Vector的源码：
/**
* Constructs an empty vector so that its internal data array
* has size {@code 10} and its standard capacity increment is
* zero.
*/
public Vector() {
this(10); //指定初始容量initialCapacity为10
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);//指定capacityIncrement增量为0
}
public Vector(int initialCapacity, int capacityIncrement增量为0) {
super();
//判断了形参初始容量initialCapacity的合法性
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//创建了一个Object[]类型的数组
this.elementData = new Object[initialCapacity];//默认是10
//增量，默认是0，如果是0，后面就按照2倍增加，如果不是0，后面就按照你指定的增量进行增量
this.capacityIncrement = capacityIncrement;
}
//synchronized意味着线程安全的
public synchronized boolean add(E e) {
modCount++;
//看是否需要扩容
ensureCapacityHelper(elementCount + 1);
//把新的元素存入[elementCount]，存入后，elementCount元素的个数增1
elementData[elementCount++] = e;
return true;
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
//看是否超过了当前数组的容量
if (minCapacity - elementData.length > 0)
grow(minCapacity);//扩容
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//获取目前数组的长度
//如果capacityIncrement增量是0，新容量 = oldCapacity的2倍
//如果capacityIncrement增量是不是0，新容量 = oldCapacity + capacityIncrement增量;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//如果按照上面计算的新容量还不够，就按照你指定的需要的最小容量来扩容minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量超过了最大数组限制，那么单独处理
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//把旧数组中的数据复制到新数组中，新数组的长度为newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
//查找obj在当前Vector中的下标
int i = indexOf(obj);
//如果i>=0，说明存在，删除[i]位置的元素
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
public int indexOf(Object o) {
return indexOf(o, 0);
}
public synchronized int indexOf(Object o, int index) {
if (o == null) {//要查找的元素是null值
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)//如果是null值，用==null判断
return i;
} else {//要查找的元素是非null值
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))//如果是非null值，用equals判断
return i;
}
return -1;
}
public synchronized void removeElementAt(int index) {
modCount++;
//判断下标的合法性
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
//j是要移动的元素的个数
int j = elementCount - index - 1;
//如果需要移动元素，就调用System.arraycopy进行移动
if (j > 0) {
//把index+1位置以及后面的元素往前移动
//index+1的位置的元素移动到index位置，依次类推
//一共移动j个
System.arraycopy(elementData, index + 1, elementData, index, j);
}
//元素的总个数减少
elementCount--;
//将elementData[elementCount]这个位置置空，用来添加新元素，位置的元素等着被GC回收
elementData[elementCount] = null; /* to let gc do its work */
}从上面的源码中我们可以看到：
Vector在初始化的时候如果我们没有指定长度的话，它会有一个默认长度10，每次扩容的时候为增加2倍
然后是Vector的一些常见的方法的源码介绍
3.3LinkedList
LinkedList底层的数据存储结构是链表结构，而且还是一个双向链表，可以实现双向操作。此外，LinkedList还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用，如peek 、push、pop等方法。
- 优点: 以链表形式进行存储，因此随机访问速度查询慢，增删快。
- 缺点: 线程不安全
下面看一下源码：
int size = 0;
Node<E> first;//记录第一个结点的位置
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 boolean add(E e) {
linkLast(e);//默认把新元素链接到链表尾部
return true;
}
void linkLast(E e) {
final Node<E> l = last;//用l 记录原来的最后一个结点
//创建新结点
final Node<E> newNode = new Node<>(l, e, null);
//现在的新结点是最后一个结点了
last = newNode;
//如果l==null，说明原来的链表是空的
if (l == null)
//那么新结点同时也是第一个结点
first = newNode;
else
//否则把新结点链接到原来的最后一个结点的next中
l.next = newNode;
//元素个数增加
size++;
//修改次数增加
modCount++;
}
public boolean remove(Object o) {
//分o是否为空两种情况
if (o == null) {
//找到o对应的结点x
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);//删除x结点
return true;
}
}
} else {
//找到o对应的结点x
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);//删除x结点
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {//x是要被删除的结点
// assert x != null;
final E element = x.item;//被删除结点的数据
final Node<E> next = x.next;//被删除结点的下一个结点
final Node<E> prev = x.prev;//被删除结点的上一个结点
//如果被删除结点的前面没有结点，说明被删除结点是第一个结点
if (prev == null) {
//那么被删除结点的下一个结点变为第一个结点
first = next;
} else {//被删除结点不是第一个结点
//被删除结点的上一个结点的next指向被删除结点的下一个结点
prev.next = next;
//断开被删除结点与上一个结点的链接
x.prev = null;//使得GC回收
}
//如果被删除结点的后面没有结点，说明被删除结点是最后一个结点
if (next == null) {
//那么被删除结点的上一个结点变为最后一个结点
last = prev;
} else {//被删除结点不是最后一个结点
//被删除结点的下一个结点的prev执行被删除结点的上一个结点
next.prev = prev;
//断开被删除结点与下一个结点的连接
x.next = null;//使得GC回收
}
//把被删除结点的数据也置空，使得GC回收
x.item = null;
//元素个数减少
size--;
//修改次数增加
modCount++;
//返回被删除结点的数据
return element;
}从上面的源码中我们可以看到：
LinkedList是基于链表的，所以没有扩容方法，默认加入元素是尾部自动扩容
然后是LinkedList的一些常见的方法的源码介绍
3.4ArrayList与Vector的区别
它们的底层结构都是数组，我们称为动态数组。
- ArrayList是新版的动态数组，线程不安全，效率高，Vector是旧版的动态数组，线程安全，效率低。
- 动态数组的扩容机制不同，ArrayList扩容为原来的1.5倍，Vector扩容增加为原来的2倍。
- 数组的初始化容量，如果在构建ArrayList与Vector的集合对象时，没有显式指定初始化容量，那么Vector的内部数组的初始容量默认为10，而ArrayList在JDK1.6及之前的版本也是10，而JDK1.7之后的版本ArrayList初始化为长度为0的空数组，之后在添加第一个元素时，再创建长度为10的数组。
加载全部内容