LinkedList源码分析

１元素的存储结构

在LinkedList中，每一个元素都是Node存储，Node拥有一个存储值的item与一个前驱prev和一个后继next，如下：

// 典型的链表结构 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继承关系如下图:

３相关属性

// LinkedList节点个数 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; //指向头结点

从源码中我们可以看出，LinkedList采用双链表的结构进行存储

４LinkedList构造函数

public LinkedList(Collection<? extends E> c) { this(); // 将集合添加到链表中去 addAll(c); } public boolean addAll(Collection<? extends E> c) { // 从链表尾巴开始集合中元素 return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { // 1.添加位置的下标的合理性检查 checkPositionIndex(index); // 2.将集合转换为Object[]数组对象 Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; // 3.得到插入位置的前继节点和后继节点 Node<E> pred, succ; if (index == size) { // 从尾部添加的情况：前继节点是原来的last节点；后继节点是null succ = null; pred = last; } else { // 从指定位置（非尾部）添加的情况:前继节点就是index位置的节点，后继节点是index位置的节点的前一个节点 succ = node(index); pred = succ.prev; } // 4.遍历数据，将数据插入 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置为最后一个插入的元素 last = pred; } else { // 如果不是从尾部插入的，则把尾部的数据和之前的节点连起来 pred.next = succ; succ.prev = pred; } size += numNew; // 链表大小+num modCount++; // 修改次数加1 return true; }

5主要方法

5.1 add(E e)方法

// 作用：将元素添加到链表尾部 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节点也为需要插入的节点。（也就是说：该节点既是头节点first也是尾节点last） first = newNode; else // 不是空链表的情况：将原来的尾部节点（现在是倒数第二个节点）的next指向需要插入的节点 l.next = newNode; size++; // 更新链表大小和修改次数，插入完毕 modCount++; }

5.2 add(int index, E element)方法

// 作用：在指定位置添加元素 public void add(int index, E element) { // 检查插入位置的索引的合理性 checkPositionIndex(index); if (index == size) // 插入的情况是尾部插入的情况：调用linkLast（）解释如上。 linkLast(element); else // 插入的情况是非尾部插入的情况（中间插入）：linkBefore（）见下面。 linkBefore(element, node(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } 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的前节点，后接点是succ节点 succ.prev = newNode; // 更新插入位置（succ）的前置节点为新节点 if (pred == null) // 如果pred为null，说明该节点插入在头节点之前，要重置first头节点 first = newNode; else // 如果pred不为null，那么直接将pred的后继指针指向newNode即可 pred.next = newNode; size++; modCount++; }

5.3 get(int index)方法

public E get(int index) { // 元素下表的合理性检查 checkElementIndex(index); // node(index)真正查询匹配元素并返回 return node(index).item; } // 作用：查询指定位置元素并返回 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; }

5.4 remove(int index)方法

// 返回元素在链表中的索引，如果不存在则返回-1 public int indexOf(Object o) { int index = 0; // 如果元素为null，进行如下循环判断 if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { // 元素不为null.进行如下循环判断 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }

6 Duque接口

6.1 addFirst(E e)方法

// 作用：在链表头插入指定元素 public void addFirst(E e) { linkFirst(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; // 头尾元素都是e else f.prev = newNode; // 否则就更新原来的头元素的prev为新元素的地址引用 size++; modCount++; }

5.2 addLast(E e)方法

// 作用：在链表尾部添加元素e public void addLast(E e) { // 上面已讲解过，参考上面。add()方法 linkLast(e); }

6.3 push(E e)方法

// 作用:往链表头部添加元素e public void push(E e) { addFirst(e); }

6.4 getFirst()方法

// 作用：得到头元素 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }

6.5 getLast()方法

// 作用：得到尾部元素 public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }

6.6 peek()方法

// 作用：返回头元素，并且不删除。如果不存在也不错，返回null public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; }

6.7 peekFirst()方法

// 作用：返回头元素，并且不删除。如果不存在也不错，返回null public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; }

6.8 peekLast()方法

// 作用：返回尾元素，如果为null,则就返回null public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; }

6.9 poll()方法

// 作用：返回头节点元素，并删除头节点。并将下一个节点设为头节点。 public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }

6.10 pollFirst()方法

// 作用：返回头节点，并删除头节点，并将下一个节点设为头节点。 public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }

6.11 pollLast()方法

// 作用：返回尾节点，并且将尾节点删除，并将尾节点的前一个节点置为尾节点 public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); }

6.12 pop()方法

// 作用：删除头节点，如果头结点为null.则抛出异常 public E pop() { return removeFirst(); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }

push(E e)方法

// 作用：将元素添加到头部 public void push(E e) { addFirst(e); } public void addFirst(E e) { linkFirst(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++; }

后记

其中的关于序列化、Iterator这两块，与ArrayList的实现也是不尽相同的，故在此可参考ArrayList中的解析。