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

前面学习了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适合增删。

 

时间： 2024-09-29 13:31:12

Java集合源码学习（三）LinkedList分析的相关文章

Java集合源码学习（二）ArrayList分析

Java集合源码学习笔记(二)ArrayList分析 1.关于ArrayList ArrayList直接继承AbstractList,实现了List. RandomAccess.Cloneable.Serializable接口, 为什么叫"ArrayList",因为ArrayList内部是用一个数组存储元素值,相当于一个可变大小的数组,也就是动态数组. (1)继承和实现 继承了AbstractList,实现了List:ArrayList是一个数组队列,提供了相关的添加.删除.修改.遍历

Java集合源码学习（四）HashMap分析

ArrayList.LinkedList和HashMap的源码是一起看的,横向对比吧,感觉对这三种数据结构的理解加深了很多. 1.数组.链表和哈希表结构 数据结构中有数组和链表来实现对数据的存储,这两者有不同的应用场景, 数组的特点是:寻址容易,插入和删除困难:链表的特点是:寻址困难,插入和删除容易: 哈希表的实现结合了这两点,哈希表的实现方式有多种,在HashMap中使用的是链地址法,也就是拉链法. 看下面这张流传很广的图, 拉链法实际上是一种链表数组的结构,由数组加链表组成,在这个长度为16

Java集合源码学习（五）几种常用集合类的比较

这篇笔记对几个常用的集合实现,从效率,线程安全和应用场景进行综合比较. 1.ArrayList.LinkedList与Vector的对比 (1)相同和不同 都实现了List接口,使用类似. Vector和ArrayList的底层实现都是数组,这一点与LinkedList的双向链表不同. Vector和ArrayList在更多元素添加进来时会请求更大的空间.Vector每次请求其大小的双倍空间,而ArrayList每次对size增长50%.(2)线程安全 ArrayList.LinkedList都

Java集合源码剖析：LinkedList源码剖析

LinkedList简介 LinkedList是基于双向循环链表(从源码中可以很容易看出)实现的,除了可以当做链表来操作外,它还可以当做栈.队列和双端队列来使用. LinkedList同样是非线程安全的,只在单线程下适合使用. LinkedList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了Cloneable接口,能被克隆. LinkedList源码剖析 LinkedList的源码如下(加入了比较详细的注释): package java.util; publi

Java集合源码学习（一）集合框架概览

>>集合框架 Java集合框架包含了大部分Java开发中用到的数据结构,主要包括 List列表.Set集合.Map映射.迭代器(Iterator.Enumeration).工具类(Arrays.Collections)几个部分. >>Collection系列 画类图好麻烦,强烈推荐processon.com. 注意,在Eclipse中使用Ctrl+T查看Collection接口的继承与实现关系, 会发现好多用于并发的相关容器,以及第三方的包实现了这个接口,这里只考察原生Java集合

Java集合源码全面分析_java

Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组.链表.栈.队列.集合.哈希表等.学习Java集合框架下大致可以分为如下五个部分:List列表.Set集合.Map映射.迭代器(Iterator.Enumeration).工具类(Arrays.Collections). 从上图中可以看出,集合类主要分为两大类:Collection和Map. Collection是List.Set等集合高度抽象出来的接口,它包含了这些集合的基本操作,它主要又分为两大部分:List和Se

Java集合源码剖析：TreeMap源码剖析

前言 本文不打算延续前几篇的风格(对所有的源码加入注释),因为要理解透TreeMap的所有源码,对博主来说,确实需要耗费大量的时间和经历,目前看来不大可能有这么多时间的投入,故这里意在通过于阅读源码对TreeMap有个宏观上的把握,并就其中一些方法的实现做比较深入的分析. 红黑树简介 TreeMap是基于红黑树实现的,这里只对红黑树做个简单的介绍,红黑树是一种特殊的二叉排序树,关于二叉排序树,参见:http://blog.csdn.net/ns_code/article/details/1982

Java集合源码剖析：Vector源码剖析

Vector简介 Vector也是基于数组实现的,是一个动态数组,其容量能自动增长. LinkedList是JDK1.0引入了,它的很多实现方法都加入了同步语句,因此是线程安全的(其实也只是相对安全,有些时候还是要加入同步语句来保证线程的安全),可以用于多线程环境. LinkedList没有丝线Serializable接口,因此它不支持序列化,实现了Cloneable接口,能被克隆,实现了RandomAccess接口,支持快速随机访问. Vector源码剖析 Vector的源码如下(加入了比较详

Java集合源码剖析：Java集合框架

Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组.链表.栈.队列.集合.哈希表等.学习Java集合框架下大致可以分为如下五个部分:List列表.Set集合.Map映射.迭代器(Iterator.Enumeration).工具类(Arrays.Collections). Java集合类的整体框架如下: 从上图中可以看出,集合类主要分为两大类:Collection和Map. Collection是List.Set等集合高度抽象出来的接口,它包含了这些集合的基本操作,它主