一、概要

• LinkedList 不是线程安全的；
• LinkedList 底层使用双向链表来存储数据；
• 可以添加任意元素，包括 null；
• LinkedList 实现了双向链表和双端队列特点（维护了两个属性 first 和 last 分别指向首节点和尾节点）；
• 每个节点（Node 对象），里面又维护了 prev、next、item 三个属性，其中通过 prev 指向前一个，通过 next 指向后一个节点，最终实现双向链表；
• 因为 LinkedList 底层使用链表进行存储，因此元素的添加和删除相对来说效率较高。

模拟双向链表

public class Main {
    public static void main(String[] args) {
        Node node = new Node(5);
        Node node1 = new Node("798string");
        Node node2 = new Node('C');
        Node node3 = new Node(true);
        // 连接四个节点，形成双向链表
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.prev = node2;
        node2.prev = node1;
        node1.prev = node;
        // 双向链表的头尾节点
        Node first = node;
        Node last = node3;
        // 从头到尾遍历
        while (first != null) {
            System.out.println(first.item);
            first = first.next;
        }
        // 从尾到头遍历
        while (last != null) {
            System.out.println(last.item);
            last = last.prev;
        }
    }
}
class Node {
    public Object item;
    public Node prev;
    public Node next;
    public Node(Object item) {
        this.item = item;
    }
    public Node(Object item, Node prev, Node next) {
        this.item = item;
        this.prev = prev;
        this.next = next;
    }
}

常用操作例子

public class Main {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        // add
        linkedList.add("asd");
        linkedList.add('A');
        linkedList.add(123);
        linkedList.add(123.1F);
        linkedList.add(1231L);
        linkedList.add(null);
        linkedList.add(false);
        // add / insert
        linkedList.add(2, "eeeeeeee");
        linkedList.add(4, "aaaaaaaaa");
        System.out.println(linkedList);
        // remove
        linkedList.remove();
        linkedList.remove(1);
        System.out.println(linkedList);
        // get
        System.out.println(linkedList.get(2));
        // 增强 for 遍历
        for (Object o : linkedList) {
            System.out.println(o);
        }
        // for 遍历
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
    }
}

源码分析

1、构造器

// 空参构造器
public LinkedList() {
}
// 传入一个 Collection 初始化链表
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

2、add

挑两个比较典型的 add 方法做分析

add ( E e )

// 将指定的元素添加到这个列表的末尾。该方法等同于addLast。
public boolean add(E e) {
    linkLast(e);
    return true;
}
// 链接 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++;
}

add( int index, E element )

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
// 检查 index 是否合法
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 链接 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++;
}
// 在非空节点 succ 之前插入元素 e。
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

3、remove

remove()

// 检索并删除该列表的头部（第一个元素）
public E remove() {
    return removeFirst();
}

// 移除并返回该列表中的第一个元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 解除非空的第一个节点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;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

remove( int index )

// 移除该列表中指定位置的元素。将任何后续的元素向左移动（从它们的索引中减去1）。返回从列表中被移除的元素。
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 判断参数 index 是否是一个现有元素的索引。
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

// 返回指定元素索引处的（非空）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;
    }
}

// 解除非空节点 x 的链接。
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

remove( Object o )

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

面试题

ArrayList 和 LinkedList 有什么区别？

1）底层数据结构

ArrayList 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是双向链表数据结构。（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别。）

2）是否支持快速随机访问

LinkedList 不⽀持⾼效的随机元素访问，⽽ArrayList⽀持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) ⽅法)。

3）内存空间占用

ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留⼀定的容量空间，⽽ LinkedList 的空间花费则体现在它的每⼀个元素都需要消耗⽐ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。