LinkedList底层通过双向链表实现，双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。当链表为空的时候first和last都指向null。
看一下LinkedList的属性：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { 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;
和内部类Node，这里Node的泛型使用的是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; } }
还有LinkedList的构造函数，都是比较熟悉的东西，这里不做赘述：
/** * Constructs an empty list. */ 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); }
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;//这里用到的的就是上面linkedList的属性中的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();//这里用到的的就是上面linkedList的属性中的last return l.item; }
下面主要说说LinkedList的增删的方法，这两个方法理解了对于LinkedList的结构就有了比较清晰的理解，其他的方法也大同小异
首先是remove方法，也就是删除元素，指的是删除第一次出现的这个元素, 如果没有这个元素，则返回false；判读的依据是equals方法， 如果equals，则直接删除这个节点Node；由于LinkedList可存放null元素，故也可以删除第一次出现null的元素；注意下这个循环的写法，删除节点用的是unlink方法：
/** * 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 ? get(i)==null : 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; }
unlink方法，在此稍作讲解：
/** * 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的next节点直接成为linkedList的首个节点 if (prev == null) { first = next; } else { //如果删除的不是第一个节点，prev前一个节点的下一个直接连接参数节点x的下一个，就是把X节点跳过了，再把x的节点的前连接删掉，这样不管是从头到尾还是从尾到头，就都找不到x节点了。见下方图示： prev.next = next; x.prev = null; } //和上面的逻辑一样，不再赘述，这里是从另一个方向做的同样的操作 if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } //将要删除的节点里的内容置为null，长度减一，操作次数加一，这个操作次数是干什么用的，下面讲解： x.item = null; size--; modCount++; return element; }
图示：加入要删除2节点，第一个操作就是2的prev也就是1，连到2的next，也就是3上。这样2和3之间的连接就断掉了，但是前面1和2的连接还在，1就有两个next了，就是2和3，这时再把2的前节点删掉，1和2的关系就彻底断了，不管从后向前还是从前向后都走不到2节点了
关于modCount这个字段，是在AbstractList中的，也就是LinkedList的父类的父类，这个字段是和迭代器有关的。摘抄网上的一段解释：
迭代器迭代中表被修改
考虑以下这段代码：
List<Integer> list = new LinkedList<>(); Iterator<Integer> it = list.listIterator(); list.add(1); it.next();
在迭代器创建之后，对表进行了修改。这时候如果操作迭代器，则会得到异常java.util.ConcurrentModificationException。
这样设计是因为，迭代器代表表中某个元素的位置，内部会存储某些能够代表该位置的信息。当表发生改变时，该信息的含义可能会发生变化，这时操作迭代器就可能会造成不可预料的事情。
因此，果断抛异常阻止，是最好的方法。
实际上，这种迭代器迭代过程中表结构发生改变的情况，更经常发生在多线程的环境中。
这种机制的实现就需要记录表被修改，那么思路是使用状态字段modCount。
每当会修改表的操作执行时，都将此字段加1。使用者只需要前后对比该字段就知道中间这段时间表是否被修改。
如linkedList中的头插和尾插函数，就将modCount字段自增：
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; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
迭代器和Node一样也是LinkedList的一个内部类：
private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; //记录下开始的值 private int expectedModCount = modCount;
其中有一个方法是：
//与现在的值比对看判断该集合是否被修改 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
摘抄完毕
还有一个remove方法是入参是下标的，这个没啥好说的，执行删除仍然是unlink方法
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isElementIndex(int index) { return index >= 0 && index < size; }
关于删除的就说到这，还有removeFirst和RemoveLast方法其实基本也是一个套路。没啥说的，自己看一看就行。
------------------------------------------------------------分割线-------------------------------------------------------------------
下面看看新增的方法：
add()方法有两个版本，一个是add(E e)，该方法在LinkedList的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是add(int index, E element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。
先看前面的方法：
/** * 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); //如果index等于list的长度，那么就是是前面的add方法 if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * 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++; } /** * Returns the (non-null) Node at the specified element index. */ //根据Index找到要插入对象的位置，如果index小于size的一半（size >> 1），那就从前往后找。 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 { //根据Index找到要插入对象的位置，如果index大于size的一半（size >> 1），那就从前往后找。 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
再看向中间插入元素的方法，上代码：
/** * 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); //如果index等于list的长度，那么就是是前面的add方法 if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * 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++; } /** * Returns the (non-null) Node at the specified element index. */ //根据Index找到要插入对象的位置，如果index小于size的一半（size >> 1），那就从前往后找。 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 { //根据Index找到要插入对象的位置，如果index大于size的一半（size >> 1），那就从前往后找。 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
以上。
