4.5.1 概述

• LinkedList 具备了 List 接口的特性（有序、重复、索引）。
• LinkedList 地城实现原理是双向链表。
• LinkedList 的增删速度快、查询慢。
• LinkedList 是线程不安全的集合，运行速度快。

4.5.2 LinkedList 集合特有方法

• 元素插入到链表开头：

public void addFirst(E e) {}

• 元素插入到列表结尾：

public void addLast(E e) {}

• 获取链表开头的元素：

public E getFirst() {}

• 获取链表结尾的元素：

public E getLast() {}

• 移除链表开头的元素：

public E removeFirst() {}

• 移除链表结尾的元素：

public E removeLast() {}

• 示例：

package com.github.linkedlist.demo1;
import java.util.LinkedList;
/**
 * @author maxiaoke.com
 * @version 1.0
 */
public class Test {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("aa");
        linkedList.add("bb");
        linkedList.add("cc");
        linkedList.add("dd");
        System.out.println("linkedList = " + linkedList); // linkedList = [aa, bb, cc, dd]
        linkedList.addFirst("你好啊");
        System.out.println("linkedList = " + linkedList); // linkedList = [你好啊, aa, bb, cc, dd]
        linkedList.addLast("你好呢");
        System.out.println("linkedList = " + linkedList); // linkedList = [你好啊, aa, bb, cc, dd, 你好呢]
        System.out.println(linkedList.getFirst()); // 你好啊
        System.out.println(linkedList.getLast()); // 你好呢
        linkedList.removeFirst();
        System.out.println("linkedList = " + linkedList); // linkedList = [aa, bb, cc, dd, 你好呢]
        linkedList.removeLast();
        System.out.println("linkedList = " + linkedList); // linkedList = [aa, bb, cc, dd]
    }
}

4.5.3 LinkedList 的类成员变量

• 集合中存储元素个数的计数器：

transient int size = 0;

• 第一个元素：

transient Node<E> first;

• 最后一个元素：

transient Node<E> last;

4.5.4 LinkedList 的成员内部类 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;
    }
}

4.5.5 LinkedList 类的 add 方法

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

void linkLast(E e) {
    // 声明新的节点对象 = last
    final Node<E> l = last; // l = null
    // 创建新的节点对象
    final Node<E> newNode = new Node<>(l, e, null);
    // 新的节点赋值给最后一个节点
    last = newNode;
    if (l == null)
        // 将新的节点赋值给first
        first = newNode;
    else
        // 将新的节点赋值给最后一个节点的最后
        l.next = newNode;
    size++;
    modCount++;
}

4.5.6 LinkedList 类的 get 方法

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

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