开发者社区> 邴越> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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>(nullnullnull);
    //链表的实际长度
    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适合增删。

 


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LinkedList源码解读—Java8版本(下)
LinkedList源码解读—Java8版本(下)
19 0
LinkedList源码解读—Java8版本(上)
LinkedList源码解读—Java8版本(上)
23 0
LinkedList源码解读—Java8版本(中)
LinkedList源码解读—Java8版本(中)
21 0
线程 - Java 多线程编程(上)
线程 - Java 多线程编程(上)
52 0
Java多线程那些事,对Java并发编程2w余字的总结,超详细(从入门到完全掌握)
Java多线程那些事,对Java并发编程2w余字的总结,超详细(从入门到完全掌握)
70 0
java多线程中的死锁、活锁、饥饿、无锁都是什么鬼?
死锁、活锁、饥饿是关于多线程是否活跃出现的运行阻塞障碍问题,如果线程出现了这三种情况,即线程不再活跃,不能再正常地执行下去了。
61 0
五分钟带你玩转多线程(一)java多线程基础知识简介
线程概念 进程:是一个执行中的程序,如打开网易云音乐,网易云音乐就是一个进程 线程:是进程的组成,一个进程包含多个线程,是jvm最小调度单元。如网易云音乐听歌是一个线程,评价是一个线程。
47 0
Java的并发编程中的多线程问题到底是怎么回事儿?
原创: Hollis 在我之前的一篇《再有人问你Java内存模型是什么,就把这篇文章发给他。》文章中,介绍了Java内存模型,通过这篇文章,大家应该都知道了Java内存模型的概念以及作用,这篇文章中谈到,在Java并发编程中,通常会遇到三个问题,即原子性问题、一致性问题和有序性问题。
1055 0
+关注
邴越
关注分布式系统及高可用架构,探讨职业规划,实践持续学习,公众号「架构进化论」
251
文章
1
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载