啃碎JDK源码(六):LinkedList

超大只乌龟 2020-11-09 22:19:19
源码 jdk LinkedList 技术开发 SegmentFault


前言

之前已经写了几篇有关Java集合的文章:

今天我们来介绍一下另外一个容器类:LinkedList

正文

LinkedListArrayList一样是集合List的实现类,虽然较之ArrayList,其使用场景并不多,但同样有用到的时候,那么接下来,我们来认识一下它。

public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{//底层是双向链表
//元素数量
transient int size = 0;
//第一个结点
transient Node<E> first;
//最后一个结点
transient Node<E> last;
.....

其实LinkedList底层使用双向链表实现的,可以看到上面有firstlast两个Node节点,来看看其内部类Node的定义:

 private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}

很简单,学过链表的同学应该都很清楚。

那首先我们还是来看看构造函数:

public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

addAll(Collection<? extends E> c)方法用来添加指定的集合数据到LinkedList中。

辅助函数

在去看LinkedListgetadd等方法前,我们先去看下几个比较重要的辅助函数:

  • 首先是第一个辅助函数linkFirst(E e),该方法用于插入元素到链表头部
/*
* 插入元素到头部
*/
private void linkFirst(E e) {
final Node<E> f = first;
// 设置newNode的前结点为null,后结点为f
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
// 首先链接元素,同时把newNode设为最后一个结点
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}

回忆一下内部类 Node 的构造函数:Node(Node<E> prev, E element, Node<E> next),三个参数分别前一个结点、元素值以及下一个结点。

从上面可以看出在插入元素到链表头部其实创建一个Node结点,让其 next 指针指向链表首结点first

  • 插入元素到链表尾部
/*
* 插入元素到尾部
*/
void linkLast(E e) {
final Node<E> l = last;
// 设置newNode的前结点为l,后结点为null
final Node<E> newNode = new Node<>(l, e, null);
// 新结点变成最后一个结点
last = newNode;
// 若l == null说明是首次链接元素,将first也指向新结点
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
// 修改次数+1
modCount++;
}

插入到尾部和上面插入到头部的方法也有异曲同工之妙,这里就不再细说。

  • 接着我们要给定结点前插入元素
/*
* 在给定结点前插入元素e
*/
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
// 设置newNode的前结点为pred,后结点为succ
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)//如果succ是头结点,将newNode设置为头结点
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

很简单,就是让给定结点succprev 指针和前一个结点的 next 指针都指向我们的新结点就可以了。

  • 那如何删除一个结点呢?
/*
* 删除链表结点
*/
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//判断是否是头结点
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;//GC回收
}
//判断是否是尾结点
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;//GC回收
}
x.item = null;//GC回收
size--;
modCount++;
return element;
}

注意这里我们删除结点 x 后要把x的前后引用包括自身引用都设为null,这样JVM垃圾回收才会帮我们去回收x,否则会有内存泄漏的隐患。

还有最后一个辅助函数,用来获取指定位置的结点

/*
*返回指定位置的结点
*/
Node<E> node(int index) {
//根据index位置考虑是从前面遍历还是从后面遍历(加快查询速度)
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

这里有一个值得我们借鉴的:就是会根据索引的位置来判读是从头部还是尾部遍历,这也是一个性能的小优化。

image

有了辅助函数后我们就可以来看看我们平常使用的比较多的API了

首先来看看getset方法:

get(int index)方法用来获取指定位置上的元素

/*
* 返回指定位置元素
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}

可以看到先调用checkElementIndex方法校验参数,然后调用辅助方法node(int index)获取元素值。

/*
* 设置元素
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

set(int index, E element)方法用来设置元素,比较简单不再细说。

接下来看看另外两个方法:

peek方法用于返回头结点,而pool用于删除头结点并返回头结点的值

/*
* 返回头结点值,如果链表为空则返回null
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/*
* 删除头结点并返回头结点值,如果链表为空则返回null
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

现在来看看如何删除一个结点:

/*
* 默认删除头结点
*/
public E remove() {
return removeFirst();
}
/*
* 删除指定位置结点
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/*
* 删除指定结点
*/
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

其实只要搞懂上面几个辅助函数后,其它的增删查改就很简单了。

继续来看另外一个index(Object o)方法,该方法用于返回指定对象在链表中的索引

/*
* 返回指定对象在链表中的索引(如果没有则返回-1)
* lastIndexOf同理(其实就是从后向前遍历)
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}

现在我们如何把LinkedList转成数组返回呢?来看看toArray方法:

/*
* 将链表包装成数组返回
*/
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
//依次取出结点值放入数组
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}

还有一个toArray(T[] a)方法,可以返回指定类型的数组:

/*
* 将链表包装成指定类型数组返回
*/
public <T> T[] toArray(T[] a) {
if (a.length < size)//给点的数组长度小于链表长度
//创建一个类型与a一样,长度为size的数组
a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;//定义result指向给定数组,修改result == 修改a
//依次把结点值放入result数组
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}

迭代器

LinkedListArrayList还有一个比较大的区别是LinkedList除了iterator方法之外还有一个listIterator方法,该迭代器除了向后遍历数据外,也可以向前遍历,正是由于底层的双向链表结构才能实现。

public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);//参数校验
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;//上次越过的结点
private Node<E> next;//下次越过的结点
private int nextIndex;//下次越过结点的索引
private int expectedModCount = modCount;//预期修改次数
ListItr(int index) {
next = (index == size) ? null : node(index);//index默认为0
nextIndex = index;
}
/*判断是否有下一个元素*/
public boolean hasNext() {
return nextIndex < size;
}
/*向后遍历,返回越过的元素*/
public E next() {
checkForComodification();//fail-fast
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
/*判断是否有上一个元素*/
public boolean hasPrevious() {
return nextIndex > 0;
}
/*向前遍历,返回越过的元素*/
public E previous() {
checkForComodification();//fail-fast
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;//调用previous后lastReturned = next
nextIndex--;
return lastReturned.item;
}
/*返回下一个越过的元素索引*/
public int nextIndex() {
return nextIndex;
}
/*返回上一个越过的元素索引*/
public int previousIndex() {
return nextIndex - 1;
}
/*删除元素*/
public void remove() {
checkForComodification();//fail-fast
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);//从链表中删除lastReturned,modCount++(该方法会帮你处理结点指针指向)
if (next == lastReturned)//调用previous后next == lastReturned
next = lastNext;
else
nextIndex--;
lastReturned = null;//GC
expectedModCount++;
}
/*设置元素*/
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();//fail-fast
lastReturned.item = e;
}
/*插入元素*/
public void add(E e) {
checkForComodification();//fail-fast
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
/*操作未遍历的元素*/
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);//判空
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
/*fail-fast*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

总结

今天有关LinkedList的源码分就暂时先到这里,其实如果理解了链表结构那么上面源码应该不是很难,如果有什么不对的地方请多多指教。

image

版权声明
本文为[超大只乌龟]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000037779028

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云