文章目录
-
- 一、ArrayList
-
- 流程图：
- 源码：
-
- 1.初始化ArrayList
- 2.add()
- 3.grow()扩容
- 4.疑点
- 二、LinkedList
-
- 流程图：
- 源码：
-
- 1.基本属性
- 2.初始化函数
- 3.add()
- 4.get()
- 5.node()
一、ArrayList
流程图：
源码：
1.初始化ArrayList
其实啥也没干就是初始化一个空数组。
//默认空数组元素，初始化的时候使用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// eg1：初始化ArrayList实例，则elementData={}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
}
2.add()
/**
* 新增元素操作
*
* List list = new ArrayList();
* list.add("a1");
*/
// eg1：第一次新增元素e="a1"
public boolean add(E e) {
/** 确定是否需要扩容，如果需要，则进行扩容操作*/
ensureCapacityInternal(size + 1); // Increments modCount!!
// eg1：size=0，elementData[0]="a1"，然后size自增为1
//todo size++ 注意a++自增是这条语句全部执行完之后才会自增 而++a是先自增才执行这条语句
elementData[size++] = e;
return true;
}
// eg1：第一次新增元素，所以size=0，则：minCapacity=size+1=1
private void ensureCapacityInternal(int minCapacity) {
// eg1：第一次新增元素，calculateCapacity方法返回值为DEFAULT_CAPACITY=10
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 计算ArrayList的容量
*
* 如果elementData数组中没有已存储的元素，则返回默认值10
* 否则，返回minCapacity。
*
* @param elementData 底层存储ArrayList元素的数组
* @param minCapacity ArrayList中的元素个数，注意是新增时的minCapacity是ArrayList中的已有元素个数+1
* @return
*/
// eg1：第一次新增元素，elementData={} minCapacity=1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// eg1：满足if判断，DEFAULT_CAPACITY=10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 确保明确的ArrayList的容量
*
* @param minCapacity ArrayList所需的最小容量
*/
// eg1：第一次新增元素，minCapacity=10
private void ensureExplicitCapacity(int minCapacity) {
// eg1: modCount++后，modCount=1，modCount是用来判断数组是否被修改
modCount++;
/** 如果所需的最小容量大于elementData数组的容量，则进行扩容操作 */
if (minCapacity - elementData.length > 0) { // eg1：10-0=10，满足扩容需求
// eg1：minCapacity=10
grow(minCapacity);
}
}
3.grow()扩容
// MAX_VALUE 的计算方法： https://blog.csdn.net/sunshine77_/article/details/98031174
// MAX_ARRAY_SIZE=2147483639=0111 1111 1111 1111 1111 1111 1111 0111
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// eg1：第一次新增元素，minCapacity=10，即：需要将elementData的0长度扩容为10长度。
private void grow(int minCapacity) {
/** 原有数组elementData的长度*/
int oldCapacity = elementData.length; // eg1：oldCapacity=0
/**
* A >> 1 等于 A/2
* eg: 3 >> 1 = 3/2 = 1
* 4 >> 1 = 4/2 = 2
* ------------------------
* A << 1 等于 A*2
* eg: 3 << 1 = 3*2 = 6
* 4 << 1 = 4*2 = 8
*
* 000100 >> 1 = 000010
* 000100 << 1 = 001000
*/
/** 新增oldCapacity的一半整数长度作为newCapacity的额外增长长度 */
int newCapacity = oldCapacity + (oldCapacity >> 1); // eg1：newCapacity=0+(0>>1)=0
/** 新的长度newCapacity依然无法满足需要的最小扩容量minCapacity，则新的扩容长度为minCapacity */
// todo 这种情况好像只是在空数组的情况下才会发生
if (newCapacity - minCapacity < 0) {
// eg1：newCapacity=10
newCapacity = minCapacity;
}
/** 新的扩容长度newCapacity超出了最大的数组长度MAX_ARRAY_SIZE todo 此时minCapacity的值可能小于或者等于MAX_ARRAY_SIZE或者大于MAX_ARRAY_SIZE*/
if (newCapacity - MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(minCapacity);
}
/** 扩展数组长度为newCapacity，并且将旧数组中的元素赋值到新的数组中 */
// eg1：newCapacity=10， 扩容elementData的length=10
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) { // overflow todo 位溢出
throw new OutOfMemoryError();
}
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
4.疑点
有个不懂的地方，有大佬知道的请帮忙解释一下，不尽感激！就是
这个方法里面的minCapacity什么情况下会小于0呢
？我猜测是
位溢出
了，不知道
对不对
？
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) { // overflow todo 位溢出
throw new OutOfMemoryError();
}
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
二、LinkedList
流程图：
源码：
1.基本属性
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
// 指向最后一个结点
transient Node<E> last;
// Node节点
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;
}
}
2.初始化函数
初始化函数啥也没干
/**
* Constructs an empty list.
*/
public LinkedList() {
}
3.add()
/**
* 新增元素
*/
// eg1: e="a1"
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 将新添加的元素e作为链表的最后一个元素， 并维护进去
*/
// eg1: e="a1"
void linkLast(E e) {
final Node<E> l = last;
// eg1: newNode null<--"a1"-->null
/** 创建一个e的Node节点，前置指向原last节点，后置指向null */
final Node<E> newNode = new Node<>(l, e, null);
/** 将newNode节点赋值为last节点 */
last = newNode;
// eg1: l=null
if (l == null) {
/** 如果是第一个添加的元素，则first指针指向该结点*/
first = newNode; // eg1: first指向newNode
} else {
/** 如果不是第一个添加进来的元素，则更新l的后置结点指向新添加的元素结点newNode*/
l.next = newNode;
}
size++;
modCount++;
}
4.get()
/**
* 查询指定下标index的结点
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* 校验是否越界
*
* @param index
*/
private void checkElementIndex(int index) {
/** index >= 0 && index < size */
if (!isElementIndex(index)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
/**
* Tells if the argument is the index of an existing element.
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
5.node()
请问，这个链表查询的算法是叫
二分遍历
吗？
/**
* Returns the (non-null) Node at the specified element index.
*
* 根据传入的index值，返回对应的结点node
*/
// eg1：index=0
Node<E> node(int index) {
// assert isElementIndex(index);
/** 如果需要获取的index小于总长度size的一半，则从头部开始向后遍历查找 */
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next; // 从first结点向后next查找，直到index下标node，返回node
}
return x;
} else { /** 从尾部开始向前遍历查找 */
Node<E> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev; // 从last结点向前prev查找，直到index下标node，返回node
}
return x;
}
}