Java数据结构深入学习之LinkedList

「爱情、让人受尽委屈。」 2024-03-23 10:48 61阅读 0赞

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--)