1.类继承体系

在这里插入图片描述
LinkedList是双向链表数据结构，它又实现了队列接口，所以又有队列的特性。

2.长度

链表不像数组那样有初始长度，除了头尾节点，每个节点都有对应的前后两个节点，只要内存够，理论上可以无限长。

3.重要方法

3.1 add(E e)

public boolean add(E e) {
  // 插入尾部
    linkLast(e);
    return true;
}

void linkLast(E e) {
   // 链表尾部last
    final Node<E> l = last;
    // 构造新的Node，它前节点就是插入之前的last，它后节点指向null
    final Node<E> newNode = new Node<>(l, e, null);
    // 新插入的节点变为尾节点
    last = newNode;
    if (l == null)
     // 链表本身为空情况，即当前为第一个插入
        first = newNode;
    else
      // 链表不为空，将原尾节点的下一节点指向 新插入的节点
        l.next = newNode;
    size++;
    modCount++;
}

以下为add(itemB) 前后对比图：
在这里插入图片描述

3.2 get(int index)

public E get(int index) {
   // 经验传入下标是否越界
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
   // 这里二分查找的思想
    if (index < (size >> 1)) {
      // 查找的下标在链表的前半段
      // 从前往后找，一直到index位置返回
        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;
    }
}

3.3 add(int index, E element)

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
       // 如果是插入到最后一个节点之后，上面已经介绍过linkLast
        linkLast(element);
    else
       // 非插入到最尾的情况
        linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
   // succ 是下标为index的节点
   // 并找出它的前节点 pred
    final Node<E> pred = succ.prev;
    // 生成新插入的节点e，将其前节点置为pred, 后节点置为succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 原index所在节点的前节点赋值为 新插入的节点e
    succ.prev = newNode;
    if (pred == null)
      // 如果原index前节点为空，说明原来index的节点就是first节点
      // 直接将新插入的节点设置为first 节点 
        first = newNode;
    else
      // 存在前节点，则将pred的next节点指向新插入的节点
        pred.next = newNode;
    size++;
    modCount++;
}

3.4 remove(int index)

 */
public E remove(int index) {
   // 检查是否越界 
    checkElementIndex(index);
    // 先找出下标为index的节点
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    // 下标index的后节点
    final Node<E> next = x.next;
    // 下标index的前节点
    final Node<E> prev = x.prev;

    if (prev == null) {
       // 如果前节点为null，则将first设置为next
        first = next;
    } else {
       // 将其(被移除节点)前节点的next指向其(被移除节点)的next
        prev.next = next;
        // 将被移除节点的前置 设置为null，为了垃圾回收吧，反正也没有引用了
        x.prev = null;
    }

    if (next == null) {
      // 表示移除的是链表最后一个节点，那么last设置为 prev(即被移除节点的前节点)
        last = prev;
    } else {
    // 将其(被移除)next节点的前置节点设置为prev
        next.prev = prev;
        // 被移除节点的next设置为null，帮助gc
        x.next = null;
    }
   
    x.item = null;
    size--;
    modCount++;
    return element;
}

3.5 indexOf(Object o)

 public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
        // 从头到尾遍历链表，判断是否为null，返回下标index
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
        // 从头到尾遍历链表，判断是否相等，返回下标index
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

3.6 lastIndexOf(Object o)

public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
    // 跟indexOf区别在于从尾部开始找
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}