源码解析java集合框架，LinkedList源码

傷城~ 2022-03-02 11:57 417阅读 0赞

### 一、LinkedList剖析 ###

LinkedList也是List接口下的一个实现类，LinkedList是一个**双向链表**，**底层数据结构为双向链表****。**

![20190320143318132.png][] LinkedList数据结构

LinkedList采用双向链表存储方式，优缺点如下

缺点：遍历、随机访问元素效率低下。

优点：插入、删除元素效率非常高，只需改变修改元素关联的内存指针即可。

### 二、源码解读 ###

我们直接看LinkedList类的add()方法。

public boolean add(E e) {
        linkLast(e);
        return true;
    }

/**  Links e as last element.  */
    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++;
    }

LinkedList每个元素都是一个Node对象，Node为LinkedList的一个内部类。

add(e)方法每次都是把元素加到链表的末端。

linkLast()方法中先是取到当前末端元素last，在把新元素追加到last后面，新元素成为新的末端元素，赋值给last。

Node有三个属性：

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

node对象中存放着前一个元素和后一个元素，item为元素的值。LinkedList存放了整个链表的首元素Node<E> first和末端元素Node<E> last。

> 后语，与ArrayList相比，LinkedList增加、移除元素不需要移动任何元素，增删的效率高。但查询访问效率低。有一定增删操作的数据还是建议使用LinkedList。

[20190320143318132.png]: /images/20220302/dacf3db8a58f40deb1e868ac69a19143.png