Java集合之List类型--LinkedList底层源码剖析

Java集合之List类型--LinkedList底层源码剖析

文章目录

• 1、linkedList简介
• 2、linkedList底层实现
• • 2.1、linkedList初始化
  • 2.2、 添加元素
  • 2.3、查找给定元素
• 3、总结

1、linkedList简介

  LikedList是List接口的实现类，与ArrayList不同的是它的底层实现不是数组，而是一个双向链表。由此我们可以知道，linkedList比起ArrayList更适合做插入删除等 *** 作，因为ArrayList在指定位置插入需要做元素的搬移，但是对于天生就支持插入的链表结构来说，只需要更改指针指向即可。而其对于数据的访问则不像ArrayList那么友好，由于数组的特性，由于内存区域的连续性，可以利用cpu缓存，能够获得更快的访问速度。和ArrayList相同，这个实现类也是线程不安全的类。同时，linkedList也可以用作队列和栈的结构，下面我们就来剖析剖析linkedList的底层实现原理。

2、linkedList底层实现 2.1、linkedList初始化

  话不多说，直接上源码：

// LikedList定义的实例变量

// list中的元素数量
transient int size = 0;
// 指向头节点的指针
// 指向尾节点的指针
transient Node first;
transient Node last;
.....
// Node的定义
private static class Node {
    E item;
    Node next;
    Node prev;

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

  从上面的定义我们不难给出linkedList的数据结构示意图：

  每个节点由三个要素组成，一个指向后一个节点的next指针，一个指向前一个节点的pre指针，以及data数据域。一个first指针始终指向第一个节点，last指针指向尾节点。可以看到Node实际上是linkedList的一个静态内部类，它可以访问外部类的private静态字段和静态方法，接下来我们来看看linkedList的构造方法：

// 无参构造方法，构造一个空List
public linkedList() {
}
// 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序
// 先初始化，再调用添加 *** 作
public linkedList(Collection c) {
    this();
    addAll(c);
}

2.2、 添加元素

// 向List表尾添加元素
public void addLast(E e) {
    linkLast(e);
}
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 将元素e插入List表尾
void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    // 如果此时为一个空列表，则直接将first指针指向新节点
    if (l == null)
        first = newNode;
    // 否则，将原last节点的next指针指向新节点
    else
        l.next = newNode;
    // 列表元素数量加1
    size++;
    modCount++;
}

  从linklast()方法中可以知道，首先将last节点复制给一个final字段 l，再创建一个新节点NewNode，并将next指针指向null。并将原list的尾节点传入Node的构造方法，使得新节点的prev指针指向原list的尾节点，然后让last指针指向这个新节点，如果此时列表中海未添加任何元素，则直接将first指针指向新节点。否则，将原last节点的next指针指向新节点。向表头插入元素也是同理，因此向表头和表尾插入元素其时间复杂度为O(1)。下面我们再看看向指定位置插入元素是怎么实现的

// 向列表中指定位置插入一个元素
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
    }

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 在指定位置插入元素
 void linkBefore(E e, Node succ) {
    // assert succ != null;
    final Node pred = succ.prev;
    // 创建一个新节点newNode，并让这个新节点的prev指针指向pred节点
    final Node newNode = new Node<>(pred, e, succ);
    // 让后一个节点的prev指针指向新节点
    succ.prev = newNode;
    // 如果列表为空则直接将first指针指向新节点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

//
Node node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

  在指定位置插入元素时首先会进行位置的合法性，如果合法则进行下一步，否则抛出IndexOutOfBoundsException这个异常。如果要插入的位置等于列表中元素的数量，也急速hi说向表尾插入，则直接调用linkLast()方法，在上面我们已经解析过了，如果在其他位置则调用linkBefore()方法。
  我们看到在这个方法调用的时候，第一个参数传入了element对象，第二个参数则传入了node(index)，我们先着重看一下这个方法。首先将要插入的位置和列表元素数量的1/2做比较，如果此位置小于后者，则我们就从表头开始遍历，直到找到index所对应的节点返回，反之，如果要插入的元素位置大于数量的1/2，那么就从表尾进行遍历，直到找到索引对应的节点返回。这样做得目的在于优化遍历的次数。
  我们再回到linkBeforre()方法中，先将找到的对应节点位置的前一个节点赋值给pred变量，让prevd变量指向它，然后创建一个新节点newNode，并让这个新节点的prev指针指向pred节点，如果列表不为空则将pred节点的next指针指向新节点。这样就完成了插入 *** 作，可以看到当我们将指定位置插入元素时，可以从头遍历，或者从尾部遍历，因此时间复杂度为O(n)；

2.3、查找给定元素

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

  可以看到再contains()方法内部实际调用了indexOf()方法，整个查找的逻辑也很简单，如果给定元素为null，则从头部遍历，然后用==符号判断节点的数据域是否为null。如果不为null，则用equals()方法判断，每次index的值加1，直到找到给定元素为止，没找到就返回-1。我们再来看看根据索引查找的方法

// 根据索引查找的方法
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

  可以看到，首先也是根据给定索引先检查索引的合法性，然后直接调用node(index)方法，这个方法我们在前面剖析根据索引插入的实现中看到过，这个方法可以根据索引所在列表的位置从而判断是从表头开始遍历还是从表尾开始遍历。因此我们可以得出结论，在linkedList中查找算法的时间复杂度为O(n)，即便是指定索引index，也无法做到ArrayList那样在O(1)找到元素，这是由链表的底层结构决定的，注意不要认为只要通过索引获取元素就是O(1)。
  此外，我们还可以得出一个结论，只要方法中需要在指定位置处做某种 *** 作的，例如查找，添加，删除，都需要调用node(index)这个内部私有方法，先找到元素，然后做相关 *** 作。

3、总结

  linkedList容器的底层数据结构是双向链表，它能够快速的进行插入，删除等 *** 作，并且不需要像ArrayList那样进行扩容，因为链表天生就支持扩容。但是需要注意的一点是，除了在表头和表尾的插入、删除 *** 作，在其他位置 *** 作，其复杂度并非O(1)，我们所说的插入删除O(1) 仅仅是指这个 *** 作本身，由于只是改变指针指向，但是在找到这个位置的过程是需要耗时的。
  linkedList可以当作队列和栈使用，其原理就是在表头或者表尾进行数据 *** 作。