【集合】LinkedList 源码分析

你的名字 2022-11-21 11:55 280阅读 0赞

# 前言 #

Github：[https://github.com/yihonglei/jdk-source-code-reading][https_github.com_yihonglei_jdk-source-code-reading]（java-collection）

主要分析 JDK8 版本源码。

# 一 LinkedList 概述 #

LinkedList基于双向链表实现（[链表数据结构][Link 1]），主要特性：

*  插入、删除较快，时间复杂度O(1)；
 *  查找慢，时间复杂度O(n)；

# 二 ListkedList 实例 #

简单demo。

package com.jpeony.collection.list;
    
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * LinkedList 基于双向链表实现
     *
     * @author yihonglei
     */
    public class LinkedListTest {
        public static void main(String[] args) {
            LinkedList<String> list = new LinkedList<>();
            // add
            list.add("one");
            list.add("two");
            list.add("three");
            // offer的底层是add
            list.offer("four");
            // pop出队
            // list.pop();
    
            for (int i = 0; i < list.size(); i++) {
                System.out.println("element[" + i + "] " + list.get(i));
            }
        }
    }

**运行结果**

![20201102192518213.png][]

# 三 LinkedList 底层实现 #

**重点分析下 offer()、pop()、get()、remove() 方法。**

## LinkedList 成员变量 ##

// 链表元素个数
    transient int size = 0;
    
    // 链表头结点
    transient Node<E> first;
    
    // 链表尾结点
    transient Node<E> last;

Node结点。

在Java语言中，链表通过引用实现链接，跟C中的指针是一个意思，一个指向对象的内存地址。

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

## 默认构造器 ##

public LinkedList() {
    }

## LinkedList\#offer() ##

往链表尾节点添加元素。offer()调用add()，也可以单独使用add()。

public boolean offer(E e) {
    	// 往链表尾结点添加元素
        return add(e);
    }

public boolean add(E e) {
    	// 往链表尾结点添加元素
        linkLast(e);
        return true;
    }

/**
     * Links e as last element.
     */
    void linkLast(E e) {
    	// 尾部结点
        final Node<E> l = last;
        // 构建新结点，通过Node构造器，可以知道新结点的上一个结点为原尾结点last
        final Node<E> newNode = new Node<>(l, e, null);
        // 尾部结点重新赋值为新节点，即尾部结点为新结点，尾部结点的下一个结点为null
        last = newNode;
        // 如果尾部结点为null，说明链表是空的，头节点和尾节点都赋值为新结点
        if (l == null)
            first = newNode;
        else // 原尾结点的下一个节点为新结点
            l.next = newNode;
        // 元素个数加1    
        size++;
        // 链表操作次数加1
        modCount++;
    }

因为链表是双向链表，构造器new Node<>(l, e, null)指定了前驱结点，l.next = newNode指定了后继结点才能把

新结点添加到链表尾结点。如果看得迷糊，看下双向链表的指针指向，再结合offer的源码，理解更深刻些。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70][]

## LinkedList\#pop() ##

pop() 从链表头结点弹出元素，即移出头结点，并返回头结点对应的元素值。

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

public E removeFirst() {
        // 如果头结点为null，抛出没有找到元素的异常
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        // 传入头结点，移出并返回头结点的值，具体实现
        return unlinkFirst(f);
    }

/**
     * Unlinks non-null first node f.
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        // 头结点对应的元素值
        final E element = f.item;
        // 头结点的下一个结点
        final Node<E> next = f.next;
        // 头结点的元素和头结点的下一个引用置为空，从链表上断掉
        f.item = null;
        f.next = null; // help GC
        // 用原头结点的下一个结点作为头结点
        first = next;
        // 如果只有一个结点，则尾结点也置为null，头尾都是null
        if (next == null)
            last = null;
        else
        	// 原头结点的上一个结点置为null，断掉原来对头结点的引用
            next.prev = null;
        // 链表元素减1
        size--;
        // 对链表的操作次数加1
        modCount++;
        // 返回原头结点对应的元素值，完成头结点的移出和返回值操作
        return element;
    }

本质操作就是把原头结点移出并返回对应的值， 同时把原头结点的第二个节点作为头结点，如果第二个节点是null，

说明链表只有一个元素，则移出后，头尾结点都置为null，然后jvm对应做GC回收。

## LinkedList\#get() ##

根据下标获取链表结点元素。

public E get(int index) {
    	// 判断下标是否合法
        checkElementIndex(index);
        // 获取下标对应结点并返回元素值
        return node(index).item;
    }

遍历查找 index 对应的结点，链表查找的时候通过分为两半范围查找，决定是从头结点还是尾结点开始遍历，提高查找效率。

Node<E> node(int index) {
        // assert isElementIndex(index);
    	// 二分思想查找元素，size >> 1即 size/2，确定元素从头结点还是尾结点开始遍历
        if (index < (size >> 1)) {
        	// 从头结点开始查找
            Node<E> x = first;
            // 从头结点开始遍历链表，找到index对应位置的结点返回，时间复杂O(n)
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
        	// 从尾结点开始查找
            Node<E> x = last;
            // 从尾结点开始遍历链表，找到index对应位置的结点返回，时间复杂O(n)
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

## LinkedList\#remove() ##

移出链表头结点，并返回对应元素值，跟pop()一样，最后都是调用removeFirst()，参考pop()实现。

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

# 四 总结 #

1、LinkedList 基于双向链表实现，非线程安全；

2、LinkedList 插入、删除快，查找慢；

[https_github.com_yihonglei_jdk-source-code-reading]: https://github.com/yihonglei/jdk-source-code-reading
[Link 1]: https://blog.csdn.net/yhl_jxy/article/details/83856317
[20201102192518213.png]: /images/20221120/ebd66fc5c9754ad98b7cac78a8171665.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70]: /images/20221120/eb7d596cfa754707b348c52e546abc4c.png