LinkedList源码剖析

发布时间：2020-12-15 07:55:40 所属栏目：Java 来源：网络整理

导读：1，概述先来简单聊聊LinkedList的初步印象。LinkedList的底层数据结构是链表。链表的增删操作很快,查询操作比较慢。那么底层是单向链表还是双向链表，增删改查的操作是怎么操作链表的，我们来看看源码。 2，LinkedList核心成员变量 #链表的长度 transient i

1，概述

先来简单聊聊LinkedList的初步印象。LinkedList的底层数据结构是链表。链表的增删操作很快,查询操作比较慢。那么底层是单向链表还是双向链表，增删改查的操作是怎么操作链表的，我们来看看源码。

2，LinkedList核心成员变量

#链表的长度
transient int size = 0;
#链表的头结点
transient Node<E> first;
#链表的尾节点
transient Node<E> last;

很明显，LinkedList的元素是一个内部类，我们看看它的结构：

    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的底层是一个双向链表，链表中挂载着一个个的Node元素。

3，构造函数

3.1??LinkedList()

    public LinkedList() {
    }

3.2?LinkedList(Collection<? extends E> c)

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

?4，核心方法

? 4.1 add(E e)

    public boolean add(E e) {
        #看这名字应该是挂载到链表尾部，核心在这了，一会看看
        linkLast(e);
        return true;
    }

linkLast(E e)

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

集合上述源码画一个从无到有3个Node挂载到链表的过程：

当第一个节点插入的时候：

当第二个数据插入的时候：

当第三个数据插入的时候：

可以发现，每当插入数据，总是把数据挂载到后面形成一个双向链表结构。

add()方法需要学习的点：

1，LinkedList的底层数据结构是一个双向链表，整个链表有一个首节点，一个尾节点，然后各个节点（Node）也包含首位节点，这样就串成一个双向链表了。

2，从上图其实很容易猜到，如果查找元素，肯定是从首节点开始，依次遍历。所以我们来看看get()方法，验证下我们的猜想

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!