首页 > 代码库 > LinkedList源码分析
LinkedList源码分析
1.类说明
实现了List和Deque接口的双向链表。实现了List的所有操作，允许所有元素(包含null)。
所有的操作基本都是可以双向进行的，对列表的索引操作会从列表的开头或者结尾开始，取决于那边比较接近该索引的位置。
LinkedList也不是线程安全的，如果需要有多线程对此集合进行操作的场景，并且其中一个会修改该集合的结构(只包含删除和新增操作，不包括设值操作)时，都必须要保证该集合的同步性。我们可以使用Collections.synchronizedList(new LinkedList(...))这个方法来获取一个同步集合。
快速失败机制和ArrayList一样，不再赘述。
2.继承和实现
该类继承了AbstractSequentialList，实现了List、Deque、Cloneable和Serializable。
AbstractSequentialList：大致意思就是说如果一个list是以"顺序访问"作为其数据存储(比如Linkedlist)，可以继承该类，它会为你提供一个骨架实现，从而最大限度地减少实现此接口所需的工作。对于随机访问数据（如ArrayList），应该优先使用AbstractList，而不是先使用此类。如果我们自己要实现一个列表，只需要扩展此类，并提供listIterator和size方法的实现即可。对于不可修改的列表，只需要实现列表迭代器的hasNext、next、hasPrevious、previous和index方法即可。对于可修改的列表，我们需要再另外实现列表迭代器的set方法。对于可变大小的列表，需要再另外实现列表迭代器的remove和add方法。从某种意义上说，此类与在列表的列表迭代器上实现“随机访问”方法（get(int index)、set(int index, Object element)、set(int index, Object element)、add(int index, Object element) 和 remove(int index)）的AbstractList类相对立，而不是其他关系(虽然是继承AbstractList)。当前我们应该不会自己去创建list。
Deque：double-ended queue，就是双端队列，支持双端插入和删除，实现了Queue(队列-FIFO，栈-LIFO)，可以插入null值但是非常不建议，因为很多方法都会把null值当做是空队列的特定返回值。
List、Cloneable和Serializable不再赘述。
3.成员变量
int size：该集合对应的元素数量
Node<E> first/last：分别指向该集合的第一个元素和最后一个元素
modCount：结构性修改的次数
4.构造方法
1 public LinkedList() { 2 // 生成一个空List集合 3 } 4 5 // 将c集合中的数据初始化到List集合中 6 // 如果c为null，会抛出空指针异常 7 public LinkedList(Collection<? extends E> c) { 8 this(); 9 // 下面介绍成员方法时介绍 10 addAll(c); 11 }
5.成员方法
首先要了解LinkedList是基于什么实现的，再来看这些方法会容易很多。LinkedList主要是基于结点(Node)实现的，如图1所示：
图1 Node类
通过这个Node我们就能很好的了解以下的一些方法了。
List操作：
void linkFirst(E e)：将该元素设置为集合第一个元素，首元素prev为null，linkedList.addFirst(E e)调用该方法
void linkLast(E e)：将该元素设置为集合最后一个元素，尾元素next为null，LinkedList的addLast(E e)、add(E e)和add(E e,int index)调用该方法
void linkBefore(E e,Node<E> succ)：将e元素插入succ结点之前，主要是LinkedList的add(E e)调用此方法，操作如下
1 void linkBefore(E e, Node<E> succ) { 2 // assert succ != null;判断succ不能为空 3 // 取出succ的前一个node 4 final Node<E> pred = succ.prev; 5 // 新建一个新结点，将e的前结点设置为succ的前结点，将e的后结点设置为succ 6 final Node<E> newNode = new Node<>(pred, e, succ); 7 // 将succ的前结点设置为新建的结点 8 succ.prev = newNode; 9 // 如果succ的前结点为空，则succ为集合头结点，将新结点设置为头结点 10 if (pred == null) 11 first = newNode; 12 else 13 pred.next = newNode;// 不然的话将pred的后结点设置为新结点，这样就算插入完成了 14 // 增加集合大小 15 size++; 16 modCount++; 17 }
E unlinkFirst(Node<E> f)：删除并返回该集合的首元素，需要确保f元素是首元素并且不为null，linkedList的removeFirst()、poll()方法和pollFirst()调用该方法
E unlinkLast(Node<E> l)：删除并返回该集合的尾元素，需要确保l元素是尾元素并且不为null，linkedList的removeLast()、pollLast()调用该方法
E unlink(Node<E> x)：删除x结点并返回x的属性值，确保x不为空，linkedList的remove(Object o)、remove(int index)、removeLastOccurrence(Object o)调用此方法，操作如下
1 E unlink(Node<E> x) { 2 final E element = x.item; 3 final Node<E> next = x.next; 4 final Node<E> prev = x.prev; 5 // 首结点的判断 6 if (prev == null) { 7 first = next; 8 } else { 9 prev.next = next; 10 x.prev = null; 11 } 12 // 尾结点的判断 13 if (next == null) { 14 last = prev; 15 } else { 16 next.prev = prev; 17 x.next = null; 18 } 19 20 x.item = null; 21 size--; 22 modCount++; 23 return element; 24 }
E getFirs()、E getLast()、E removeFirst()、E removeLast()、void addFirst(E e)、void addLast(E e)、int size()、boolean add(E e)方法相对简单，不再赘述
boolean contains(Object o)：判断o是否存在该集合中，其中的indexOf(Object o)方法是返回o在集合中的第一次出现的位置，没有则返回-1
boolean remove(Object o)：删除集合中第一次出现的o元素，o可以是null
boolean addAll(Collection<? extends E> c)：将集合c全部添加到该list尾部，如果c为空，抛空指针异常
boolean addAll(int index, Collection<? extends E> c)：在指定的index位插入c集合，步骤如下：
1 public boolean addAll(int index, Collection<? extends E> c) { 2 // 检查index的合理性，必须属于[0,size]，否则抛出IndexOutOfBoundsException 3 checkPositionIndex(index); 4 Object[] a = c.toArray(); 5 int numNew = a.length; 6 if (numNew == 0) { 7 return false; 8 } 9 // succ-要被插入的结点，也就是从这个节点之后开始新增，pred-上一个结点 10 Node<E> pred, succ; 11 // 如果index==size，上一个结点就是尾元素 12 if (index == size) { 13 succ = null; 14 pred = last; 15 } else { 16 // 如果index < (size >> 2)，从头元素开始遍历集合，不然从尾元素开始遍历 17 succ = node(index); 18 pred = succ.prev; 19 } 20 for (Object o : a) { 21 @SuppressWarnings("unchecked") 22 E e = (E) o; 23 // 每个的结点next为空，默认为尾结点 24 Node<E> newNode = new Node<>(pred, e, null); 25 // pred为空表示是头结点，将第一个生成的结点作为第一个结点 26 if (pred == null) 27 first = newNode; 28 else 29 pred.next = newNode; 30 // 为下一次循环做准备 31 pred = newNode; 32 } 33 // 尾结点后续处理 34 if (succ == null) { 35 last = pred; 36 } else { 37 pred.next = succ; 38 succ.prev = pred; 39 } 40 size += numNew; 41 modCount++; 42 return true; 43 }
void clear()清空集合、E get(int index)获取index位置的结点的值(item)、E set(int index, E element)将e元素设置到index对应的结点、add(int index, E element)在index之后新增e元素结点、E remove(int index)删除index位对应的结点，相对简单，不再赘述。
Node<E> node(int index)：属于工具方法，获取index结点对应的值，要确保index值得合理性。源码的if判断是一个精髓，如果index < (size >> 1)，从头开始遍历，否则从尾部开始遍历，效率最大化
int indexOf(Object o)和int lastIndexOf(Object o)：二者都是查询元素所在位置，不同的是一个从头开始，一个从尾开始
Queue(FIFO)操作:
E peek()：获取集合的第一个元素值，不会将该数据从集合中删除，不存在返回null
E element()：也是获取集合第一个元素，与上述方法基本相同，只是如果不存在会抛出NoSuchElementException
E poll()：取出第一个元素，会将该数据从集合中删除，不存在返回null
E remove()：移除第一个元素，于poll基本相同，如果不存在该元素会抛出NoSuchElementException
boolean offer(E e)：向集合末尾追加元素，成功返回true
Deque(双端队列，既可以FIFO，也可以LIFO，看实现)操作：
boolean offerFirst(E e)、boolean offerLast(E e)：向集合头部/尾部追加元素，成功返回true
E peekFirst()、E peekLast()：获取但是不取出头/尾元素
E pollFirst()、E pollLast()：获取并移除头/尾元素
void push(E e)：向集合头部添加元素
E pop()：获取并移除头元素，不存在抛出NoSuchElementException
boolean removeFirstOccurrence(Object o)、boolean removeLastOccurrence(Object o)：删除第一个/最后一个元素为o的结点
Object clone()：对该集合的浅克隆，只是克隆了引用地址，并不会对元素克隆(会有指向该元素的引用)
LinkedList<E> superClone()：调用父类clone方法，一般会成功，如果JVM出异常，会抛出InternalError
Object[] toArray()：将集合变成数组并返回，返回的数组是安全的，并且与原来的集合没有任何关联，也就是给这个数组重新分配了内存
T[] toArray(T[] a)：将集合变成指定类型的数组，跟ArrayList的基本一致，只是多了个从结点取值的操作
void writeObject(java.io.ObjectOutputStream s)、void readObject(java.io.ObjectInputStream s)：集合序列化/反序列化的过程
Iterator<E> descendingIterator()：返回一个从尾部到头部的迭代器，和listIterator是反向的
6.jdk1.8新方法
Spliterator<E> spliterator()：获取一个并行遍历集合的迭代器(splitable iterator可分割迭代器)，详见：https://segmentfault.com/q/1010000007087438
7.ArrayList和LinkedList的区别
由于最近有跳槽的打算，所以经历了一些面试。面试的开场问题一般都是谈谈你了解的集合，一般我们用的集合有三种，List、Set和Queue，均是继承于Collection，具体可以展开很多。我在这里就大致归纳一下这二者的区别，如下：
ArrayList是数组大小可变的实现，是基于数组实现的。这也使得它在获取、修改元素的时候很快(O(1))。新增的情况分为两种吧，如果是在集合末尾新增，ArrayList比LinkedList要快，如果是在集合中间插入元素，则LinkedList比ArrayList快，因为ArrayList多了一步将元素移位的操作，相对耗时，删除同理。插入的测试可以看以下代码
1 public class AddTest { 2 public static void main(String[] args) { 3 List<String> arrList = new ArrayList<String>(); 4 List<String> linkList = new LinkedList<String>(); 5 long startTime = System.currentTimeMillis(); 6 // ArrayList执行1000000次插入，这种插入属于在集合末尾插入 7 for (int i = 0; i < 1000000; i++) { 8 arrList.add("123"); 9 } 10 long endTime = System.currentTimeMillis(); 11 System.out.println("arr add time:" + (endTime - startTime));//arr add time:14 12 // LinkedList执行1000000插入，这种插入属于在集合末尾插入 13 startTime = System.currentTimeMillis(); 14 for (int i = 0; i < 1000000; i++) { 15 linkList.add("123"); 16 } 17 endTime = System.currentTimeMillis(); 18 System.out.println("link add time:" + (endTime - startTime));//link add time:61 19 // 不停的在index为100的位置新增 20 startTime = System.currentTimeMillis(); 21 for (int i = 0; i < 100; i++) { 22 arrList.add(100, "234"); 23 } 24 endTime = System.currentTimeMillis(); 25 System.out.println("arr index add time:" + (endTime - startTime));//arr index add time:49 26 // 不停的在index为100的位置新增 27 startTime = System.currentTimeMillis(); 28 for (int i = 0; i < 100; i++) { 29 linkList.add(100, "234"); 30 } 31 endTime = System.currentTimeMillis(); 32 System.out.println("link index add time:" + (endTime - startTime));//link index add time:0 33 } 34 }
LinkedList是链表的方式，基于结点实现的。使得它在新增、删除时候优于ArrayList，因为只需要更改一下结点上、下结点的指向就可以了，不用移动元素。但是修改、获取的时候比较慢，因为需要遍历集合，执行时间是O(n)。
这就是二者的基本总结，如果你可以添加对CopyOnWriteArraySet的介绍应该会加分。当然这些都属于基础，答出来是应该的。
后记：最近有跳槽的打算，所以CopyOnWriteArrayList等这些同步集合之后才会去看源码，接下来应该是set和map的分析，set主要是hashSet，有可能有TreeSet，Map主要就是我用到的两个，HashMap、ConcurrentHashMap，可能会有LinkedHashMap和TreeSet。一个集合说一两个应该就够了，毕竟是面试入场题，感觉深度比广度重要。
LinkedList源码分析