LinkedList特性

• 按需分配空间，不需要预先分配很多空间
• 不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率为O(N/2)。
• 不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率为O(N)。
• 在两端添加、删除元素的效率很高，为O(1)。
• 在中间插入、删除元素，要先定位，效率比较低，为O(N)，但修改本身的效率很高，效率为O(1)。
• 长度无限制（）

实现接口

• Collection<E>，List<E>, Deque<E>,Queue<E>, Cloneable, Serializable

内部主要组成部分

 transient int size;
 transient LinkedList.Node<E> first;
 transient LinkedList.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;
    }
}

• 有头有尾有长度的双向链表

实现Queue接口拥有队列特性(先进先出)

• 队列特性方法

    //在尾部添加元素
    boolean add(E e);//队列为满时，抛出异常IllegalStateException
    boolean offer(E e);//队列为满时，返回false

    //删除头部元素，返回头部元素，并且从队列中删除
    E remove();//队列为空时，抛出异常NoSuchElementException
    E poll();//队列为空时，返回null

    //查看头部元素,返回头部元素，不改变队列
    E element();//队列为空时，抛出异常NoSuchElementException
    E peek();//队列为空时，返回null

实现Deque（双端队列）接口拥有栈（后进先出）、双端队列特性

• 栈特性方法

    //入栈，在头部添加元素
    void push(E e); //栈满时抛出异常IllegalStateException
    //出栈，返回头部元素，并且从栈中删除
    E pop();//如果为空抛出异常NoSuchElementException
    //查看栈头部元素，不修改栈
    E peek();//如果栈为空，返回null

• LinkedList当做栈用法

    Deque<String> stack = new LinkedList<>();

• 双端队列 (Deque)操作两端方法

    void addFirst(E e);
    void addLast(E e);
    E getFirst();
    E getLast();
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E peekFirst();
    E peekLast();
    E pollFirst();
    E pollLast();
    E removeFirst();
    E removeLast();

迭代器

Iterator<E> descendingIterator();
//向后迭代代码
public E next() {
            this.checkForComodification();
            if(!this.hasNext()) {
                throw new NoSuchElementException();
            } else {
                this.lastReturned = this.next;
                this.next = this.next.next;
                ++this.nextIndex;
                return this.lastReturned.item;
            }
}