#yyds干货盘点# Collection - LinkedList源码解析 _linkedlist

努力尽今夕，少年犹可夸。这篇文章主要讲述#yyds干货盘点# Collection - LinkedList源码解析相关的知识，希望能为你提供帮助。
Collection - LinkedList源码解析
概述
LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类(它是个接口名字)。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)有着更好的性能。
LinkedLists实现
底层数据结构
LinkedList底层通过双向链表实现，本节将着重讲解插入和删除元素时双向链表的维护过程，也即是之间解跟List接口相关的函数，而将Queue和Stack以及Deque相关的知识放在下一节讲。双向链表的每个节点用内部类Node表示。LinkedList通过first和last?引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候first和last?都指向null。

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;

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;

构造函数

/**
* Constructs an empty list.
*/
public LinkedList()

/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collections
* iterator.
*
* @paramc the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection< ? extends E> c)
this();
addAll(c);

getFirst(), getLast()
获取第一个元素，和获取最后一个元素:

/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst()
final Node< E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;

/**
* Returns the last element in this list.
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast()
final Node< E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;

removeFirest(), removeLast(), remove(e), remove(index)
【#yyds干货盘点# Collection - LinkedList源码解析】remove()方法也有两个版本，一个是删除跟指定元素相等的第一个元素remove(Object o)，另一个是删除指定下标处的元素remove(int index)。

/**
* Removes the first occurrence of the specified element from this list,
* if it is present.If this list does not contain the element, it is
* unchanged.More formally, removes the element with the lowest index
* @code i such that
* < tt> (o==null& nbsp; ?& nbsp; get(i)==null& nbsp; :& nbsp; o.equals(get(i)))< /tt>
* (if such an element exists).Returns @code true if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return @code true if this list contained the specified element
*/
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;

/**
* 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;

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; // GC
size--;
modCount++;
return element;

/**
* Removes the element at the specified position in this list.Shifts any
* subsequent elements to the left (subtracts one from their indices).
* Returns the element that was removed from the list.
*
* @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));

/**
* Removes and returns the first element from this list.
*
* @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);

/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node< E> f)
// assert f == first & & f != null;
final E element = f.item;
final Node< E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;