List接口下的常用类源码解析
原创
该文章的方法不是逐个介绍，而是根据List接口的方法针对源码解析三者的区别
1.List接口下常用的类
常用的有 ArrayList、LinkedList、Vector，其特点都是有序，按照插入顺序进行排序并允许元素重复。
各自的特点
ArrayList: 底层数据结构是一个数组，允许对元素快速随机访问，插入和删除速度相对较慢，线程不安全
LinkedList: 底层数据结构是链表，随机访问较慢，插入和删除速度较快，重新指向头尾指针即可，线程不安全
Vector: 底层数据结构是数组，允许对元素快速随机访问，插入和删除速度相对较慢，线程安全
2.add(E e)
ArrayList:
public boolean add(E e) {
// 检查加一个元素后 数组长度是否够用，不够用的话需要增加数组长度
// 详细方法解析看下面
ensureCapacityInternal(size + 1); // Increments modCount!!
// 在记录的元素长度最后加入元素
elementData[size++] = e;
return true;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果增加后的长度大于现有数组长度 则扩
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 原来的数组长度
int oldCapacity = elementData.length;
// 扩充数组长度=原来的数组长度+(原来的数组长度/2)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩充后，依旧比所需最小容量小，则直接使用所需最小容量作为扩充长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
// 扩容后的数量大于预设的数组最大容量 则设置为Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 最小容量通常接近size
// 创建一个新数组（长度为扩容后的长度），复制原来的元素到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}LinkedList:
// 通常添加数据是添加到链表的最后，等效于 linkLast方法
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;
// 第一次插入元素是空，所以first也要设置
if (l == null)
first = newNode;
else
// 原来最后一个元素的尾指针指向新节点，形成双向链表
l.next = newNode;
size++;
modCount++;
}Vector:
vector的插入跟ArrayList的插入流程几乎一致，最重要的不同点在于线程安全，方法上添加了synchronized
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
}
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，每次扩容长度为旧长度*2
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}3.remove
ArrayList
这个是根据索引删除的
public E remove(int index) {
// 检查索引是否溢出
rangeCheck(index);
modCount++;
// 找到数组中的索引为index的元素
E oldValue = elementData(index);
int numMoved = size - index - 1;
// 如果等于0 则代表删的是最后一个元素
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}这段是根据元素值来进行删除的
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 需要逐个遍历元素，确定位置后再进行删除，按此逻辑只会删除第一个，其他相同值的不会被删除
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 几乎跟remove(int index)没什么差别，感觉只用调用都可以了，不需要重新写。都是先找到索引再删
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}LinkedList
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
Node<E> node(int index) {
// assert isElementIndex(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;
}
}public boolean remove(Object 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;
}E unlink(Node<E> 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 {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}LinkedList新增节点是不需要预先申请什么空间的，都是动态扩展的，像使用数组的结构的，都是需要新建数组搬移旧数据，其内存占用就多了，插入、删除效率也慢，
vector
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}4.get()方法
ArrayList
检查索引是否越界，不然就从数组里找，简单。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}LinkedList
只能遍历链表，找到对应的索引index，把值返回。对比ArrayList 和Vector 是慢了不少，尤其是数据量大时
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
// 索引小于现有size的一半，从头找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
// 索引大于现有size的一半，从尾往头找
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}vector
也是基本和ArrayList一致
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}5.contains方法
ArrayList
只能遍历数组找
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object 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;
}LinkedList
只能遍历链表找，其效率和ArrayList半斤八两
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}Vector
除了加个synchronized，能有什么特别。。
public boolean contains(Object o) {
return indexOf(o, 0) >= 0;
}
public synchronized int indexOf(Object o, int index) {
if (o == null) {
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}大致都是以源码的角度进行分析，有什么不对，多多指教。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
