LinkedList 源码分析，你想知道的都在这里("LinkedList源码深度解析：你所关心的全部细节汇总")

原创

ithorizon 1个月前 (10-19) 阅读数 14 #后端开发

LinkedList源码深度解析：你所关心的全部细节汇总

一、LinkedList简介

LinkedList是Java集合框架中List接口的一个实现类，它通过双向链表的形式存储元素，提供了敏捷的随机访问和高效的插入、删除操作。LinkedList不仅可以作为一个列表使用，还可以作为队列、双端队列使用。下面我们将深入分析LinkedList的源码，揭示其内部实现和工作原理。

二、LinkedList的数据结构

LinkedList内部使用双向链表存储元素，每个元素都封装在一个Node对象中。Node对象包含三个基本属性：prev（指向前一个节点）、next（指向下一个节点）和item（存储元素值）。以下是LinkedList的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的构造方法

LinkedList提供了两个构造方法：无参构造方法和带有一个Collection类型参数的构造方法。无参构造方法会创建一个空的LinkedList，而带参数的构造方法会凭借传入的Collection初始化LinkedList。以下是LinkedList的构造方法的源码：


        public LinkedList() {
        }
        public LinkedList(Collection c) {
            this();
            addAll(c);
        }

四、LinkedList的核心方法

以下是LinkedList中几个核心方法的源码分析：

1. add(E e)

向LinkedList尾部添加一个元素。如果LinkedList为空，则新元素既是头节点也是尾节点；如果LinkedList不为空，则将新元素添加到尾部，并更新尾节点的next指向新元素。


        public boolean add(E e) {
            linkLast(e);
            return true;
        }
        void linkLast(E e) {
            final Node l = last;
            final Node newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }

2. get(int index)

获取LinkedList中指定索引处的元素。由于LinkedList是基于双向链表的，于是可以通过从头节点或尾节点开端遍历，以更高效地访问元素。


        public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
        Node node(int index) {
            Node x;
            if (index < size / 2) {
                x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
            } else {
                x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
            }
            return x;
        }

3. remove(int index)

删除LinkedList中指定索引处的元素。删除操作需要更新被删除元素前后的节点引用。


        public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
        E unlink(Node x) {
            E element = x.item;
            Node next = x.next;
            Node prev = x.prev;
            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
            }
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
            }
            x.item = null;
            x.next = null;
            x.prev = null;
            size--;
            modCount++;
            return element;
        }