当你停下来休息的时候,不要忘记,别人还在奔跑~
LinkedList是一个实现了List接口和Deque接口的双链表。 LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性; LinkedList不是线程安全的，如果想使LinkedList变成线程安全的，可以调用静态类Collections类中的synchronizedList方法：
List list=Collections.synchronizedList(new LinkedList(...));
内部结构
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;
}
}
1.构造方法
空构造方法：
public LinkedList() {
}
用集合参数构造方法：
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
通过上面可以看出和ArrayList的区别：
ArrayList比LinkedList多了一个可以指定容量大小的构造方法。因为LinkedList采用双向链表为数据结构，所以不支持指定连续的一块内存空间。
2.add方法
add(E e) 方法：将元素添加到链表尾部
public boolean add(E e) {
linkLast(e);//这里就只调用了这一个方法
return true;
}
/**
* 链接使e作为最后一个元素。
*/
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++;
}
add(int index,E e)：在指定位置添加元素
public void add(int index, E element) {
checkPositionIndex(index); //检查索引是否处于[0-size]之间
if (index == size)//添加在链表尾部
linkLast(element);
else//添加在链表中
linkBefore(element, node(index));
}
linkBefore方法需要给定两个参数，一个插入节点的值，一个指定的node，所以调用了Node(index)去找到index对应的node
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;
}
}
可以看出 node() 方法这里写的还是挺妙的，不是从头到尾或者从尾到头遍历链表，而是将 index 与 当前链表的一半做对比（右移一位相当于/2），比一半小从头遍历，比一半大从后遍历。对于数据量很大时能省下不少时间。
addAll(Collection c )：将集合插入到链表尾部
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
addAll(int index, Collection c)： 将集合从指定位置开始插入
public boolean addAll(int index, Collection<? extends E> c) {
//1:检查index范围是否在size之内
checkPositionIndex(index);
//2:toArray()方法把集合的数据存到对象数组中
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//3：得到插入位置的前驱节点和后继节点
Node<E> pred, succ;
//如果插入位置为尾部，前驱节点为last，后继节点为null
if (index == size) {
succ = null;
pred = last;
}
//否则，调用node()方法得到后继节点，再得到前驱节点
else {
succ = node(index);
pred = succ.prev;
}
// 4：遍历数据将数据插入
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//创建新节点
Node<E> newNode = new Node<>(pred, e, null);
//如果插入位置在链表头部
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//如果插入位置在尾部，重置last节点
if (succ == null) {
last = pred;
}
//否则，将插入的链表与先前链表连接起来
else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
上面可以看出addAll方法通常包括下面四个步骤：
1.检查index范围是否在size之内
2.toArray()方法把集合的数据存到对象数组中
3.得到插入位置的前驱和后继节点
4.遍历数据，将数据插入到指定位置
可以看出核心方法仍然是node（index）
3.remove 操作
remove(int index) 移除指定位置的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
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;
}
先检查下标是否越界，然后调用 unlink 释放节点。
remove(Object o) 移除指定元素
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;
}
判断要移除的元素是否为 null，然后在遍历链表，找到该元素第一次出现的位置，移除并返回 true。
4.根据位置取数据的方法
get(int index)： 根据指定索引返回数据
public E get(int index) {
//检查index范围是否在size之内
checkElementIndex(index);
//调用Node(index)去找到index对应的node然后返回它的值
return node(index).item;
}
5.根据对象得到索引的方法
int indexOf(Object o)： 从头遍历找
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;
}
总结
篇幅有限 ，只贴主要代码。像其他的常用方法如：getFirst, getLast, removeFirst, removeLast, addFirst, addLast 等都很简单，扫一眼源码就能懂。。。
1.从源码可以看出 LinkedList 是基于链表实现的。
2.在查找和删除某元素时，区分该元素为 null和不为 null 两种情况来处理，说明LinkedList 中允许元素为 null。
3.基于链表实现所以不存在扩容现象。
4.查找时先判断该节点位于前半部分还是后半部分，加快了速度。
5.因为基于链表，所以插入删除极快，查找比较慢。
