前言

Java 集合可分为Collection 和Map 两种体系:

• Collection接口：单列数据，定义了存取一组对象的方法的集合
  • List：元素有序、可重复的集合
    • ArrayList、LinkedList、Vector
  • Set：元素无序、不可重复的集合
    • HashSet、LinkedHashSet、TreeSet
• Map接口：双列数据，保存具有映射关系“key-value对”的集合，也称为键值对。
  • HashMap、LinkedHashMap、TreeMap、Hashtable、Properties

现在我们开始学习List接口的实现类LinkedList。

概述

• 对于频繁的插入或删除元素的操作，建议使用LinkedList类，效率较高

• 底层使用双向链表存储，内部没有声明数组，而是定义了内部类，内部类为Node类型的first和last，用于记录首末元素。同时，定义内部类Node，作为LinkedList中保存数据的基本结构。Node除了保存数据，还定义了两个变量：

  • prev变量记录前一个元素的位置
  • next变量记录下一个元素的位置

源码分析

构造器

先看空参的构造器：

LinkedList list = new LinkedList();

空参实例化时，内部声明了Node类型的first和last属性，默认值为null。size=0，modCount=0。

添加元素

当追加元素时，调用add方法：

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

而add方法里会调用linkLast方法

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

我们解析一下这段代码：

• 声明l节点是当前集合的last属性指向的节点，也就是上次最后的节点。
• 调用Node的实例化方法，把(l节点，新节点和null)做为参数，调用Node的构造器创建节点对象。
• last属性指向新节点
• 如果l节点是空的话，first属性指向新节点。否则l节点的next属性指向新节点。
• size和modCount都自增。

下面是创建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;
    }
}

这时如果是第一次追加元素，linkLast方法调用Node对象的构造器，实际上参数为：(l节点,新节点,null)，l节点是上次的最后节点，即null，会将当前对象的first和last属性指向null。

如果不是第一次追加元素，linkLast调用Node对象的构造器，实际上参数为：(l节点,新节点,null)，，l节点是上次的最后后节点，并且prev变量记录前一个元素的位置，next变量记录下一个元素的位置。

看到这里，你就明白为什么是双向链表，每个元素，也就是节点，每次实例化时都有prev和next属性指向某个元素或null，分别指向前后节点，first和last都记录当前集合的首末元素。无论新增还是插入元素，只要改变指向就行了，所以当频繁的插入和删除元素时比ArrayList效率高很多。

如果是ArrayList节点在中间插入元素，还得让后面的元素挪位，重新指向。

假设ArrayList集合里有1万个元素，我要从第三个位置插入，那集合的操作就很多了，后面每个元素都要挪位，这样子效率就很低了。

如果这是LinkeList集合，只需要移动指针，需要做的操作是：

• 将第二个元素的next指针指向要插入的元素
• 要插入的元素的prev指针指向第二个元素
• 要插入的元素的next指针指向第四个元素
• 第四个元素的prev指针指向要插入的元素

get和set方法

先源码：

• get

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

• set

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

• get和set方法都需要node方法来返回对象。

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        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--)
            x = x.prev;
        return x;
    }
}

这里很明显，当LinkedList随机get/set元素时，都需要从集合的首元素或者末元素开始，一个个遍历去找到想要寻找的元素，所以这里相对效率就低了。

而ArrayList集合底层是一个动态数组，直接通过下标就可以设置或者获取到元素了，所以在get和set方面，相对效率就高。

• ArrayList的get和set方法

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

E elementData(int index) {
    return (E) elementData[index];
}

新增方法

• void addFirst(Object obj)
• void addLast(Object obj)
• Object getFirst()
• Object getLast()
• Object removeFirst()
• Object removeLast()