乐趣区

Java集合中的LinkedList

jiezi

什么是 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. 基本结构

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

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

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

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 这两个对象来进行。

LinkedList 的其他相关内容

1.0 和 ArrayList 相比

虽然两种数据结构都可以当 List 来用，但是对于不同的数据操作而言，性能和开销是不等的。ArrayList 身为 Array 的实现，优势体现在 随机访问 上，而 LinkedList 是通过连表来实现，则其优势便体现在了 删除和插入 操作上。

2.0 线程安全问题

LinkedList 是线程不安全的实现，若要使用线程安全的 LinkedList 则需要你通过 List list = Collections.synchronizedList(new LinkedList(...)) 来获取。

3.0 并发修改异常

原理类似 ArrayList 参考：ArrayList

退出移动版