LinkedList源码分析--基于JDK1.8

LinkedList源码分析

LinkedList的UML图:
1592201271(1).png
LinkedList真正用来存储元素的数据结构-> Node类
Node类是LinkedList中的私有内部类,LinkedList中通过Node来存储集合中的元素

  • E:节点的值
  • Node next: 当前节点的后一个节点的引用(可以理解为指向当前节点的后一个节点的指针)
  • Node prev:当前节点的前一个节点的引用(可以理解为指向当前节点的前一个节点的指针)

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

LinkedList的元素

//LinkedList节点个数,用来记录LinkedList的大小
transient int size = 0;

/**
 * 指向第一个节点的指针。用来表示LinkedList的头结点
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * 指向最后一个节点的指针。用来表示LinkedList的尾结点
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

LinkedList的构造函数(两个)

ArrayList的构造函数有三个,比LinkedList多提供了一个设置初始化容量来初始化类。LinkedList没有提供该方法,原因:因为LinkedList底层是通过链表实现的,每添加新元素的时候,都是通过链接新的节点实现的,也就是说它的容量是随着元素的个数的变化而动态变化的。而ArrayList底层是通过数组来存储新添加的元素的,所以我们可以为ArrayList设置初始容量(也就是设置数组的大小)

/**
 * 空参构造
 */
public LinkedList() {
}

/**
 * 构造包含指定集合元素的列表,按照集合的迭代器返回元素的顺序
 * 传入一个结合作为参数初始化LinkedList。
 *
 * @param  c 将其元素放置在此列表中的集合
 * @throws NullPointerException 如果指定的集合为空
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

LinkedList的构造函数(带参数)

在LinkedList带集合参数的构造函数中有一个重要的方法addAll(int index, Collection),这块儿的方法有点绕,如果没看懂,建议手画一遍。

/**
 * 通过调用addAll(int index, Collection<? extends E> c)添加 集合
 */
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
/**
 * checkPositionIndex(index); 检查传入的参数是否合法
 */
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    // 将集合转换为数组
    Object[] a = c.toArray();
    // numNew 存储数组的长度
    int numNew = a.length;
    // 如果 c:待添加的集合为null,直接返回false,不进行后面的操作
    if (numNew == 0)
        return false;
    // pred:指代 待添加节点的前一个节点
    // succ:指的是待添加节点的位置
    Node<E> pred, succ;
     // 如果index==size,说明此时需要添加LinkedList的集合中每一个元素都是在LinkedList最后面。所以把succ设置为null, pred指向尾结点
     // 否则的话succ指向插入待插入位置的节点。这里用到了node(index)方法,pred指向succ节点的前一个节点
    if (index == size) {
        // 新添加的元素的位置是位于LinkedList最后一个元素的后面,也就是在LinkedList尾部追加元素
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    /**
      * 遍历数组中的每一个元素。在每次遍历的时候,都新建一个节点,该节点的值存储数组a中遍历的值,该节点的prev存储pred节点,next设置为null。
      * 接着判断该节点的前一个节点是否为空,如果为空的话,则把当前节点设置为头结点
      * 否则的话就把当前节点的前一个节点的next值设置为当前节点。最后把pred指向当前节点,方便后续节点的添加
      */
    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;
    }
    /**
      * 当succ为null时,也就是新添加的节点位于LinkedList集合的最后一个元素的后面。
      * 上面的for遍历的a的所有元素,此时的pred指向的是Linked中的最后一个元素,所以把last指向pred指向的节点
      * 当不为空的时候,表明在LinkedList集合中添加的元素,需要把pred的next指向succ上,succ的prev指向pred
      */
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    // 重新设置集合的大小
    size += numNew;
    // 修改的次数-自增。
    modCount++;
    return true;
}

LinkedList中的一些辅助方法

  • linkFirst(E e){};把参数中的元素作为链表的第一个元素
/**
 * 链接e作为第一个元素。
 */
private void linkFirst(E e) {
    final Node<E> f = first;// LinkedList中的第一个元素first赋给 f
    // 组建新的node,新添加的元素的succ(后指针指向给 f)
    final Node<E> newNode = new Node<>(null, e, f);
    // 将新插入的节点e,赋给first
    first = newNode;
    // 如果 f== null ;说明是空链表,把新节点设置为尾结点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
  • linkLast(E e){};把参数中的元素作为链表的最后一个元素
/**
 * 链接e作为最后一个元素。
 */
void linkLast(E e) {
    // 获取尾部元素
    final Node<E> l = last; 
    // 以尾部元素为前继结点创建一个新节点
    final Node<E> newNode = new Node<>(l, e, null);
    // 更新尾部节点为需要插入的节点
    last = newNode;

    if (l == null)
        //如果为空链表的情况:同时更新first节点为需要插入的节点。(也就是说,该节点即是头结点也是尾节点last)
        first = newNode;
    else
        // 不是空链表的情况:将原来的尾部节点(现在是倒是第二个节点)的next指向需要插入的节点
        l.next = newNode;
    size++;  // 更新链表大小和修改次数,插入完毕
    modCount++;
}
  • linkBefore(E e,Node succ);在非空节点succ之前插入元素 e
/**
 * 将元素e插入到非空节点succ之前。
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 创建一个pred变量指向succ节点的前一个节点
    final Node<E> pred = succ.prev;
    // 创建一个新节点,他的prev设置为我们新建的pred变量,后节点设置为succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // succ的上节点(prev)指向新建的节点
    succ.prev = newNode;
    // 判断succ的前节点是否为null,为null,则把新节点设置为链表的头结点
    if (pred == null)
        first = newNode;
    else
        // 不为空把,succ的前一个节点的next指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}
  • unlinkFirst( Node f ){};删除LinkedList中的第一个节点。(该节点不为空,返回删除节点的值)。这是一个私有方法,我们不能够调用,assert f == first && f != null; 参数f是头结点,而且f不能为null
/**
 * 解除非空第一个节点f的链接。
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 定义一个变量element,值为待删除节点的值。
    final E element = f.item;
    // 定义变量next,值为:待删除的节点的下一个节点
    final Node<E> next = f.next;
    // f节点的值设置为空
    f.item = null;
    f.next = null; // help GC
    // 将变量next设置为头节点
    first = next;
    // 判断f的下一个节点是否为空,为空:把last设置为空
    if (next == null)
        last = null;
    else
        // 不为空,将next的前节点设置为空。next为头结点
        next.prev = null;
    size--;
    modCount++;
    return element;
}
  • unlinkLast(Node l){};删除LinkedList的最后一个节点(该节点不为空,并返回删除节点对应的值)
/**
 * Unlinks non-null last node l.
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 创建变量element,值为:待删除的节点的值
    final E element = l.item;
    // 创建变量 prev:值为:待删除的节点的前节点
    final Node<E> prev = l.prev;
    // 待删除的节点的值赋空
    l.item = null;
    l.prev = null; // help GC
    // 将last指向 新建的节点 prev 
    last = prev;
    // 判断待删除的节点的前节点是否为空,为空:该链表则为空链表,将头结点first赋null值
    if (prev == null)
        first = null;
    else
        // 不为空,将待删除的前节点的next指向 null
        prev.next = null;
    size--;
    modCount++;
    return element;//返回删除的节点的值
}
  • unlink(Node e);删除一个节点,该节点不为空
/**
 * Unlinks non-null node x.
 */
E unlink(Node<E> x) {
    // assert x != null;
    // 变量 element:值:要删除的节点的值
    final E element = x.item;
    // 新建变量:next,值:要删除的节点的下一个节点
    final Node<E> next = x.next;
    // 新建变量:prev,值:要删除的节点的上一个节点
    final Node<E> prev = x.prev;
    // 判断要删除的节点的上一个节点为空,为空:则删除的是头结点,将first指向新建的next
    if (prev == null) {
        first = next;
    } else {
        // 不为空:将要删除的节点的上一个节点的next指向要删除的节点的下一个节点
        prev.next = next;
        x.prev = null;
    }
    // 判断要删除的节点的下一个节点是否为空,为空:则删除的尾结点,将last指向prev,也就是指向要删除的节点的上一个节点
    if (next == null) {
        last = prev;
    } else {
        // 不为空,将要删除的节点的下一个节点的上节点指向-》要删除的节点的上个节点
        next.prev = prev;
        x.next = null;
    }
    // 这一步就把要删除的节点赋了空值,有助于gc回收
    x.item = null;
    size--;
    modCount++;
    return element;
}
  • Node node(int index); 计算指定索引上的节点,并返回。 这里LinkedList不是从头开始进行遍历,而是先比较一下index更靠近链表的头结点还是尾结点,然后进行遍历,获取对应index的节点
/**
 * 返回指定元素索引处的(非空)节点。
 */
Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

以上是一些辅助方法,在LinkedList的add,get,remove等方法中都会使用到相应的方法。

LinkedList中的contains(Object o);

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

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

indexOf(Object o)方法中分两种情况,

  1. 首先判断传入的参数 o 是不是空,

    1. 为空:for循环进行查找,找第一个节点的item的值==null的,找到返回对应的下标,没有则返回-1
    2. 不为空,for循环进行查找,找第一个节点的item的值与o相等的,找到返回对应的下标,没有返回-1;

个人认为看懂了上面的方法,其他的方法都简单明了。

LinkedList和ArrayList的区别

  • 顺序插入的速度ArrayList会快些,LinkedList的速度会稍慢一些。因为ArrayList只是在指定的位置上赋值即可,而LinkedList则需要创建Node对象,并且需要建立前后关联,如果对象比较大的话,速度会稍微慢一些
  • LinkedList占用的内存空间要大一些
  • 数组遍历的方式ArrayList推荐使用for循环,而LinkedList则推荐使用foreach,如果使用for循环,效率将会很慢。下面有测试代码
  • LinkedList做插入、删除的时候,慢在寻址,快在只需要改变前后Entrty的引用地址;ArrayList做插入、删除的时候,慢在数组元素的批量copy,快在寻址。

所以,如果待插入、删除的元素是在数据结构的前半段,尤其是非常靠前的位置的时候,LinkedList的效率将大大快过ArrayList,因为ArrayList将批量copy大量的元素;越往后,对于LinkedList来说,因为它是双向链表,所以在第2个元素后面和在倒数第2个元素后面插入一个元素在效率上基本没有差别,但是ArrayList由于copy的元素越来越少,操作速度肯定会越来越快

为什么不建议使用for循环迭代LinkedList

测试:

步骤:1、分别创建一个LinkedList和一个ArrayList;
    2、分别插入100000条数据
    3、分别使用for,foreach。iterator遍历,记录所用时间
LinkedList<String> linkedList = new LinkedList<String>();

ArrayList<String> arrayList = new ArrayList<String>();

for(int i = 0; i < 100000; i ++) {
    linkedList.add("linkedList -- " + i);
    arrayList.add("arrayList -- " + i);
}

// ------------------------foreach-----------------------
long befor = System.currentTimeMillis();
for(String ii : arrayList){
}
long after = System.currentTimeMillis();
System.out.println("Arraylist使用foreach遍历的时间是:"+(after-befor)+"ms");

befor = System.currentTimeMillis();
for(String ii : linkedList){
}
after = System.currentTimeMillis();
System.out.println("Linkedlist使用foreach遍历的时间:"+(after-befor)+"ms");
// ------------------------Iterator-----------------------
Iterator<String> arrayListIterator = arrayList.iterator();
befor = System.currentTimeMillis();
while(arrayListIterator.hasNext()) {
    arrayListIterator.next();
}
after = System.currentTimeMillis();
System.out.println("Arraylist使用Iterator遍历的时间是:"+(after-befor)+"ms");


Iterator<String> linkedListIterator = arrayList.iterator();
befor = System.currentTimeMillis();
while(linkedListIterator.hasNext()) {
    linkedListIterator.next();
}
after = System.currentTimeMillis();
System.out.println("Linkedlist使用Iterator遍历的时间是:"+(after-befor)+"ms");
// -------------------------for----------------------------

befor = System.currentTimeMillis();
for (int i = 0; i < arrayList.size(); i++) {
    arrayList.get(i);
}
after = System.currentTimeMillis();
System.out.println("Arraylist使用for遍历的时间是:"+(after-befor)+"ms");



befor = System.currentTimeMillis();
for (int i = 0; i < linkedList.size(); i++) {
    linkedList.get(i);
}
after = System.currentTimeMillis();
System.out.println("Linkedlist使用for遍历的时间是:"+(after-befor)+"ms");


// 第1次运行结果
/**
  * Arraylist使用foreach遍历的时间是:7ms
  *  Linkedlist使用foreach遍历的时间:10ms
  * Arraylist使用Iterator遍历的时间是:2ms
  * Linkedlist使用Iterator遍历的时间是:1ms
  * Arraylist使用for遍历的时间是:0ms
  * Linkedlist使用for遍历的时间是:35070ms
  */
// 第2次运行结果
/**
  * Arraylist使用foreach遍历的时间是:2ms
  *  Linkedlist使用foreach遍历的时间:4ms
  * Arraylist使用Iterator遍历的时间是:1ms
  * Linkedlist使用Iterator遍历的时间是:1ms
  * Arraylist使用for遍历的时间是:0ms
  * Linkedlist使用for遍历的时间是:37262ms
  */

10万条记录。可以看出,不管是foreach还是Iterator,速度都差别不大,但是对于for循环时,linkedList的for循环遍历的时间很长

原因分析

LinkedList的get();

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

由于LinkedList是双链表,所以通过index去获取的时候回判断index是在前半段还是后半段,前半段正序遍历,后半段倒序遍历,这也是Linked优化的部分。那么为什么使用不同的for循环遍历LinkedList会很慢呢?
例:

  • get(0):直接拿到Node(0)的地址,获取里面的数据
  • get(1):先拿到Node(0)的地址,在从Node(0)中获取到Node(1)的地址,在拿到Node(1)的数据
  • get(2):先拿到Node(0)的地址,在从Node(0)中获取Node(1)的地址,在从Node(1)中获取Node(2)的地址,在获取到Node(2)的数据

以此类推,也就是说,LinkedList在get任何数据的时候,会把前面的数据走一遍,随着LinkedList的容量越来越大,时间的消耗就会越来越长 所以说建议使用迭代器或者foreach循环去遍历LinkedList,这种方式是直接按照地址去找数据的,将大大提升遍历LinkedList的效率。

评论

暂无评论