将分析以下内容
- 字段
- 构造函数
- 研究插入和删除
- 研究查询
1.首先来看一下LinkedList里面的属性
这个是数组存储元素的总数，相信size()方法大家都用过
transient int size = 0;
下面两个分别是首节点和为节点
transient Node<E> first;
transient Node<E> last;
这里顺便介绍一下数组中存储的基本单位——节点（包括节点内容，上一节点，下一节点）
private static class Node<E> {
E item; //节点存储的内容
Node<E> next; //下一节点
Node<E> prev; //上一节点
//三个参数的构造函数
Node(Node<E> prev, E element, Node<E> next) {...}
}
1.接下来看一下LinkedList里面的构造函数
如果是无参的构造函数，仅仅只会进行初始化
public LinkedList() {}
在介绍下一个构造函数之前，我们先来看一看LinkedList是如何获取元素的
public E get(int index) {
checkElementIndex(index); //判断角标是否越界
return node(index).item;
}
这里我们可以看到需要调用一个node()方法，并且我们可以知道该方法返回的是一个Node对象，接下来我们就看一看该方法
Node<E> node(int index) { //index=34; size=100
//判断查询索引在数组中点左边还是右边
//左边：从第一个节点开始遍历
//右边：从最后一个节点开始遍历
if (index < (size >> 1)) { //index(34) < (size >> 1)(50)
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;
}
}
可以看到node()方法需要从首节点或是尾节点一个一个遍历，所以说当需要查询普遍时不要用LinkedList
接下来让我们来看一看LinkedList的另一构造函数
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
该构造函数传递了一个集合c，需要调用addAll()方法
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
addAll又需要调用addAll的另一个重载函数，注意此时将size也就是当前数组存储元素的总数作为下面函数的index索引
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //检查索引位置是否可做插入，也就比checkElementIndex多了size
Object[] a = c.toArray();
int numNew = a.length;
//长度为空的话什么也不做
if (numNew == 0)
return false;
//记录插入的前置节点和后置节点
Node<E> pred, succ;
//如果未指定角标，将succ设置为空，将pred设置为最后一个节点
//否则将succ设置为指定索引处的节点，pred设置为succ的上一节点
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//循环设置每个节点的前置和后置节点
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//创建新节点，设置节点内容和前置节点
Node<E> newNode = new Node<>(pred, e, null);
//如果上一节点为空，说明为首节点，并设置first
//否则设置前置节点的后置节点，使两个节点相互关联
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//succ为空，说明未指定索引，设置尾节点
//否则关联succ和所插入的最后一个节点
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew; //修改当前数组存储元素的总数
modCount++; //数组修改的次数,该变量在AbstractList定义，不研究
return true;
}
为了方便理解，下面画了一个图，这是从中间插入集合，注意当使用集合初始化LinkedList是直接从末尾差入，这里相当于调用了addAll(int index, Collection<? extends E> c)方法，从指定位置插入集合
在这里插入图片描述
理解了addAll()再来看add()就非常简单了
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++; //数组修改的次数,该变量在AbstractList定义，不研究
}
这里不做细说了，和上面一样，无非就是创建一个节点，维护该节点和前置节点的关系
最后我们来看一下LinkedList是如何实现删除
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
这里可以看到删除的具体逻辑是封装在unlink里面的
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;
x.prev = null;
}
//删除节点为尾节点，设置后置节点为前置节点
//否则设置后置节点的前置节点为删除节点的前置节点
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
在这里插入图片描述
下面是另一个删除方法，这里不过细说
public boolean remove(Object o) {
//循环遍历
//当传入对象为null,==判断
//否则equals判断
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;
}
总结——
通过以上我们明白了LinkedList为什么不适合做查询
- get()方法会循环不断调用node.next或node.prev以找到查询元素，它没有数组的索引，只能通过节点之间的关联进行查询
为什么适合做插入和删除
- 只需要修改节点之间的关联
