JDK1.8源码(六)——java.util.LinkedList 类
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JDK1.8源码(六)——java.util.LinkedList 类，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含20992字，纯文字阅读大概需要30分钟。
内容图文
JDK1.8源码(六)——java.util.LinkedList 类
上一篇博客我们介绍了List集合的一种典型实现 ArrayList，我们知道 ArrayList 是由数组构成的，本篇博客我们介绍 List 集合的另一种典型实现 LinkedList，这是一个由链表构成的数组，关于链表的介绍，在这篇博客中 我们也详细介绍过，本篇博客我们将介绍 LinkedList 是如何实现的。
1、LinkedList 定义
LinkedList 是一个用链表实现的集合，元素有序且可以重复。
1 public class LinkedList2 extends AbstractSequentialList3 implements List, Deque, Cloneable, java.io.Serializable
和 ArrayList 集合一样，LinkedList 集合也实现了Cloneable接口和Serializable接口，分别用来支持克隆以及支持序列化。List 接口也不用多说，定义了一套 List 集合类型的方法规范。
注意，相对于 ArrayList 集合，LinkedList 集合多实现了一个 Deque 接口，这是一个双向队列接口，双向队列就是两端都可以进行增加和删除操作。
2、字段属性
//链表元素（节点）的个数 transient int size = 0; /** *指向第一个节点的指针 */ transient Node first; /** *指向最后一个节点的指针 */ transient Nodelast;
注意这里出现了一个 Node 类，这是 LinkedList 类中的一个内部类，其中每一个元素就代表一个 Node 类对象，LinkedList 集合就是由许多个 Node 对象类似于手拉着手构成。
1 private static class Node { 2 E item;//实际存储的元素 3 Nodenext;//指向上一个节点的引用 4 Nodeprev;//指向下一个节点的引用 5 6 //构造函数 7 Node(Nodeprev, E element, Node next) { 8 this.item = element; 9 this.next = next;10 this.prev = prev;11 }12 }View Code
如下图所示：
上图的 LinkedList 是有四个元素，也就是由 4 个 Node 对象组成，size=4，head 指向第一个elementA,tail指向最后一个节点elementD。
3、构造函数
public LinkedList() {
} public LinkedList(Collection<? extends E> c) { this();
addAll(c);
}LinkedList 有两个构造函数，第一个是默认的空的构造函数，第二个是将已有元素的集合Collection 的实例添加到 LinkedList 中，调用的是 addAll() 方法，这个方法下面我们会介绍。
注意：LinkedList 是没有初始化链表大小的构造函数，因为链表不像数组，一个定义好的数组是必须要有确定的大小，然后去分配内存空间，而链表不一样，它没有确定的大小，通过指针的移动来指向下一个内存地址的分配。
4、添加元素
①、addFirst(E e)
将指定元素添加到链表头
1 //将指定的元素附加到链表头节点 2 public void addFirst(E e) { 3 linkFirst(e); 4 } 5 private void linkFirst(E e) { 6 final Nodef = first;//将头节点赋值给 f 7 final NodenewNode = new Node<>(null, e, f);//将指定元素构造成一个新节点，此节点的指向下一个节点的引用为头节点 8 first = newNode;//将新节点设为头节点，那么原先的头节点 f 变为第二个节点 9 if (f == null)//如果第二个节点为空，也就是原先链表是空10 last = newNode;//将这个新节点也设为尾节点（前面已经设为头节点了）11 else12 f.prev = newNode;//将原先的头节点的上一个节点指向新节点13 size++;//节点数加114 modCount++;//和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。15 }View Code
②、addLast(E e)和add(E e)
将指定元素添加到链表尾
1 //将元素添加到链表末尾 2 public void addLast(E e) { 3 linkLast(e); 4 } 5 //将元素添加到链表末尾 6 public boolean add(E e) { 7 linkLast(e); 8 return true; 9 }10 void linkLast(E e) {11 final Nodel = last;//将l设为尾节点12 final NodenewNode = new Node<>(l, e, null);//构造一个新节点，节点上一个节点引用指向尾节点l13 last = newNode;//将尾节点设为创建的新节点14 if (l == null)//如果尾节点为空，表示原先链表为空15 first = newNode;//将头节点设为新创建的节点（尾节点也是新创建的节点）16 else17 l.next = newNode;//将原来尾节点下一个节点的引用指向新节点18 size++;//节点数加119 modCount++;//和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。20 }View Code
③、add(int index, E element)
将指定的元素插入此列表中的指定位置
//将指定的元素插入此列表中的指定位置
public void add(int index, E element) { //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常 checkPositionIndex(index); if (index == size)//如果索引值等于链表大小
linkLast(element);//将节点插入到尾节点
else
linkBefore(element, node(index));
} void linkLast(E e) { final Nodel = last;//将l设为尾节点
final NodenewNode = new Node<>(l, e, null);//构造一个新节点，节点上一个节点引用指向尾节点l
last = newNode;//将尾节点设为创建的新节点
if (l == null)//如果尾节点为空，表示原先链表为空
first = newNode;//将头节点设为新创建的节点（尾节点也是新创建的节点）
else
l.next = newNode;//将原来尾节点下一个节点的引用指向新节点
size++;//节点数加1
modCount++;//和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。 }
Nodenode(int index) { if (index < (size >> 1)) {//如果插入的索引在前半部分
Nodex = first;//设x为头节点
for (int i = 0; i < index; i++)//从开始节点到插入节点索引之间的所有节点向后移动一位
x = x.next; return x;
} else {//如果插入节点位置在后半部分
Nodex = last;//将x设为最后一个节点
for (int i = size - 1; i > index; i--)//从最后节点到插入节点的索引位置之间的所有节点向前移动一位
x = x.prev; return x;
}
} void linkBefore(E e, Node succ) { final Nodepred = succ.prev;//将pred设为插入节点的上一个节点
final NodenewNode = new Node<>(pred, e, succ);//将新节点的上引用设为pred,下引用设为succ
succ.prev = newNode;//succ的上一个节点的引用设为新节点
if (pred == null)//如果插入节点的上一个节点引用为空
first = newNode;//新节点就是头节点
else
pred.next = newNode;//插入节点的下一个节点引用设为新节点
size++;
modCount++;
}View Code
④、addAll(Collection
按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾
此方法还有一个 addAll(int index, Collection
addAll(Collection
源码如下：
1 //按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾。 2 public boolean addAll(Collection<? extends E> c) { 3 return addAll(size, c); 4 } 5 //将集合 c 中所有元素插入到指定索引的位置。 6 public boolean addAll(int index, Collection<? extends E> c) { 7 //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常 8 checkPositionIndex(index); 9 10 Object[] a = c.toArray();//将集合转换成一个 Object 类型的数组11 int numNew = a.length;12 if (numNew == 0)//如果添加的集合为空，直接返回false13 return false;14 15 Node pred, succ;16 if (index == size) {//如果插入的位置等于链表的长度，就是将原集合元素附加到链表的末尾17 succ = null;18 pred = last;19 } else {20 succ = node(index);21 pred = succ.prev;22 }23 24 for (Object o : a) {//遍历要插入的元素25 @SuppressWarnings("unchecked") E e = (E) o;26 NodenewNode = new Node<>(pred, e, null);27 if (pred == null)28 first = newNode;29 else30 pred.next = newNode;31 pred = newNode;32 }33 34 if (succ == null) {35 last = pred;36 } else {37 pred.next = succ;38 succ.prev = pred;39 }40 41 size += numNew;42 modCount++;43 return true;44 }View Code
看到上面向 LinkedList 集合中添加元素的各种方式，我们发现LinkedList 每次添加元素只是改变元素的上一个指针引用和下一个指针引用，而且没有扩容。，对比于 ArrayList ，需要扩容，而且在中间插入元素时，后面的所有元素都要移动一位，两者插入元素时的效率差异很大，下一篇博客会对这两者的效率，以及何种情况选择何种集合进行分析。
还有，每次进行添加操作，都有modCount++ 的操作，
5、删除元素
删除元素和添加元素一样，也是通过更改指向上一个节点和指向下一个节点的引用即可，这里就不作图形展示了。
①、remove()和removeFirst()
从此列表中移除并返回第一个元素
1 //从此列表中移除并返回第一个元素 2 public E remove() { 3 return removeFirst(); 4 } 5 //从此列表中移除并返回第一个元素 6 public E removeFirst() { 7 final Nodef = first;//f设为头结点 8 if (f == null) 9 throw new NoSuchElementException();//如果头结点为空，则抛出异常10 return unlinkFirst(f);11 }12 private E unlinkFirst(Node f) {13 // assert f == first && f != null;14 final E element = f.item;15 final Nodenext = f.next;//next 为头结点的下一个节点16 f.item = null;17 f.next = null; // 将节点的元素以及引用都设为 null，便于垃圾回收18 first = next; //修改头结点为第二个节点19 if (next == null)//如果第二个节点为空（当前链表只存在第一个元素）20 last = null;//那么尾节点也置为 null21 else22 next.prev = null;//如果第二个节点不为空，那么将第二个节点的上一个引用置为 null23 size--;24 modCount++;25 return element;26 }View Code
②、removeLast()
从该列表中删除并返回最后一个元素
1 //从该列表中删除并返回最后一个元素 2 public E removeLast() { 3 final Nodel = last; 4 if (l == null)//如果尾节点为空，表示当前集合为空，抛出异常 5 throw new NoSuchElementException(); 6 return unlinkLast(l); 7 } 8 9 private E unlinkLast(Node l) {10 // assert l == last && l != null;11 final E element = l.item;12 final Nodeprev = l.prev;13 l.item = null;14 l.prev = null; //将节点的元素以及引用都设为 null，便于垃圾回收15 last = prev;//尾节点为倒数第二个节点16 if (prev == null)//如果倒数第二个节点为null17 first = null;//那么将节点也置为 null18 else19 prev.next = null;//如果倒数第二个节点不为空，那么将倒数第二个节点的下一个引用置为 null20 size--;21 modCount++;22 return element;23 }View Code
③、remove(int index)
删除此列表中指定位置的元素
1 //删除此列表中指定位置的元素 2 public E remove(int index) { 3 //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常 4 checkElementIndex(index); 5 return unlink(node(index)); 6 } 7 E unlink(Node x) { 8 // assert x != null; 9 final E element = x.item;10 final Nodenext = x.next;11 final Nodeprev = x.prev;12 13 if (prev == null) {//如果删除节点位置的上一个节点引用为null（表示删除第一个元素）14 first = next;//将头结点置为第一个元素的下一个节点15 } else {//如果删除节点位置的上一个节点引用不为null16 prev.next = next;//将删除节点的上一个节点的下一个节点引用指向删除节点的下一个节点（去掉删除节点）17 x.prev = null;//删除节点的上一个节点引用置为null18 }19 20 if (next == null) {//如果删除节点的下一个节点引用为null（表示删除最后一个节点）21 last = prev;//将尾节点置为删除节点的上一个节点22 } else {//不是删除尾节点23 next.prev = prev;//将删除节点的下一个节点的上一个节点的引用指向删除节点的上一个节点24 x.next = null;//将删除节点的下一个节点引用置为null25 }26 27 x.item = null;//删除节点内容置为null，便于垃圾回收28 size--;29 modCount++;30 return element;31 }View Code
④、remove(Object o)
如果存在，则从该列表中删除指定元素的第一次出现
此方法本质上和 remove(int index) 没多大区别，通过循环判断元素进行删除，需要注意的是，是删除第一次出现的元素，不是所有的。
1 public boolean remove(Object o) { 2 if (o == null) { 3 for (Nodex = first; x != null; x = x.next) { 4 if (x.item == null) { 5 unlink(x); 6 return true; 7 } 8 } 9 } else {10 for (Nodex = first; x != null; x = x.next) {11 if (o.equals(x.item)) {12 unlink(x);13 return true;14 }15 }16 }17 return false;18 }View Code
6、修改元素
通过调用 set(int index, E element) 方法，用指定的元素替换此列表中指定位置的元素。
public E set(int index, E element) { //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常 checkElementIndex(index);
Nodex = node(index);//获取指定索引处的元素
E oldVal = x.item;
x.item = element;//将指定位置的元素替换成要修改的元素
return oldVal;//返回指定索引位置原来的元素
}这里主要是通过 node(index) 方法获取指定索引位置的节点，然后修改此节点位置的元素即可。
7、查找元素
①、getFirst()
返回此列表中的第一个元素
1 public E getFirst() {2 final Nodef = first;3 if (f == null)4 throw new NoSuchElementException();5 return f.item;6 }View Code
②、getLast()
返回此列表中的最后一个元素
1 public E getLast() {2 final Nodel = last;3 if (l == null)4 throw new NoSuchElementException();5 return l.item;6 }View Code
③、get(int index)
返回指定索引处的元素
1 public E get(int index) {2 checkElementIndex(index);3 return node(index).item;4 }View Code
④、indexOf(Object o)
返回此列表中指定元素第一次出现的索引，如果此列表不包含元素，则返回-1。
1 //返回此列表中指定元素第一次出现的索引，如果此列表不包含元素，则返回-1。 2 public int indexOf(Object o) { 3 int index = 0; 4 if (o == null) {//如果查找的元素为null(LinkedList可以允许null值) 5 for (Nodex = first; x != null; x = x.next) {//从头结点开始不断向下一个节点进行遍历 6 if (x.item == null) 7 return index; 8 index++; 9 }10 } else {//如果查找的元素不为null11 for (Nodex = first; x != null; x = x.next) {12 if (o.equals(x.item))13 return index;14 index++;15 }16 }17 return -1;//找不到返回-118 }View Code
8、遍历集合
①、普通 for 循环
LinkedListlinkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");for(int i = 0 ; i < linkedList.size() ; i++){
System.out.print(linkedList.get(i)+" ");//A B C D}View Code
代码很简单，我们就利用 LinkedList 的 get(int index) 方法，遍历出所有的元素。
但是需要注意的是， get(int index) 方法每次都要遍历该索引之前的所有元素，这句话这么理解：
比如上面的一个 LinkedList 集合，我放入了 A,B,C,D是个元素。总共需要四次遍历：
第一次遍历打印 A：只需遍历一次。
第二次遍历打印 B：需要先找到 A，然后再找到 B 打印。
第三次遍历打印 C：需要先找到 A，然后找到 B，最后找到 C 打印。
第四次遍历打印 D：需要先找到 A，然后找到 B，然后找到 C，最后找到 D。
这样如果集合元素很多，越查找到后面（当然此处的get方法进行了优化，查找前半部分从前面开始遍历，查找后半部分从后面开始遍历，但是需要的时间还是很多）花费的时间越多。那么如何改进呢？
②、迭代器
1 LinkedListlinkedList = new LinkedList<>(); 2 linkedList.add("A"); 3 linkedList.add("B"); 4 linkedList.add("C"); 5 linkedList.add("D"); 6 7 8 IteratorlistIt = linkedList.listIterator(); 9 while(listIt.hasNext()){10 System.out.print(listIt.next()+" ");//A B C D11 }12 13 //通过适配器模式实现的接口，作用是倒叙打印链表14 Iteratorit = linkedList.descendingIterator();15 while(it.hasNext()){16 System.out.print(it.next()+" ");//D C B A17 }View Code
在 LinkedList 集合中也有一个内部类 ListItr，方法实现大体上也差不多，通过移动游标指向每一次要遍历的元素，不用在遍历某个元素之前都要从头开始。其方法实现也比较简单：
1 public ListIteratorlistIterator(int index) { 2 checkPositionIndex(index); 3 return new ListItr(index); 4 } 5 6 private class ListItr implements ListIterator { 7 private Node lastReturned; 8 private Node next; 9 private int nextIndex; 10 private int expectedModCount = modCount; 11 12 ListItr(int index) { 13 // assert isPositionIndex(index); 14 next = (index == size) ? null : node(index); 15 nextIndex = index; 16 } 17 18 public boolean hasNext() { 19 return nextIndex < size; 20 } 21 22 public E next() { 23 checkForComodification(); 24 if (!hasNext()) 25 throw new NoSuchElementException(); 26 27 lastReturned = next; 28 next = next.next; 29 nextIndex++; 30 return lastReturned.item; 31 } 32 33 public boolean hasPrevious() { 34 return nextIndex > 0; 35 } 36 37 public E previous() { 38 checkForComodification(); 39 if (!hasPrevious()) 40 throw new NoSuchElementException(); 41 42 lastReturned = next = (next == null) ? last : next.prev; 43 nextIndex--; 44 return lastReturned.item; 45 } 46 47 public int nextIndex() { 48 return nextIndex; 49 } 50 51 public int previousIndex() { 52 return nextIndex - 1; 53 } 54 55 public void remove() { 56 checkForComodification(); 57 if (lastReturned == null) 58 throw new IllegalStateException(); 59 60 NodelastNext = lastReturned.next; 61 unlink(lastReturned); 62 if (next == lastReturned) 63 next = lastNext; 64 else 65 nextIndex--; 66 lastReturned = null; 67 expectedModCount++; 68 } 69 70 public void set(E e) { 71 if (lastReturned == null) 72 throw new IllegalStateException(); 73 checkForComodification(); 74 lastReturned.item = e; 75 } 76 77 public void add(E e) { 78 checkForComodification(); 79 lastReturned = null; 80 if (next == null) 81 linkLast(e); 82 else 83 linkBefore(e, next); 84 nextIndex++; 85 expectedModCount++; 86 } 87 88 public void forEachRemaining(Consumer<? super E> action) { 89 Objects.requireNonNull(action); 90 while (modCount == expectedModCount && nextIndex < size) { 91 action.accept(next.item); 92 lastReturned = next; 93 next = next.next; 94 nextIndex++; 95 } 96 checkForComodification(); 97 } 98 99 final void checkForComodification() {100 if (modCount != expectedModCount)101 throw new ConcurrentModificationException();102 }103 }View Code
这里需要重点注意的是 modCount 字段，前面我们在增加和删除元素的时候，都会进行自增操作 modCount，这是因为如果想一边迭代，一边用集合自带的方法进行删除或者新增操作，都会抛出异常。（使用迭代器的增删方法不会抛异常）
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException();
}比如：
1 LinkedListlinkedList = new LinkedList<>(); 2 linkedList.add("A"); 3 linkedList.add("B"); 4 linkedList.add("C"); 5 linkedList.add("D"); 6 7 8 IteratorlistIt = linkedList.listIterator(); 9 while(listIt.hasNext()){10 System.out.print(listIt.next()+" ");//A B C D11 //linkedList.remove();//此处会抛出异常12 listIt.remove();//这样可以进行删除操作13 }View Code
迭代器的另一种形式就是使用 foreach 循环，底层实现也是使用的迭代器，这里我们就不做介绍了。
LinkedListlinkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");for(String str : linkedList){
System.out.print(str + "");
}View Code
9、迭代器和for循环效率差异
1 LinkedListlinkedList = new LinkedList<>(); 2 for(int i = 0 ; i < 10000 ; i++){//向链表中添加一万个元素 3 linkedList.add(i); 4 } 5 long beginTimeFor = System.currentTimeMillis(); 6 for(int i = 0 ; i < 10000 ; i++){ 7 System.out.print(linkedList.get(i)); 8 } 9 long endTimeFor = System.currentTimeMillis();10 System.out.println("使用普通for循环遍历10000个元素需要的时间："+ (endTimeFor - beginTimeFor));11 12 13 long beginTimeIte = System.currentTimeMillis();14 Iteratorit = linkedList.listIterator();15 while(it.hasNext()){16 System.out.print(it.next()+" ");17 }18 long endTimeIte = System.currentTimeMillis();19 System.out.println("使用迭代器遍历10000个元素需要的时间："+ (endTimeIte - beginTimeIte));打印结果为：
一万个元素两者之间都相差一倍多的时间，如果是十万，百万个元素，那么两者之间相差的速度会越来越大。下面通过图形来解释：
普通for循环：每次遍历一个索引的元素之前，都要访问之间所有的索引。
迭代器：每次访问一个元素后，都会用游标记录当前访问元素的位置，遍历一个元素，记录一个位置。
内容总结
以上是互联网集市为您收集整理的JDK1.8源码(六)——java.util.LinkedList 类全部内容，希望文章能够帮你解决JDK1.8源码(六)——java.util.LinkedList 类所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。