### LinkedList LinkedList基于双向链表机制实现； 双向链表就是集合中的每个元素都知道其前一个元素和后一个元素的位置 【知识点】 * 顺序访问会非常高效，而随机访问效率比较低 * LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 * LinkedList 实现 List 接口，能对它进行队列操作。 * LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。 * LinkedList 实现了Cloneable接口，即覆盖了函数clone\(\)，能克隆。 * LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。 * LinkedList 是非同步的 ### LinkedList属性 ``` public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ //当前有多少个节点 transient int size = 0; //第一个节点 transient Node<E> first; //最后一个节点 transient Node<E> last; //省略内部类和方法。。 } ``` ### API * **add\(E e\)** 该方法直接将新增的元素放置链表的最后面，然后链表的长度（size）加1，修改的次数（modCount）加1 ``` 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++; } ``` * **add\(int index, E element\)** 指定位置往数组链表中添加元素 1. 检查添加的位置index 有没有小于等于当前的长度链表size，并且要求大于0 2. 如果是index是等于size，那么直接往链表的最后面添加元素，相当于调用add\(E e\)方法 3. 如果index不等于size，则先是索引到处于index位置的元素，然后在index的位置前面添加新增的元素 ``` public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } 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++; } ``` * **get\(int index\)** 首先是判断索引位置有没有越界，确定完成之后开始遍历链表的元素，那么从头开始遍历还是从结尾开始遍历呢，这里其实是要索引的位置与当前链表长度的一半去做对比，如果索引位置小于当前链表长度的一半则从链表头开始往后查找，否则从链表尾开始查找 ``` 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; } } ```