int newCapacity = oldCapacity + (oldCapacity >> 1);
ArrayList 数据新增
上面分析扩容时候已经看到了新增一个元素的具体逻辑，因为底层是数组，所以直接指定下标赋值即可，非常简单。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e; // 直接赋值
return true;
}
但是还有一种新增数据得情况，就是新增时指定了要加入的下标位置。这时逻辑有什么不同呢？
/**
- Inserts the specified element at the specified position in this
- list. Shifts the element currently at that position (if any) and
- any subsequent elements to the right (adds one to their indices).
- @param index index at which the specified element is to be inserted
- @param element element to be inserted
- @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 指定下标开始所有元素后移一位
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}
可以发现这种新增多了关键的一行，它的作用是把从要插入的坐标开始的元素都向后移动一位，这样才能给指定下标腾出空间，才可以放入新增的元素。
比如你要在下标为 3 的位置新增数据100，那么下标为3开始的所有元素都需要后移一位。
由此也可以看到 ArrayList 的一个缺点，随机插入新数据时效率不高。
ArrayList 数据获取
数据下标获取元素值，一步到位，不必多言。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
LinkedList
LinkedList 的底层就是一个链表线性结构了，链表除了要有一个节点对象外，根据单向链表和双向链表的不同，还有一个或者两个指针。那么 LinkedList 是单链表还是双向链表呢？
LinkedList 存储结构
依旧深入 LinkedList 源码一探究竟，可以看到 LinkedList 无参构造里没有任何操作，不过我们通过查看变量 first、last 可以发现它们就是存储链表第一个和最后 一个的节点。
transient int size = 0;
/**
*/
transient Node first;
/**
*/
transient Node last;
/**
- Constructs an empty list.
*/
public LinkedList() {
}
变量 first 和 last 都是 Node 类型，继而查看 Node 源码。
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
可以看到这就是一个典型的双向链表结构，item 用来存放元素值；next 指向下一个 node 节点，prev 指向上一个 node 节点。
LinkedList 数据获取
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
- Returns the (non-null) Node at the specified element index.
*/
// 遍历查找 index 位置的节点信息
Node node(int index) {
// assert isElementIndex(index);
// 这里判断 index 是在当前链表的前半部分还是后半部分，然后决定是从
// first 向后查找还是从 last 向前查找。
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 对象，这个部分要注意的是，查找会首先判断 index 是在当前链表的前半部分还是后半部分，然后决定是从 first 向后查找还是从 last 向前查找。这样可以增加查找速度。从这里也可以看出链表在查找指定位置元素时，效率不高。
LinkedList 数据新增
因为 LinkedList 是链表，所以 LinkedList 的新增也就是链表的数据新增了，这时候要根据要插入的位置的区分操作。
- 尾部插入
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node l = last;
// 新节点，prev 为当前尾部节点，e为元素值，next 为 null，
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
// 目前的尾部节点 next 指向新的节点
l.next = newNode;
size++;
modCount++;
}
默认的 add 方式就是尾部新增了，尾部新增的逻辑很简单，只需要创建一个新的节点，新节点的 prev 设置现有的末尾节点，现有的末尾 Node 指向新节点 Node，新节点的 next 设为 null 即可。
- 中间新增
下面是在指定位置新增元素，涉及到的源码部分。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
// 如果位置就是当前链表尾部，直接尾插
linkLast(element);
else
// 获取 index 位置的节点，插入新的元素
linkBefore(element, node(index));
}
/**
- Inserts element e before non-null Node succ.
*/
// 在指定节点处新增元素，修改指定元素的下一个节点为新增元素，新增元素的下一个节点是查找到得 node 的next节点指向，
// 新增元素的上一个节点为查找到的 node 节点，查找到的 node 节点的 next 指向 node 的 prev 修改为新 Node
void linkBefore(E e, Node succ) {
// assert succ != null;
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
可以看到指定位置插入元素主要分为两个部分，第一个部分是查找 node 节点部分，这部分就是上面介绍的 LinkedList 数据获取部分，
第二个部分是在查找到得 node 对象后插入元素。主要就是修改 node 的 next 指向为新节点，新节点的 prev 指向为查找到的 node 节点，新节点的 next 指向为查找到的 node 节点的 next 指向。查找到的 node 节点的 next 指向的 node 节点的 prev 修改为新节点。
LinkedList 数据删除
依旧查看源码进行分析，源码中看到如果节点是头结点或者尾节点，删除比较简单。我们主要看删除中间一个节点时的操作
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
- Unlinks non-null node x.
*/
E unlink(Node x) {
// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node 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;
}
node(index) 方法依旧是二分查找目标位置，然后进行删除操作。比如要删除的节点叫做 X，删除操作主要是修改 X 节点的 prev 节点的 next 指向为 X 节点的 next 指向，修改 X 节点的 next 节点的 prev 指向为 X 节点的 prev 指向，最后把 X 节点的 prev 和 next 指向清空。如果理解起来有点费劲，可以看下面这个图，可能会比较明白。
扩展
你以为 LinkedList 只是一个 List，其他它不仅实现了 List 接口，还实现了 Deque ，所以它表面上是一个 List，其实它还是一个队列。
public class LinkedList extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
体验一下先进先出的队列。
Queue queue = new LinkedList<>();
queue.add(“a”);
queue.add(“b”);
queue.add(“c”);
queue.add(“d”);
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
// result：
// a
// b
// c
// d
同学可以思考一下这个队列是怎么实现的，其实很简单对不对，就是先进先出嘛，poll 时删除 first 节点不就完事了嘛。
总结
不管是 ArrayList 还是 LinkedList 都是开发中常用的集合类，这篇文章分析了两者的底层实现，通过对底层实现的分析我们可以总结出两者的主要优缺点。
- 遍历，ArrayList 每次都是直接定位，LinkedList 通过 next 节点定位，不相上下。这里要注意的是 LinkedList 只有使用迭代器的方式遍历才会使用 next 节点。如果使用
get ，则因为遍历查找效率低下。 - 新增，ArrayList 可能会需要扩容，中间插入时，ArrayList 需要后移插入位置之后的所有元素。LinkedList 直接修改 node 的 prev, next 指向，LinkedList 胜出。
- 删除，同 2.
- 随机访问指定位置，ArrayList 直接定位，LinkedList 从头会尾开始查找，数组胜出。
综上所述，ArrayList 适合存储和访问数据，LinkedList 则更适合数据的处理，希望你以后在使用时可以合理的选择 List 结构。
#####大家看完有什么不懂的可以在下方留言讨论也可以关注.
#####谢谢你的观看。
#####觉得文章对你有帮助的话记得关注我点个赞支持一下！
链接：https://juejin.im/post/6860260129926250509
最后
自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。
深知大多数Java工程师，想要提升技能，往往是自己摸索成长，自己不成体系的自学效果低效漫长且无助。
因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，不论你是刚入门Java开发的新手，还是希望在技术上不断提升的资深开发者，这些资料都将为你打开新的学习之门！
[外链图片转存中…(img-u4d1F2S2-1715779266883)]
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，不论你是刚入门Java开发的新手，还是希望在技术上不断提升的资深开发者，这些资料都将为你打开新的学习之门！
