LinkedList 源码分析

简介

• LinkedList 继承了 AbstractSequentialList ，而 AbstractSequentialList 又继承于 AbstractList 。而 ArrayList 同样也继承了 AbstractList，所以会有很多方法类似。
• LinkedList 实现了 List, Deque, Cloneable, java.io.Serializable 这些接口

源码分析

定义：

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;
    }
}
// 创建一个空的链表对象
public LinkedList() {
}

// 接收一个集合类型作为参数，会创建一个与传入集合相同元素的链表对象
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

相关方法

插入元素:

• add(E e) :在 LinkedList 的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。
• add(int index, E element):用于在指定位置插入元素,时间复杂度为 O(n)
  • linkLast(E e):将元素节点插入到链表尾部
  • linkBefore(E e, Node<E> succ):在指定元素之前插入元素

获取元素：

• getFirst()：获取链表的第一个元素。
• getLast()：获取链表的最后一个元素。
• get(int index)：获取链表指定位置的元素。-

对于 node(int index) 方法：该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是尾开始遍历。

删除元素：

• removeFirst()：删除并返回链表的第一个元素。
• removeLast()：删除并返回链表的最后一个元素。
• remove(E e)：删除链表中首次出现的指定元素，如果不存在该元素则返回 false。
• remove(int index)：删除指定索引处的元素，并返回该元素的值。
• void clear()：移除此链表中的所有元素。

对于 unlink(Node<E> x) 方法：即实现：

迭代器操作：
从头到尾：hasNext，next
从尾到头：hasPrevious，previous