- 1、ArrayList、linkedList、Vector异同点
- 2、核心源码解析
- 2.1、ArrayList核心源码解析
- 2.1.1、ArrayList数据结构
- 2.1.2、ArrayList的add(E e)方法
- 2.1.3、ArrayList的get(int index)方法
- 2.1.4、ArrayList的remove(int index)方法
- 2.1.5、ArrayList的set(int index, E element)方法
- 2.2、linkedList核心源码解析
- 2.2.1、数据结构
- 2.2.2、linkedList的add(E e)方法
- 2.2.3、linkedList的get(int index)方法
- 2.2.4、linkedList的remove(int index)方法
- 2.2.5、linkedList的set(int index, E element)方法
- 2.2.6、linkedList的poll()方法
- 2.2.7、linkedList的peek()方法
- 2.3、Vector核心源码解析
- 3、双向链表和双向循环链表
- 3.1、双向链表
- 3.2、双向循环链表
- 存储的元素是有序的、可重复的。
- 底层数据结构： Arraylist 底层使用的是 Object 数组；Vector底层使用的也是Object数组；linkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
- 是否保证线程安全： ArrayList 和 linkedList 都是不同步的，也就是不保证线程安全；Vector中的方法都被synchronized关键字修饰，故线程安全，但性能较低。
- 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n)。因为在进行上述 *** 作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的 *** 作。 ② linkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入；Vector类似ArrayList。
- 是否支持快速随机访问： linkedList 不支持高效的随机元素访问，而 ArrayList、vector 支持。快速随机访问就是通过元素的index快速获取元素对象(对应于get(int index)方法)。
- 内存空间占用： ArrayList、vector 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 linkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱指针以及数据）。
Object数组。
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested **加粗样式**class access
private int size;
有参构造：当initialCapacity为0，会把定义的EMPTY_ELEMENTDATA实例赋值给elementData，大于0时，this.elementData = new Object[initialCapacity]。
无参构造：默认会把定义的DEFAULTCAPACITY_EMPTY_ELEMENTDATA实例赋值给elementData。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//当initialCapacity为0，会把定义的EMPTY_ELEMENTDATA实例赋值给elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.1.2、ArrayList的add(E e)方法
public boolean add(E e) {
//数组扩容方法
ensureCapacityInternal(size + 1); // Increments modCount!!
//往数组添加元素
elementData[size++] = e;
return true;
}
数组扩容方法：ensureCapacityInternal
private void ensureCapacityInternal(int minCapacity) {
//calculateCapacity方法：
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
计算当前数组需要最小大小。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果是刚new ArrayList()创建的实例，则此时数组默认大小是DEFAULT_CAPACITY：10，否则是当前元素个数+1
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
判断当前数组是否需要扩容。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 执行数组扩容条件
//minCapacity：当前数组最小的大小
//elementData.length：当前数组实际大小
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
数组扩容方法:每次扩容后数组大小是原大小的1.5倍。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容代码
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
2.1.3、ArrayList的get(int index)方法
获取指定下标的元素。
public E get(int index) {
//检查下标index是否越界
rangeCheck(index);
//直接返回指定下标元素
return elementData(index);
}
检查下标index是否越界，越界会抛出IndexOutOfBoundsException，即索引越界异常。
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2.1.4、ArrayList的remove(int index)方法
ArrayList删除元素需要移动大量元素，这就是ArrayList增删效率低的原因。
public E remove(int index) {
//检查下标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; // clear to let GC do its work
return oldValue;
}
2.1.5、ArrayList的set(int index, E element)方法
public E set(int index, E element) {
//检查下标index是否越界
rangeCheck(index);
//暂存需要删除的元素，最后需要返回
E oldValue = elementData(index);
//给指定下标赋值
elementData[index] = element;
return oldValue;
}
2.2、linkedList核心源码解析
2.2.1、数据结构
双向链表。
//元素个数
transient int size = 0;
transient Node first;
transient Node last;
linkedList除了实现List接口，还实现了Deque双端队列接口，因此linkedList提供了 *** 作队列相关方法，例如：poll()、pollFirst()、pollLast()、peek()、peekFirst()、peekLast()等；也提供了对栈的相关 *** 作，例如：pop()、push()等方法。
public class linkedList2.2.2、linkedList的add(E e)方法extends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable
新增元素。
public boolean add(E e) {
//在链表尾添加一个节点
linkLast(e);
return true;
}
void linkLast(E e) {
//创建一个l指针指向最后一个元素
final Node l = last;
//新创建一个节点，并把该节点的前驱指针指向l指向的节点，即尾部节点
final Node newNode = new Node<>(l, e, null);
//last指针指向新节点
last = newNode;
if (l == null)
//l指针为空，代表链表为空链表
first = newNode;
else
//非空，把尾节点的next指针指向新的节点
l.next = newNode;
//元素个数加1
size++;
modCount++;
}
新创建的节点结构。
private static class Node2.2.3、linkedList的get(int index)方法{ //元素 E item; //前驱指针 Node next; //后继指针 Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
获取指定小标的元素。
public E get(int index) {
//检查下标是否越界
checkElementIndex(index);
//遍历链表获取指定下标节点的元素
return node(index).item;
}
遍历链表方法：获取指定下标的节点。此处做了优化，不是遍历整个链表，而是判断指定下标是在链表的前半部分还是后半部分，最终最多只会遍历一半链表。
Node2.2.4、linkedList的remove(int index)方法node(int index) { // assert isElementIndex(index); //size >> 1:元素个数/2 if (index < (size >> 1)) { Node x = first; //从链表头部开始遍历 for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; //从链表尾部开始遍历 for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
node()方法如上，遍历链表，找到需要删除的节点。
public E remove(int index) {
//检查下标是否越界
checkElementIndex(index);
return unlink(node(index));
}
unlink():删除指定下标的节点，x指向被删除的节点。
E unlink(Node2.2.5、linkedList的set(int index, E element)方法x) { // assert x != null; //暂存被删除的元素，最后返回 final E element = x.item; //next指针指向被删除节点的下一个节点 final Node next = x.next; //prev指针指向被删除节点的上一个节点 final Node prev = x.prev; if (prev == null) { first = next; } else { //prev指向的节点的后继指针指向next指向的节点，即被删除元素的下一个节点 prev.next = next; //将被删除节点的前驱指针赋值null x.prev = null; } if (next == null) { last = prev; } else { //next指向的节点的前驱指针指向prev指向的节点，即被删除元素的上一个节点 next.prev = prev; //将被删除节点的后继指针赋值null x.next = null; } x.item = null; size--; modCount++; return element; }
给指定下标元素重新赋值。
public E set(int index, E element) {
//检查下标是否越界
checkElementIndex(index);
//遍历链表获取指定下标的节点
Node x = node(index);
E oldVal = x.item;
//新元素覆盖旧元素
x.item = element;
return oldVal;
}
2.2.6、linkedList的poll()方法
获取并删除列表的头(第一个元素)。与remove()相似，区别是remove()方法中如果链表为空，则会抛出NoSuchElementException异常。
public E poll() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
private E unlinkFirst(Nodef) { // assert f == first && f != null; final E element = f.item; final Node next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }
remove()方法删除逻辑。
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
2.2.7、linkedList的peek()方法
获取但不删除列表的头(第一个元素)。
public E peek() {
final Node f = first;
return (f == null) ? null : f.item;
}
2.3、Vector核心源码解析
Vector底层数据结构与ArrayList一样，功能也类似，但比ArrayList功能更丰富。并且可以手动指定扩容大小，capacityIncrement指定。
protected Object[] elementData;
protected int elementCount;
protected 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;
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
Vector中Object数组扩容方法，当capacityIncrement不大于0时，每次扩容原来数组的一倍。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容代码
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、双向链表和双向循环链表
3.1、双向链表
双向链表： 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
双向循环链表： 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）