一、LinkedList简介
LinkedList继承了AbstractSequentialList类，实现了List，Deque,Cloneable,Serializable接口。
二、LinkedList源码分析
LinkedList底层是一个双向链表，支持大量的随机新增，删除操作，较ArrayList不支持大量随机的数据访问。
2.1底层实现--双向链表
/**
* 内部类，链的节点
* item节点元素
* next后继
* prev前驱
* */
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
/**
* prev前驱
* element当前元素
* next后继
* */
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
2.2成员变量
/**
* 链的大小/长度
* */
transient int size = 0;
/**
* 指向第一个节点
* (first == null && last == null) ||
* (first.prev == null && first.item != null)
*
* */
transient Node<E> first;
/**
* 指向最后一个节点
* (first == null && last == null) ||
* (last.next == null && last.item != null)
*
* */
transient Node<E> last;
2.3构造方法
LinkedList提供了两个构造方法：
1.public LinkedList()；构造一个空的list
2.public LinkedList(Collection<? extends E> c) ;构造一个包含指定元素集的list;
/**
* 构造一个空的list
* */
public LinkedList() {
}
/**
* 构造一个包含指定元素集的list,该元素集按照迭代器的输出系列进行排列
* */
public LinkedList(Collection<? extends E> c) {
//先构造一个空的list
this();
//再进行添加
addAll(c);
}
2.4新增方法
LinkedList提供了如下几个新增方法：
1.public void addFirst(E e)；在列表头部插入指定元素e
2.public void addLast(E e)；在列表尾部插入指定元素e
3.public boolean add(E e) ；在列表尾部插入指定元素e,返回boolean类型值true;该方法和#addLast方法类似
4.public boolean addAll(Collection<? extends E> c)；追加元素集c到列表尾部
5.public boolean addAll(int index, Collection<? extends E> c)；添加元素集c到指定位置
6.public void add(int index, E element)；添加元素e到指定位置
源码解析：
/**
* 在链表头部插入一个元素
*
* @param e 待插入元素
*/
public void addFirst(E e) {
//指向头部操作
linkFirst(e);
}
/**
* 在链表尾部追加一个元素e
*
* <p>This method is equivalent to {@link #add}.
* equivalent等价的
* @param e 待插入元素
*/
public void addLast(E e) {
linkLast(e);
}
/**
* 追加指定元素到链表尾部,该方法与addLast方法是相等的
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
*
* 追加元素集到链表尾，
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the specified
* collection's iterator. The behavior of this operation is undefined if
* the specified collection is modified while the operation is in
* progress. (Note that this will occur if the specified collection is
* this list, and it's nonempty.)
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
*
* 添加指定元素集到指定位置
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
//检查位置
checkPositionIndex(index);
//元素集转成对象数组
Object[] a = c.toArray();
//数组长度
int numNew = a.length;
if (numNew == 0)
return false;
//前驱和后继节点
Node<E> 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);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
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) {
/**位置检查*/
checkPositionIndex(index);
//如果下标等于链长，则将元素插入链尾
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
其中比较重要的操作链表的方法：
1.private void linkFirst(E e)；指向第一个元素之前（即元素e作为第一个节点）
2.void linkLast(E e) ；在最后一个元素之后（即元素e作为尾节点）
3.void linkBefore(E e, Node<E> succ)；在非空元素succ前插入元素e
源码分析：
/**
* 插入第一个元素之前
* */
private void linkFirst(E e) {
// 得到第一个元素
final Node<E> f = first;
// 新的节点，前驱为空，后继为当前节点的第一个元素
final Node<E> newNode = new Node<>(null, e, f);
// 新的第一个元素
first = newNode;
// 如果之前第一个元素为空，则最后一个元素为新的节点元素，否则之前元素的前驱为当前元素
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* 在最后一个元素之后插入一个元素
* */
void linkLast(E e) {
// 最后一个元素
final Node<E> l = last;
// 当前节点，该元素的前驱是l,该元素的后继是null
final Node<E> newNode = new Node<>(l, e, null);
// 新的最后一个元素是当前新的元素
last = newNode;
// 如果之前最后一个元素为空，则第一个元素为当前元素，否则，原来最后一个元素的后继指向该元素
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/**
* 在一个非空元素succ前插入一个元素e
*
* */
void linkBefore(E e, Node<E> succ) {
// succ不为空，断言机制
// assert succ != null;
// 元素succ的前驱节点
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
// 元素succ的前驱指向newNode
succ.prev = newNode;
// 如果前驱节点为空，则newNode作为第一个节点
// 否则前驱节点的后继指向newNode
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
2.5移除方法
LinkedList提供了如下几个移除方法：
1.public E remove(int index)；移除index处元素，并返回该元素
2.public E remove() ；移除头部元素，并返回该被移除的元素，如果列表为空，则抛出异常
3.public E removeFirst()；移除头部元素，并返回该被移除的元素，如果列表为空，则抛出异常
源码分析：
/**
* 移除index处的元素，并返回该元素
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
/*下标检查*/
checkElementIndex(index);
return unlink(node(index));
}
/**
* 移除头部元素，返回列表头部元素，如果列表为空，则抛出异常
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E remove() {
//返回列表第一个元素
return removeFirst();
}
/**
* 移除列表第一个元素，并返回该元素，如果列表为空，则抛出异常
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
//指向列表头部元素
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
//解链
return unlinkFirst(f);
}
其中操作链表的方法：
1.E unlink(Node<E> x)；将非空元素X解链
源码分析：
/**
* 解链
* Unlinks non-null node x.
*/
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;
//如果前驱为空，则首元素为x后继
//否则前驱的后继指向x的后继，x的前驱指向null
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
//如果后继为空，则尾元素为x的前驱
//否则，后继的前驱指向x的前驱，x的后继指向空
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//链表长度减一
x.item = null;
size--;
modCount++;
return element;
}