title: java集合之LinkedList
tags: java集合
author: 辰砂
一. LinkedList概述：
List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
注意，此实现不是同步的。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法来“包装”该列表。最好在创建时完成这一操作，以防止对列表进行意外的不同步访问，如下所示：
List list = Collections.synchronizedList(new LinkedList(...));
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的
二.LinkedList的用法 (参考优秀博文)
public class LinkedListTest { public static void main(String[] args) { // 测试LinkedList的API
testLinkedListAPIs() ; // 将LinkedList当作 LIFO(后进先出)的堆栈
useLinkedListAsLIFO(); // 将LinkedList当作 FIFO(先进先出)的队列
useLinkedListAsFIFO();
} /*
* 测试LinkedList中部分API
*/
private static void testLinkedListAPIs() {
String val = null; //LinkedList llist;
//llist.offer("10");
// 新建一个LinkedList
LinkedList llist = new LinkedList(); //---- 添加操作 ----
// 依次添加1,2,3
llist.add("1");
llist.add("2");
llist.add("3"); // 将“4”添加到第一个位置
llist.add(1, "4");
System.out.println("\nTest \"addFirst(), removeFirst(), getFirst()\""); // (01) 将“10”添加到第一个位置。 失败的话，抛出异常！
llist.addFirst("10");
System.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话，抛出异常！
System.out.println("llist.removeFirst():"+llist.removeFirst());
System.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话，抛出异常！
System.out.println("llist.getFirst():"+llist.getFirst());
System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\""); // (01) 将“10”添加到第一个位置。 返回true。
llist.offerFirst("10");
System.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话，返回null。
System.out.println("llist.pollFirst():"+llist.pollFirst());
System.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话，返回null。
System.out.println("llist.peekFirst():"+llist.peekFirst());
System.out.println("\nTest \"addLast(), removeLast(), getLast()\""); // (01) 将“20”添加到最后一个位置。 失败的话，抛出异常！
llist.addLast("20");
System.out.println("llist:"+llist); // (02) 将最后一个元素删除。 失败的话，抛出异常！
System.out.println("llist.removeLast():"+llist.removeLast());
System.out.println("llist:"+llist); // (03) 获取最后一个元素。 失败的话，抛出异常！
System.out.println("llist.getLast():"+llist.getLast());
System.out.println("\nTest \"offerLast(), pollLast(), peekLast()\""); // (01) 将“20”添加到第一个位置。 返回true。
llist.offerLast("20");
System.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话，返回null。
System.out.println("llist.pollLast():"+llist.pollLast());
System.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话，返回null。
System.out.println("llist.peekLast():"+llist.peekLast()); // 将第3个元素设置300。不建议在LinkedList中使用此操作，因为效率低！
llist.set(2, "300"); // 获取第3个元素。不建议在LinkedList中使用此操作，因为效率低！
System.out.println("\nget(3):"+llist.get(2)); // ---- toArray(T[] a) ----
// 将LinkedList转行为数组
String[] arr = (String[])llist.toArray(new String[0]); for(String str:arr) {
System.out.println("str:"+str);
} // 输出大小
System.out.println("size:"+llist.size()); // 清空LinkedList
llist.clear(); // 判断LinkedList是否为空
System.out.println("isEmpty():"+llist.isEmpty()+"\n");
} /**
* 将LinkedList当作 LIFO(后进先出)的堆栈
*/
private static void useLinkedListAsLIFO() {
System.out.println("\nuseLinkedListAsLIFO"); // 新建一个LinkedList
LinkedList stack = new LinkedList(); // 将1,2,3,4添加到堆栈中
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4"); // 打印“栈”
System.out.println("stack:"+stack); // 删除“栈顶元素”
System.out.println("stack.pop():"+stack.pop()); // 取出“栈顶元素”
System.out.println("stack.peek():"+stack.peek()); // 打印“栈”
System.out.println("stack:"+stack);
} /**
* 将LinkedList当作 FIFO(先进先出)的队列
*/
private static void useLinkedListAsFIFO() {
System.out.println("\nuseLinkedListAsFIFO"); // 新建一个LinkedList
LinkedList queue = new LinkedList(); // 将10,20,30,40添加到队列。每次都是插入到末尾
queue.add("10");
queue.add("20");
queue.add("30");
queue.add("40"); // 打印“队列”
System.out.println("queue:"+queue); // 删除(队列的第一个元素)
System.out.println("queue.remove():"+queue.remove()); // 读取(队列的第一个元素)
System.out.println("queue.element():"+queue.element()); // 打印“队列”
System.out.println("queue:"+queue);
}三.源码解读
1.数据结构
LinkedList 是一个双向链表。内部类 Node 是 LinkedList 中的基本数据结构，包含当前节点值，上一个节点得引用，和下个节点的引用。
// 链表中有多少个节点，默认为 0 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) { this.item = element; this.next = next; this.prev = prev;
}
}2.构造方法
比较简单，默认无参构造，和一个 Collection 参数的构造（ 将里面元素按顺序前后连接，修改节点个数，并且操作次数 + 1 ）。
public LinkedList() {
} /**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c 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);
}3.添加方法ADD
// 尾部插入public boolean add(E e) { // 去为节点加
linkLast(e); return true;
}// 将指定的元素防止在链表的尾节点，以前的尾节点变成它前面的节点，如果上个尾节点为null，说明以前是的空链表。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增加
size++;
modCount++;
}
add(int index, E element) public void add(int index, E element) { // 边界校验
checkPositionIndex(index); if (index == size)
linkLast(element); else
linkBefore(element, node(index));
} /**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) { // assert isElementIndex(index);// 双链表可以分别从 头节点 或者尾节点开始遍历，计算它是在前面一半，还是在后面的位置，决定遍历方式。// 这也是LinkedList 为什么要使用双向链表，提升了使用游标操作链表的效率。
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;
}
} /**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) { // assert succ != null;
final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode; if (pred == null)
first = newNode; else
pred.next = newNode;
size++;
modCount++;
}检查索引是否越界，虽然 ListedList 中没有索引概念；
如果 index 和 size 相同，则在尾节点上加上元素；
不相同的话，先去遍历链表查找到索引位置的节点，然后在它的前面插入节点。
1.s->prior=p->prior; 2. p->prior->next=s; 3. s->next=p; 4. p->prior=s;
4.获取元素Get
public E get(int index) {
// 检查索引越界；// 跟上面的一样，查找该索引位置的节点，然后获取它的元素。
checkElementIndex(index);
return node(index).item;
}5.删除元素Remove
public E remove() { return removeFirst();
} // 移除头节点
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f);
} // 参数 f 为头节点// 将头节点指向 next 节点，如果 next节点 为 null 则链表 为 null ，链表大小减 1 ，修改次数记录加 1.
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;
}public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* 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; // 如果本节点为头节点，头节点指向next
if (prev == null) {
first = next;
} else { // 不是头节点，则将前节点和后节点连接起来，然后删掉本节点的引用 GC
prev.next = next;
x.prev = null;
} // 如果是尾节点，则将尾节点指向前节点
if (next == null) {
last = prev;
} else { // 连接，双向链表，双方都有引用，删除自身的引用GC
next.prev = prev;
x.next = null;
} // 删除自身 GC
x.item = null;
size--;
modCount++; return element;
}// 遍历 equals 找出 node，然后调用 unlink(Node<E> x) 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;
}6.更新元素Set
/**
*有索引，第一件事去检查索引是否越界；根据索引找出 node；
*替换 node 的元素，返回 该索引位置 Node 的旧元素的值。
*注意，Set 方法不增加LinkedList 的修改次数
*/public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element; return oldVal;
}7.清空clear()
//释放所有的元素，让他们直接无引用，垃圾回收器发现这些 node 元素是不可达的时候，释放内存。// 数据恢复默认；修改次数记录加一。public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}四、ArrayList和LinkedList比较
ArrayList的实现是基于数组，LinkedList的实现是基于双向链表。
对于随机访问，ArrayList优于LinkedList
对于插入和删除操作，LinkedList优于ArrayList
LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
参考
https://blog.wuwii.com/java-linkedlist.html#more
https://www.cnblogs.com/skywang12345/p/3308807.html