Java集合源码学习（三）LinkedList分析

2021-08-22 02:29:59

前面学习了ArrayList的源码，
数组是顺序存储结构，存储区间是连续的，占用内存严重，故空间复杂的很大。
但数组的二分查找时间复杂度小，为O(1)，数组的特点是寻址容易，插入和删除困难。
今天学习另外的一种常用数据结构LinkedList的实现，
LinkedList使用链表作为存储结构，链表是线性存储结构，在内存上不是连续的一段空间，
占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N），链表的特点是寻址困难，插入和删除容易。
所有的代码都基于JDK 1.6。

>>关于LinkedList

LinkedList继承了AbstractSequentialList，实现了List，Deque，Cloneable，Serializable 接口，

（1）继承和实现

继承AbstractSequentialList类，提供了相关的添加、删除、修改、遍历等功能。
实现List接口，提供了相关的添加、删除、修改、遍历等功能。
实现 Deque 接口，即能将LinkedList当作双端队列使用，可以用做队列或者栈
实现了Cloneable接口，即覆盖了函数clone()，能被克隆复制，
实现java.io.Serializable接口，LinkedList支持序列化，能通过序列化传输。

（2）线程安全

LinkedList是非同步的，即线程不安全，如果有多个线程同时访问LinkedList，可能会抛出ConcurrentModificationException异常。

1
2
3
4
final void checkForComodification() {
        if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }

　　代码中，modCount记录了LinkedList结构被修改的次数。Iterator初始化时，expectedModCount=modCount。任何通过Iterator修改LinkedList结构的行为都会同时更新expectedModCount和modCount，使这两个值相等。通过LinkedList对象修改其结构的方法只更新modCount。所以假设有两个线程A和B。A通过Iterator遍历并修改LinkedList，而B，与此同时，通过对象修改其结构，那么Iterator的相关方法就会抛出异常

>>双向链表结构

 

和普通的链表不同，双向链表每个节点不止维护指向下一个节点的next指针，还维护着指向上一个节点的previous指针。
（1）内部实现

LinkedList内部使用Entry<E>来封装双向循环链表结点。
LinkedList头结点的定义:

1
2
3
4
//头结点的定义
    private transient Entry<E> header = new Entry<E>(null, null, null);
    //链表的实际长度
    private transient int size = 0;

　　Entry是一个静态内部类，

1
2
3
4
5
6
7
8
9
10
11
private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;
 
    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
    }

　　

（2）构造函数

LinkedList内部提供了两个构造函数，

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
    * 初始化一个空的list，可以理解为一个双向循环链表
    */
   public LinkedList() {
       header.next = header.previous = header;
   }
   /**
    * 使用指定的collection构造一个list
    */
   public LinkedList(Collection<? extends E> c) {
   this();
   addAll(c);
   }

　　

 

>>常用方法

（1）遍历方式

LinkedList支持多种遍历方式。建议不要采用随机访问的方式去遍历LinkedList，而采用逐个遍历的方式。
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。

for(Iterator iter = list.iterator(); iter.hasNext();)
    iter.next();

(02) 通过快速随机访问遍历LinkedList

int size = list.size();
for (int i=0; i<size; i++) {
    list.get(i);        
}

(03) 通过另外一种for循环来遍历LinkedList

for (Integer integ:list) 
    ;

(04) 通过pollFirst()来遍历LinkedList

while(list.pollFirst() != null)
    ;

(05) 通过pollLast()来遍历LinkedList

while(list.pollLast() != null)
    ;

(06) 通过removeFirst()来遍历LinkedList

try {
    while(list.removeFirst() != null)
        ;
} catch (NoSuchElementException e) {
}

(07) 通过removeLast()来遍历LinkedList

try {
    while(list.removeLast() != null)
        ;
} catch (NoSuchElementException e) {
}

 

遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，应该使用第3种遍历方式。
链表的特点是内存空间不连续，插入和删除简单，寻址的时间复杂度较高，随机访问去遍历LinkedList的效率是最低的。

（2）常用方法（从API摘的）

boolean add(E e) 
将指定元素添加到此列表的结尾。 
void add(int index, E element) 
在此列表中指定的位置插入指定的元素。 
boolean addAll(Collection<? extends E> c) 
添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。 
boolean addAll(int index, Collection<? extends E> c) 
将指定 collection 中的所有元素从指定位置开始插入此列表。 
void addFirst(E e) 
将指定元素插入此列表的开头。 
void addLast(E e) 
将指定元素添加到此列表的结尾。 
void clear() 
从此列表中移除所有元素。 
Object clone() 
返回此 LinkedList 的浅表副本。 
boolean contains(Object o) 
如果此列表包含指定元素，则返回 true。 
Iterator<E> descendingIterator() 
返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。 
E element() 
获取但不移除此列表的头（第一个元素）。 
E get(int index) 
返回此列表中指定位置处的元素。 
E getFirst() 
返回此列表的第一个元素。 
E getLast() 
返回此列表的最后一个元素。 
int indexOf(Object o) 
返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。 
int lastIndexOf(Object o) 
返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。 
ListIterator<E> listIterator(int index) 
返回此列表中的元素的列表迭代器（按适当顺序），从列表中指定位置开始。 
boolean offer(E e) 
将指定元素添加到此列表的末尾（最后一个元素）。 
boolean offerFirst(E e) 
在此列表的开头插入指定的元素。 
boolean offerLast(E e) 
在此列表末尾插入指定的元素。 
E peek() 
获取但不移除此列表的头（第一个元素）。 
E peekFirst() 
获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 
E peekLast() 
获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 
E poll() 
获取并移除此列表的头（第一个元素） 
E pollFirst() 
获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 
E pollLast() 
获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。 
E pop() 
从此列表所表示的堆栈处弹出一个元素。 
void push(E e) 
将元素推入此列表所表示的堆栈。 
E remove() 
获取并移除此列表的头（第一个元素）。 
E remove(int index) 
移除此列表中指定位置处的元素。 
boolean remove(Object o) 
从此列表中移除首次出现的指定元素（如果存在）。 
E removeFirst() 
移除并返回此列表的第一个元素。 
boolean removeFirstOccurrence(Object o) 
从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。 
E removeLast() 
移除并返回此列表的最后一个元素。 
boolean removeLastOccurrence(Object o) 
从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。 
E set(int index, E element) 
将此列表中指定位置的元素替换为指定的元素。 
int size() 
返回此列表的元素数。

 

>>双端队列

 

双端队列是一个限定插入和删除操作的数据结构，具有队列和栈的性质，
双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。
查看源码的实现，可以发现作为队列和栈时的相关方法。

（1）作为队列使用

add(e) 内部实现是addLast(e)
offer(e) 入队，直接返回add()
remove() 获取并移除列表第一个元素，和poll()相同，内部调用removeFirst()
poll() 出队 获取并移除队头元素 内部实现是调用removeFirst()
element() 返回列表第一个元素但不移除，内部调用getFirst()
peek() 返回列表第一个元素但不移除，和element()相同，内部调用getFirst()

（2）作为栈使用

push(e) 入栈 即addFirst(e)
pop() 出栈 即removeFirst()
peek() 获取栈顶元素但不移除 即peekFirst()

 

>>源码分析

（1）主要的节点更新操作

源码中的两个私有方法addBefore和remove是维护了节点更新的主要操作，
这一部分主要是数据结构中对链表的操作，理解起来比较简单，
大部分的add、remode等操作都可以通过这两个方法实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
    * 在传入节点之前插入新的节点元素
    */
   private Entry<E> addBefore(E e, Entry<E> entry) {
   //构造一个新的节点
   Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
   //调整新节点前后节点的指向
   newEntry.previous.next = newEntry;
   newEntry.next.previous = newEntry;
   size++;
   modCount++;
   return newEntry;
   }
    
    /**
    * 在链表中删除这个节点
    */
   private E remove(Entry<E> e) {
       //e等于初始化时的空节点，抛出异常
   if (e == header)
       throw new NoSuchElementException();
       E result = e.element;
       /**
        * 删除操作就是调整前后结点指针的指向，绕过传入节点
        * 然后再把传入节点的前后指针以及value都置为null
        */
   e.previous.next = e.next;
   e.next.previous = e.previous;
       e.next = e.previous = null;
       e.element = null;
   size--;
   modCount++;
       return result;
   }

（2）List迭代器 通过ListItr内部类实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
private class ListItr implements ListIterator<E> {
  private Entry<E> lastReturned = header;
  private Entry<E> next;
  private int nextIndex;
  private int expectedModCount = modCount;
 
  ListItr(int index) {
      if (index < 0 || index > size)
      throw new IndexOutOfBoundsException("Index: "+index+
                          ", Size: "+size);
      if (index < (size >> 1)) {
      next = header.next;
      for (nextIndex=0; nextIndex<index; nextIndex++)
          next = next.next;
      } else {
      next = header;
      for (nextIndex=size; nextIndex>index; nextIndex--)
          next = next.previous;
      }
  }
 
  public boolean hasNext() {
      return nextIndex != size;
  }
 
  public E next() {
      checkForComodification();
      if (nextIndex == size)
      throw new NoSuchElementException();
 
      lastReturned = next;
      next = next.next;
      nextIndex++;
      return lastReturned.element;
  }
 
  public boolean hasPrevious() {
      return nextIndex != 0;
  }
 
  public E previous() {
      if (nextIndex == 0)
      throw new NoSuchElementException();
 
      lastReturned = next = next.previous;
      nextIndex--;
      checkForComodification();
      return lastReturned.element;
  }
 
  public int nextIndex() {
      return nextIndex;
  }
 
  public int previousIndex() {
      return nextIndex-1;
  }
 
  public void remove() {
          checkForComodification();
          Entry<E> lastNext = lastReturned.next;
          try {
              LinkedList.this.remove(lastReturned);
          } catch (NoSuchElementException e) {
              throw new IllegalStateException();
          }
      if (next==lastReturned)
              next = lastNext;
          else
      nextIndex--;
      lastReturned = header;
      expectedModCount++;
  }
 
  public void set(E e) {
      if (lastReturned == header)
      throw new IllegalStateException();
      checkForComodification();
      lastReturned.element = e;
  }
 
  public void add(E e) {
      checkForComodification();
      lastReturned = header;
      addBefore(e, next);
      nextIndex++;
      expectedModCount++;
  }
 
  final void checkForComodification() {
      if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
  }
  }

　　

 

>>fail-fast机制

fail-fast，快速失败是Java集合的一种错误检测机制。
当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。
记住是有可能，而不是一定。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。

>>ArrayList和LinkedList的区别

ArrayList是一个基于数组的结构，里面的节点相互之间没有特别的联系，默认的大小是10，最大大小是Integer.MAX_VALUE - 8。
当大小不够时会自动增长，它可以通过get，set来直接获取、修改某一个节点数据。

LinkedList是一个基于双向链表的结构，每一个节点都有两个指针来分别指向上一个节点和下一个节点。它是可变长度的。
这两个实现类的区别在于，ArrayList的get()/set()效率比LinkedList高，而LinkedList的add()/remove()效率比ArrayList高。

具体来说：数组申请一块连续的内存空间，是在编译期间就确定大小的，运行时期不可动态改变，但为什么ArrayList可以改变大小呢，
因为在add如果超过了设定的大小就会创建一个新的更大的（增长率好像是0.5）ArrayList，
然后将原来的list复制到新的list中，并将地址指向新的list，旧的list被GC回收，显然这是非常消耗内存而且效率非常低的。
但是由于它申请的内存空间是连续的，可以直接通过下标来获取需要的数据，时间复杂度为O(1)，而链表则是O(n)，
而链表结构不一样，它可以动态申请内存空间。在需要加入的节点的上一个节点的指针解开并指向新加节点，再将新加节点的指针指向后一个节点即可。速度很快的。
所以说ArrayList适合查询，LinkedList适合增删。

 


上一篇：一个不使用CRM中间件成功地将ERP Material下载到CRM的原型开发


下一篇：高校计划ESC7天训练营-Leanote搭建云笔记平台