转载

Java集合中的LinkedList

什么是LinkedList

1 LinkedList 是一个 Doubly-linked list 双向连表，实现了 Deque 接口，该接口中定义了双向连表的一般操作。

2 LinkedList 也实现了 List 接口，所以 List 包含的基本方法（新增，删除，插入等）LinkedList都实现了。

3 LinkedList 也继承了 AbstractSequentialList 该类中定义了 顺序访问 所需实现的方法。

顺序访问：数据是有序的，访问也是有序的，获取元素必须从头开始遍历比对，不能直接以数组的方式获取指定索引位上的值。

随机访问：随机访问可以通过随机访问方法直接获取指定索引位上的值如 ArrayList 的 get(int index), set(int index, E element), add(int index, E element) and remove(int index) 等

双向连表数据结构及相关操作

1.基本结构

Java集合中的LinkedList

双向连表包含的基本元素包含 直接前驱、直接后继、值域 ，直接前驱指向前一个节点地址，直接后继指向后一个节点地址，直接前驱为空时是 头节点 ，直接后继为空时是 尾节点

2.基本操作(add,remove过程相反)

Java集合中的LinkedList

在双向连表中插入节点时需要改变插入位置前后两个节点的直接前驱和直接后继的指向如图所示

LinkedList的实现

LinkedList 在内部是通过一个私有的静态内部类来实现连表的，内部类代码如下

transient Node<E> first; // 头节点
transient Node<E> last; // 尾节点
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;
    }
}

LinkedList的操作都是围绕着 first last 这两个对象来进行。