Java 列表和队列（二）：剖析 LinkedList

1. LinkedList 实现的接口有

• LinkedList 除了实现了 List 列表接口外，还实现了 Deque 双端队列接口和 Queue 队列接口，可以按照队列、栈、双端队列的方式进行操作
• 栈和队列只是双端队列的特殊情况，它们的方法都可以使用双端队列的方法替代。不过，使用不同的名称和方法在概念上更为清晰

2. 怎样理解队列接口 Queue

• 队列的特点就是先进先出，即：在尾部添加元素、从头部删除元素

• 接口定义

  public interface Queue<E> extends Collection<E> {
      boolean add(E e); //在尾部添加元素
      boolean offer(E  e); //在尾部添加元素
      
      E remove(); //返回头部元素，并且从队列中删除
      E poll(); //返回头部元素，并且从队列中删除
  
      E element(); //查看头部元素，但不改变队列
      E peek(); //查看头部元素，但不改变队列
  }

3. Queue 接口的添加、删除和查看操作都有两种形式，区别是什么

• 区别在于，对于边界情况的处理不同

  • 边界情况是指队列为空或者队列为满
  • LinkedList 的实现中，队列长度没有限制，但别的 Queue 的实现可能有

• 队列为空时

  • element() 和 remove() 会抛出 NoSuchElementException 异常
  • peek() 和 poll() 返回特殊值 null

• 队列为满时

  • add() 会抛出 IllegalStateException 异常
  • offer() 只是返回 false

4. Java 中是怎样实现栈这种数据结构的

• 栈的特点是先进后出、后进先出

  • Java 中没有单独的栈接口
  • 栈相关方法包括在了表示双端队列的接口 Deque 中
  • 主要有 push()、pop()、peek() 三个方法

• 需要注意的是

  • Java 中有一个类 Stack（单词意思是栈），它也实现了栈的一些方法，如 push()、pop()、peek() 等，但它没有实现 Deque 接口
  • Stack 是 Vector 的子类，它增加的这些方法也通过 synchronized 实现了线程安全
  • 不需要线程安全的情况下，推荐使用 LinkedList 或 ArrayDeque

5. 使用 LinkedList 实现栈和队列

• 把 LinkedList 当做栈使用

  Deque<String> stack = new LinkedList<> ();
  stack.push("a");
  stack.push("b");
  stack.push("c");
  while(stack.peek() != null) {
      System.out.println(stack.pop()); //输出有三行，依次是 c、b、a
  }

• 把 LinkedList 当做队列使用

  Queue<String> queue = new LinkedList<> ();
  queue.offer("a");
  queue.offer("b");
  queue.offer("c");
  while(queue.peek() != null) {
      System.out.println(queue.poll()); //输出有三行，依次是 a、b、c
  }

6. LinkedList 的实现原理

• LinkedList 直译就是链表，内部实现是双向链表
• 在内存中，每个元素是单独存放的，元素之间通过链接连在一起，内存按需分配
• 在 add() 方法中，modCount++ 的目的与 ArrayList 是一样的，纪录修改次数，便于迭代中间检测结构性变化

7. LinkedList 的特点是什么

• 用法：LinkedList 是一个 List，但也实现了 Deque 接口，可以作为队列、栈、双端队列使用
• 原理：LinkedList 内部是一个双向链表，并维护了长度、头节点和尾节点
• 特点：不需要预先分配很多空间，按需分配空间
• 时间复杂度
  • 不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找。效率是 O(N/2)；不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较。效率是 O(N)
  • 在两端添加、删除元素的效率很高，为 O(1)；在中间插入、删除元素，要先定位，效率比较低，为 O(N)
  • 修改的效率很高，效率为 O(1)