关于LinkedList源码解读

1.LinkedList概述

LinkedList底层的数据结构是双向链表，实现了 List, Deque, Cloneable, java.io.Serializable接口，因为它实现了Deque,所以也可以作为一个双端队列。和ArrayList相比因为没有实现RandomAccess接口，所以不支持下标访问，随机访问元素比较慢。

因为底层数据结构是链表，所以在增删数据的时候，只需要改变指针的指向就可以，所以增删数据的效率相对要高一点，不需要批量扩容，也不需要预留空间。在空间效率上比ArrayList高。每次增删的时候都会去修modCount的值。

2.LinkedList的成员变量

LinkedList的成员变量相对于ArrayList来说较少,下面是每个成员变量的说明

transient int size = 0; //集合的元素数量 transient Node<E> first; //头节点 transient Node<E> last; //尾节点 public LinkedList() { //无参构造方法 } public LinkedList(Collection<? extends E> c) { //传入一个其他集合 this(); addAll(c); }

3.Node

Node是LinkedList中的一个私有的静态内部类

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; } }

4.LinedList中的有参构造方法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6CTlvDBY-1602204296096)(C:\Users\kingdee\Desktop\连接信息\Snipaste_2020-09-29_14-32-02.png)]

我们可以清楚的看见，LinkeList中的有参构造会在内部调用无参构造，然后再调用addAll()方法进行一系列操作，接下来我们来看看addAll这个方法中具体做了哪些操作.请看addAll源码:

public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); //该方法检查是否越界[0,size] Object[] a = c.toArray();//将目标集合转换成数组 int numNew = a.length; //获取数组的长度，也就是新增的元素数量 if (numNew == 0) //判断新增元素数量是否为0，如果为零则不添加 return false; Node<E> pred, succ; //定义当前index节点的前置节点和后置节点 if (index == size) { //在链表尾部插入数据 succ = null; //后置节点为null pred = last;//前置节点为链表最后一个元素 } else { succ = node(index);//取出当前位置的节点，作为后置节点 pred = succ.prev; //当前位置的前置节点，作为前置节点 } for (Object o : a) { //遍历数组 @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); //利用前置节点和值创建一个节点 if (pred == null) //如果前置节点为空，则代表是一个新链表 first = newNode; //将此节点设为链表的头结点 else pred.next = newNode; //如果不为空，前置节点的后置节点设置问新节点， pred = newNode; //当前节点变为前置节点，为下一次连接座准备 } if (succ == null) { //判断后置节点是否为空，说明是在尾部添加元素操作 last = pred; //设置尾节点 } else { pred.next = succ; //在队中插入的节点 ，更新前置节点 后置节点 succ.prev = pred;//更新后置节点的前置节点 } size += numNew; //元素个数添加 modCount++; //记录修改次数 return true; }

顺带分析一下node(int index)这个方法，该方法乍一看是使用以二分法的思想，先本身的链表的size,利用位运算判断索引的位置，由此来提高查询效率

/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; //将头节点赋值给x for (int i = 0; i < index; i++) //根据index从头节点遍历获取到该节点 x = x.next; return x; } else { Node<E> x = last;//将尾节点赋值给x for (int i = size - 1; i > index; i--)//根据index从尾节点遍历获取到该节点 x = x.prev; return x; } }

5.LinkedList的方法

5.1 增加操作

1.插入单个节点 add(E e)

public boolean add(E e) { linkLast(e); //调用linkLast从尾部添加节点 return true; //添加成功 }

接下来分析一下linkLast(E e)这个方法

/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; //将链表的尾部节点赋值给 l节点 final Node<E> newNode = new Node<>(l, e, null); //以 l 节点也就是以链表的尾结点为前置节点创建一个新节点 last = newNode; //将新创建的节点作为尾部节点 if (l == null) //判断 l 是否为空，如果为空则代表是新创的一个链表，头节点就为当前新创的节点 first = newNode; else //否则 新创建的节点为尾部节点 l.next = newNode; size++; 元素数量加一 modCount++; //修改次数加一 }

2.在指定的位置插入一个元素add(int index,E e)

public void add(int index, E element) { checkPositionIndex(index); //判断是否越界 if (index == size) //如果指定位置的索引刚好等于链表的大小，则执行尾部添加操作，上面已经有讲到 linkLast(element); else //否则执行linkBefore() linkBefore(element, node(index)); }

下面我们来看看linkBefore()方法中作了什么操作

void linkBefore(E e, Node<E> succ) { //获取了指定位置的节点 // assert succ != null; final Node<E> pred = succ.prev; //获取指定位置的前置节点 final Node<E> newNode = new Node<>(pred, e, succ); //以指定位置的前置节点作为前置节点，指定位置的节点作为后置节点创建一个节点 succ.prev = newNode; //更新指定位置的前置节点为新创建的节点 if (pred == null) //如果指定位置的前置节点为null,则更新头节点为新创建的节点 first = newNode; else pred.next = newNode; //否则如果指定位置的前置节点的后置节点为新创建的节点 size++; //元素数量加一 modCount++; //修改次数加一 }

前置节点为null,则更新头节点为新创建的节点 first = newNode; else pred.next = newNode; //否则如果指定位置的前置节点的后置节点为新创建的节点 size++; //元素数量加一 modCount++; //修改次数加一 }