首页 > 代码库 > 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     }
linkBefore

  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     }
unlink

  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     }
addAll

  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 }
View Code

  LinkedList是链表的方式,基于结点实现的。使得它在新增、删除时候优于ArrayList,因为只需要更改一下结点上、下结点的指向就可以了,不用移动元素。但是修改、获取的时候比较慢,因为需要遍历集合,执行时间是O(n)。

  这就是二者的基本总结,如果你可以添加对CopyOnWriteArraySet的介绍应该会加分。当然这些都属于基础,答出来是应该的。

后记:最近有跳槽的打算,所以CopyOnWriteArrayList等这些同步集合之后才会去看源码,接下来应该是set和map的分析,set主要是hashSet,有可能有TreeSet,Map主要就是我用到的两个,HashMap、ConcurrentHashMap,可能会有LinkedHashMap和TreeSet。一个集合说一两个应该就够了,毕竟是面试入场题,感觉深度比广度重要。

LinkedList源码分析