队列(Queue)：遵循的原则，先进后出，往队列尾塞元素，从队列头取元素。今天就来讲一下，最灵活的队列LinkedList ###### 概念 LinkedList 类是List，Deque 两接口实现类，既有像List集合一样线性操作特征，又有队列先进后出的特性约束。鉴于Deque是Queue的子接口，双端队列的特性让LinkedList成为最灵活的集合。 LinkedList 底层是一个双端链表，可以当作堆栈、队列或双端队列使用。如果是经常执行插入和删除操作，可以考虑使用。 LinkedList 所有方法没有加锁操作，是线程不安全的，但可以额外加锁实现 ```java List list = Collections.synchronizedList(new LinkedList(...)); ``` LinkedList 是一个非阻塞队列 ###### 常用的方法 实现List接口的方法： add(E)/set(index, E) : 添加元素/指定位置添加元素 get(index) : 获取指定位置的元素 remove(index)/remove(E) ： 删除指定位置元素/删除元素 实现Queue接口方法： add(E)： 在队尾加入元素，不合法会抛异常 offer(E)：在队尾加入元素，不合法会返回false remove()：获取并移除此队列的头，不合法抛异常 poll()：获取并移除此队列的头，不合法返回null element()：获取，但是不移除此队列的头，不合法抛异常 peek()：获取，但是不移除此队列的头，不合法返回null 实现Deque： 太多了， 看下表   ```java public class App { public static void main(String[] args) { LinkedList queue = new LinkedList(); queue.add("a"); //队尾添加a queue.offer("b"); //队尾添加a queue.add("c"); //队尾添加a queue.offer("d"); //队尾添加a System.out.println(queue); //[a, b, c, d] System.out.println(queue.poll()); //获取队头并删除 同：remove System.out.println(queue); //[b, c, d] System.out.println(queue.element()); //获取队头不删除 同：peek System.out.println(queue); //[b, c, d] queue.addFirst("e"); //队头加 System.out.println(queue); //[e, b, c, d] queue.addLast("f"); //队尾加 System.out.println(queue); //[e, b, c, d, f] queue.removeFirst(); //队头删除 System.out.println(queue); //[b, c, d, f] ：同pollFisrt queue.removeLast(); //队尾删除 System.out.println(queue); //[b, c, d] ：同pollLast } } ``` ###### 源码结构 ```java public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable transient Node first; //队列头 transient Node last; //队列尾 } ``` ```java private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } ``` add方法 ```java public boolean add(E e) { linkLast(e); return true; } ``` ```java void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } ``` remove方法： ```java public E remove() { return removeFirst(); } public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; final Node next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } ``` get方法： ```java public E get(int index) { checkElementIndex(index); return node(index).item; } Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } ``` 代码比较简单，都是基础的链表操作，看看就好 ###### 结语 LinkedList在并发环境下使用频率较低，这里就不讨论如何使用了， 可以参照之前的ArrayList篇。本篇目的仅仅是回顾一下Queue队列的使用，为后面介绍其他队列做铺垫。