作者：whisper

链接：http://proprogrammar.com:443/article/560

声明：请尊重原作者的劳动，如需转载请注明出处

    先前说了一下算法题中常用的java数据结构，讲了java中常用的各种数据结构，今天要来详细说一下其中的LinkedList，还是以应用为主，不说让人头疼的原理实现，只讲一讲在实际中的具体应用（本人不爱看源码^-^），为什么要说LinkedList呢，大家可能都知道LinkedList和ArrayList一样都是List，有List的功能，不同之处在于ArrayList内部实现是数组，所以查询的效率比较高，但更新的效率较低，而LinkedList内部是双向链表，所以查询的效率比较低，但更新的效率较高。由于LinkedList内部实现是双向链表，通过双向链表这一结构，它又可以完成队列（双向队列），栈的功能，所以它在算法中的应用还是比较多的。下面就来具体说一说LinkedList。

    查询jdk1.8文档可以知道，LinkedList的继承结构是下面这样的：

    java.lang.Object
        java.util.AbstractCollection<E>
            java.util.AbstractList<E>
                java.util.AbstractSequentialList<E>
                    java.util.LinkedList<E>

    它继承了AbstractSequentialList，所以是个有序的List

    它实现了下面的接口：

    Serializable ， Cloneable ， Iterable <E>， Collection <E>， Deque <E>， List <E>， Queue <E>

    由于实现了Serializable ， Cloneable ， Iterable <E>，所以可以序列化，克隆与迭代操作，他既是一个List，又是一个Deque（双端队列，双端队列还可以实现队列和栈的功能）

    既然LinkedList内部是链表，那么查找的效率是不高的，如果用普通for循环去遍历，效率较低，如果换用增强的for循环或者迭代器进行遍历，那么效率就会提高，因为迭代时不是每次都从头部重新遍历，这是LinkedList使用时的一个小技巧。

    下面重点说一说做为双端队列（队列，栈）使用时的情况，双端队列即是两端都可以插入删除的队列，队列是在尾部插入，头部删除的数据结构，有先进先出的特点，栈是在一端插入删除，有先进后出的特点。当作为队列时，队头在List的索引最大处，队尾在索引0处。

    当用做栈时，常用的方法有下面四个：

    E peek() 查看栈顶元素
    void push(E e) 入栈
    E pop() 出栈
    boolean isEmpty() 判空

    当用做队列时，常用的方法有下面七个：

    boolean add(E e) 入队
    E remove() 出队
    E element() 查看队头元素

    上面三个方法，当因容量限制不能入队，空队列不能出队或查看队头元素时，会抛出异常，而下面三个类似操作是安全的，并不会抛出异常

    boolean offer(E e) 入队
    E poll() 出队
    E peek() 查看栈顶元素

    boolean isEmpty() 判空

    当用做双端队列时，常用的方法如下：

    void addFirst(E e)
    void addLast(E e)
    boolean offerFirst(E e)
    boolean offerLast(E e)

    上面四个方法在队头和队尾增加元素，add与offer的不同是offer是安全的，而add在容量超过限制时会抛出异常

    E getFirst()
    E getLast()

    E peekFirst()
    E peekLast()

    上面的四个方法查看队头队尾元素，get与peek的不同之处是peek是安全的，而get在队列为空时会抛出异常

    E removeFirst()
    E removeLast()
    E pollFirst()
    E pollLast()

    上面四个方法返回并删除队头队尾元素，remove与poll的不同之处在于poll是安全的，而remove在队列为空时会抛出异常

    boolean remove(Object o) 删除对应第一次出现的元素
    boolean removeFirstOccurrence(Object o) 删除对应第一次出现的元素
    boolean removeLastOccurrence(Object o) 删除对应最后一次出现的元素
    boolean contains(Object o) 判断是否包含一个元素
    int size() 计算队列的大小
    boolean isEmpty() 判断队列是否为空

    上面六个是增强和辅助的方法

    Iterator<E> iterator() 正向迭代器
    Iterator<E> descendingIterator() 反向迭代器

    上面两个返回迭代器

    LinkedList中的其它方法主要与他的列表属性相关，涉及到索引的操作，主要如下

    void add(int index, E element) 指定索引处增加元素
    boolean addAll(Collection<? extends E> c) 增加一个集合中的所有元素
    boolean addAll(int index, Collection<? extends E> c) 在指定索引处增加一个集合中的所有元素
    void clear() 清空
    E remove(int index) 删除指定索引处的元素
    E set(int index, E element) 修改指定索引处的元素
    E get(int index) 获取指定索引处的元素
    int indexOf(Object o) 获取指定元素的索引
    int lastIndexOf(Object o) 获取指定元素的最后一个索引
    ListIterator<E> listIterator(int index) 从指定索引开始的迭代器

    下面是一些辅助的方法

    Spliterator<E> spliterator() 迭代器，与Iterator不同的是这是并行迭代器
    Object clone() 浅克隆
    Object[] toArray() 转为数组
    <T> T[] toArray(T[] a) 转为指定类型的数组

    LinkedList在算法题中最大的用处就是作为队列（双端队列）或者栈使用了，作为栈使用时，可以代替Stack，因为Stack是线程安全的，所以一般使用时用LinkedList就可以了，另一个可以选择的双端队列是ArrayDeque，与LinkedList内部使用双向链表不同，ArrayDeque内部是用数组实现的。

亲爱的读者：有时间可以点赞评论一下