Java(List接口)集合LinkedList源码分析

概述

LinkedList是通过双向链表实现的，它拥有双向链表的优缺点，即顺序迭代访问、增删操作时效率较高，但是通过下标访问时效率较低。

类关系结构图

关键字段

transient int size = 0; // 链表的长度

/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first; // 链表的首节点

/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
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;
    }
}

get方法

虽然传入的是下标，但本质上还是遍历链表中的数据

Node<E> node(int index) {
          
   
    // assert isElementIndex(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;
    }
}

set方法

public E set(int index, E element) {
          
   
    checkElementIndex(index);// 检查下标是否合法
    Node<E> x = node(index); // 根据下标获取对应的node对象
    E oldVal = x.item; // 记录原来的值
    x.item = element; // 赋予新的值
    return oldVal; // 返回修改之前的值
}