Java数据结构深入学习之LinkedList

LinkedList是链表结构，相比于ArrayList的数组结构，链表的增删效率更高，不需要移动其他元素，但是查找效率没有数组高，数组查找元素可以根据索引下标快速获取，而链表只能逐个遍历。

初始化

LinkedList<Integer> linkedList = new LinkedList<>();

源码解析

LinkedList有两个构造函数：

public LinkedList() {
}

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

在学习增删改查源码之前，我们得先了解一下链表结构的核心：Node节点：

// 容量
// transient关键字表示修饰的变量会在序列化时被忽略，即仅存在于内存而不会在磁盘里持久化
transient int size = 0;

// 第一个节点
transient Node<E> first;

// 最后一个节点
transient Node<E> last;

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为什么用transient修饰节点对象？

LinkedList中用双向链表来保存数据，节点内保存的是上一个和下一个节点的引用地址，在序列化后节点的引用地址会发生改变，所以需要自定义序列化。

源码解析

// 自定义链表的写序列化
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // 对没有被transient修饰的变量进行默认的序列化
    s.defaultWriteObject();

    // 序列化元素数量
    s.writeInt(size);

    // 序列化节点的值，而不序列化节点的引用地址
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

// 自定义链表的读序列化
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // 对没有被transient修饰的变量进行默认的序列化
    s.defaultReadObject();

    // 读数量
    int size = s.readInt();

    // 读取节点保存的值，创建新的节点，重新连接生成一个新链表
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

查找元素

源码解析

根据索引查找

public E get(int index) {
    // 检查索引位置合法性
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
	// size>>1表示除以2，相当于index小于size的一半
    // 因为链表只能遍历查找，所以这个if的目的是判断出index处于size的左侧还是右侧，来决定正序遍历查找还是反序遍历查找，这样可以减少遍历次数，加快查找效率
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 遍历循环到第index个元素，返回
        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;
    }
}

查找第一个节点元素

public E getFirst() {
    // first作为全局变量，可以直接返回
    final Node<E> f = first;
    if (f == null)
        // 在空链表的时候抛出异常
        throw new NoSuchElementException();
    return f.item;
}

查找最后一个节点元素

// 同理，不多解释
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

查找指定元素所在的索引

// 查找元素第一次出现的索引
public int indexOf(Object o) {
    int index = 0;
    // 比较相等用的是equals方法，所以要针对值是否为null做处理，不然会出现空指针异常
    if (o == null) {
        // 返回第一个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;
}

// 查找元素最后一次出现的索引
public int lastIndexOf(Object o) {
    // 原理同上，只是遍历顺序相反了
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

添加元素

源码解析

添加元素有5种方式

1. 添加元素到末尾

   linkedList.add(1);
   

2. 添加元素到指定位置

   linkedList.add(0, 1);
   

3. 添加元素到第一个节点

   linkedList.addFirst(0);
   

4. 添加元素到末尾

   linkedList.addLast(0);
   

5. 添加多个元素到指定位置

   linkedList.addAll(0, list);
   

6. 添加

   linkedList.addAll(list);
   

添加单个元素

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    // 获取最后一个节点引用
    final Node<E> l = last;
    // 创建一个新节点，记录上一个节点和值
    final Node<E> newNode = new Node<>(l, e, null);
    // 让新节点成功最后一个节点
    last = newNode;
    // 如果最后一个节点是null，表示该链表是空的，那么第一个节点也等于最后一个节点
    if (l == null)
        first = newNode;
    else
        // 最后一个节点不为null，修改其的下一个节点引用为新节点
        l.next = newNode;
    // 增加容量
    size++;
    modCount++;
}

添加元素到指定位置

public void add(int index, E element) {
    // 检查索引范围合法性
    checkPositionIndex(index);

    if (index == size)
        // index==size，说明要添加到链表末尾
        linkLast(element);
    else
        // 否则找到该索引节点，添加到其后面
        linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
    // 获取指定索引节点的前面节点引用
    final Node<E> pred = succ.prev;
    // 生成新节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 让新节点成为索引节点的前面节点
    succ.prev = newNode;
    // 索引节点的前面节点为空，表示其是first节点，此时让新节点成为新的first节点
    if (pred == null)
        first = newNode;
    else
        // 索引节点前面有节点，修改该节点的后面节点为新节点
        pred.next = newNode;
    // 增加容量
    size++;
    modCount++;
}

添加元素到第一个节点

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    // 获取第一个节点引用
    final Node<E> f = first;
    // 创建新节点
    final Node<E> newNode = new Node<>(null, e, f);
    // 让新节点称为第一个节点
    first = newNode;
    // 如果第一个节点为空，表示该链表是空的，那么最后一个节点也等于第一个节点
    if (f == null)
        last = newNode;
    else
        // 第一个节点不为空，修改其的上一个节点引用为新节点
        f.prev = newNode;
    // 增加容量
    size++;
    modCount++;
}

添加元素到末尾

代码相同，不解释。

添加多个元素到指定位置

public boolean addAll(int index, Collection<? extends E> c) {
    // 检查索引范围合法性，要在0到size之间，否则抛出IndexOutOfBoundsException异常
    checkPositionIndex(index);
	
    // 将传入的集合参数转换成数组
    Object[] a = c.toArray();
    // 得到数组大小
    int numNew = a.length;
    if (numNew == 0)
        // 空数组返回false
        return false;

    // 上一个节点和下一个节点
    Node<E> pred, succ;
    // 插入位置等于容量大小，表示插入到最后一个节点
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 查找索引为index的节点
        succ = node(index);
        // 获取索引为index节点的上一个节点引用
        pred = succ.prev;
    }

    // 循环插入节点
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        // 生成新节点对象
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果没有上一个节点，表示该节点为first节点，将新节点作为新的first节点
        if (pred == null)
            first = newNode;
        else
            // 有上一个节点，修改新节点该节点的下一个节点
            pred.next = newNode;
        // 修改节点引用，另for循环生效
        pred = newNode;
    }

    // 插入位置没有后续节点，则让刚刚插入的新节点为最后一个节点
    if (succ == null) {
        last = pred;
    } else {
        // 插入位置有后续节点，修改其下一个节点为该后续节点，该后续节点的上一个节点为新节点，使链表连接完整
        pred.next = succ;
        succ.prev = pred;
    }
	
    // 增加容量
    size += numNew;
    modCount++;
    return true;
}

添加多个元素

public boolean addAll(Collection<? extends E> c) {
    // 同添加多个元素到指定位置，只是自动设置一个size参数，表示添加到链表末尾
    return addAll(size, c);
}

删除元素

源码解析

删除第一个元素

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 删除第一个节点
private E unlinkFirst(Node<E> f) {
    // 获取待删除节点的值，用来返回
    final E element = f.item;
    // 获取传入元素的下一个节点
    final Node<E> next = f.next;
    // 置空传入元素
    f.item = null;
    f.next = null; // help GC
    // 修改第一个节点
    first = next;
    // 如果第一个节点为空，表示这是空链表，那么把最后一个节点也设置为空
    if (next == null)
        last = null;
    else
       	// 否则设置节点的前面节点为空
        next.prev = null;
    size--;
    modCount++;
    return element;
}

删除指定索引的元素

public E remove(int index) {
    // 检查索引范围合法性
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
	// 获取待删除节点的值，用来返回
    final E element = x.item;
    // 获取待删除节点的前后节点引用
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // 如果待删除节点的前面节点引用为空，表示此为first节点，则修改first的引用
    if (prev == null) {
        first = next;
    } else {
        // 更新前面节点的下一个节点
        prev.next = next;
        // 待删除节点的prev置空
        x.prev = null;
    }

    // 如果待删除节点的后面节点引用为空，则表示此为last节点，则修改last节点的引用
    if (next == null) {
        last = prev;
    } else {
        // 更新后面节点的下一个节点引用
        next.prev = prev;
        // 待删除节点的next置空
        x.next = null;
    }

    // 待删除节点的值置空，等待GC回收
    x.item = null;
    // 减少容量
    size--;
    modCount++;
    return element;
}

删除指定值的元素

public boolean remove(Object o) {
    // 找到第一个符合条件的节点并删除，然后通过unlink方法修改前后节点引用
    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;
}

删除最后一个元素

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
    // 待删除节点
    final E element = l.item;
    // 待删除节点的前面节点
    final Node<E> prev = l.prev;
	// 置空待删除节点的值、前面节点引用
    l.item = null;
    l.prev = null; // help GC
    // 新的last节点
    last = prev;
    // 如果prev为空，表示是空链表，则first也为空
    if (prev == null)
        first = null;
    else
        // 否则prev的next就设置为空，因为prev也是last
        prev.next = null;
    // 减少容量
    size--;
    modCount++;
    return element;
}

删除节点的时候要注意处理该节点的前后引用，避免因为删除的节点还持有其他节点的引用，导致其他节点后续被删除后无法被GC回收，导致的内存溢出问题。

更新元素

源码解析

public E set(int index, E element) {
    // 检查索引范围合法性
    checkElementIndex(index);
    // 找到该索引节点
    Node<E> x = node(index);
    // 获取节点旧值，用来返回
    E oldVal = x.item;
    // 修改节点值
    x.item = element;
    return oldVal;
}

其他方法

peek()

获取第一个元素，和getFirst()不同的是，如果链表为空：

• getFirst()会抛出NoSuchElementException异常
• peek()会返回null

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

element()

等于getFirst()

poll()

获取链表第一个元素，并在成功获取之后移除

如果是空链表则返回null

一些疑问

为什么LinkedList要做成双向链表？

因为链表结构的查找性能较差，所以双向链表记录了首尾节点，通过索引查询的时候可以判断索引处于链表左区间还是右区间再进行遍历，最少可以减少一半的遍历次数，能加快查询速度；并且提供了addFirst()和addLast()方法，可以快速的在链表开头和结尾添加元素。

结论是在不考虑空间浪费的情况下，双向链表更具有通用性和多功能性。

为什么ArrayList的使用率比LinkedList高这么多，甚至可以说没人用LinkedList？

通常来说，链表相较于数组的优势是增删快，而在ArrayList中，增删是通过数组拷贝实现的，也就是System.arraycopy()方法，这个方法比for循环遍历移动元素的效率要高，实际上比链表增删效率还要高，这涉及到现代CPU的多级缓存机制，所以大部分的场景，用ArrayList一把梭是没有问题的。