深入解析List源码：揭秘Java集合框架的核心
在Java编程语言中，集合框架是一个非常重要的组成部分，它提供了丰富的数据结构，如List、Set、Queue等，用于存储和操作数据。在这些数据结构中，List是最基本的一种，它允许存储一组有序的元素。本文将深入解析List源码，带您了解Java集合框架的核心机制。
一、List接口概述
List接口是Java集合框架中的一个核心接口，它继承自Collection接口，并提供了有序集合的行为。List接口定义了以下方法：
1.添加元素：add(E e) 2.删除元素：remove(int index) 3.获取元素：get(int index) 4.设置元素：set(int index, E e) 5.检查是否包含元素：contains(Object o) 6.获取元素索引：indexOf(Object o) 7.获取最后一个元素索引：lastIndexOf(Object o) 8.判断是否为空：isEmpty() 9.获取元素数量：size() 10. 清空集合：clear() 11.判断是否包含所有元素：containsAll(Collection<?> c) 12.添加所有元素：addAll(Collection<? extends E> c) 13.移除所有元素：removeAll(Collection<?> c) 14.保留所有元素：retainAll(Collection<?> c) 15.差集操作：removeAll(Collection<?> c)
二、ArrayList源码解析
ArrayList是List接口的一个实现类，它基于动态数组实现，提供了高效的随机访问能力。下面我们来分析ArrayList的源码。
1.类定义
`java
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
private int size;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ARRAY;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ARRAY;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class) {
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
} else {
this.elementData = EMPTY_ARRAY;
}
}}
`
2.添加元素
java
public boolean add(E e) {
modCount++;
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
在添加元素时，首先检查数组是否已满，如果已满，则扩容。扩容方法为ensureCapacityInternal：
java
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ARRAY) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
如果当前数组为默认空数组，则将最小容量设置为默认容量或传入的容量值，然后调用ensureExplicitCapacity方法确保数组容量。
java
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
如果数组长度小于最小容量，则调用grow方法进行扩容。
java
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
if (newCapacity - MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(minCapacity);
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
扩容方法首先计算新的容量，然后使用Arrays.copyOf方法将旧数组复制到新数组中。
3.删除元素
java
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
return oldValue;
}
删除元素时，首先检查索引是否有效，然后获取要删除的元素，并移动后面的元素以填补空位。
三、LinkedList源码解析
LinkedList是List接口的另一个实现类，它基于双向链表实现，提供了高效的插入和删除操作。下面我们来分析LinkedList的源码。
1.类定义
`java
public class LinkedList<E> extends AbstractList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}}
`
2.添加元素
java
public boolean add(E e) {
linkLast(e);
return true;
}
在添加元素时，调用linkLast方法将元素添加到链表的末尾。
java
private void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = ((last = new Node<>(l, e, null)) == null) ? (last = newNode) : (last = newNode);
if (l == null)
first = newNode;
}
如果链表为空，则新节点即为头节点和尾节点。否则，将新节点添加到链表的末尾，并更新尾节点。
3.删除元素
java
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
在删除元素时，首先检查索引是否有效，然后调用unlink方法删除节点。
`java
private E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
}
x.item = null;
x.next = x.prev = null;
return element;}
`
删除节点时，首先获取节点的前驱和后继节点，然后更新它们的前驱和后继指针。最后，将节点从链表中移除，并返回被删除的元素。
四、总结
通过以上对List接口及其实现类ArrayList和LinkedList的源码解析，我们可以了解到Java集合框架的核心机制。在实际开发中，选择合适的集合类型对于提高代码效率和性能至关重要。希望本文能帮助您更好地理解Java集合框架，并在实际项目中灵活运用。