02-LinkedList

1. 概述

2. 用法

LinkedList 有两个构造方法：一个是默认的构造方法，另一个是接受已有的 Collection，定义如下：

public LinkedList(){
}
public LinkedList(Collection<? extends E> c) {
  this();
  addAll(c);
}

我们可以这样创建 LinkedList 对象，例如：

LinkedList<String> list = new LinkedList();
LinkedList<String> names = new LinkedList(Arrays.asList("ken","shaw","james"));

2.1 作为队列使用

与生活中的排队类似，特点是先进先出，在尾部添加元素，从头部删除

public interface Queue<E> extends Collection<E> {
  /**
  在尾部追加元素
  @throw IllegalStateException 如果队列满了的时候，会抛出该异常
  */
  boolean add(E e);
  /**
  在尾部追加元素
  @return false:如果队列满了的时候返回 false,反之返回 true
  */
  boolean offer(E e);
  /**
  删除头部元素，返回头部元素，并且从队列中删除
  @throw NuSuchElementException 在队列为空的时候抛出该异常
  */
  E remove();
  /**
  删除头部元素,返回头部元素，并从队列中删除
  如果队列为空,返回特殊值null
  */
  E poll();
  /**
  返回头部元素,但不改变队列
  @throw NuSuchElementExceptio 在队列为空的时候抛出该异常
  */
  E element();
  /**
  返回头部元素,但不改变队列
  如果队列为空,返回特殊值 null
  */
  E peek();
}

public static void queue(){
  Queue<String> queue = new LinkedList<>();
  queue.offer("a");
  queue.offer("b");
  queue.offer("c");
  while(queue.peek() != null){
    System.out.println(queue.poll());
  }
}

2.2 作为栈使用

后进先出，类似于放书，放的时候一件一件堆上去

public interface Deque<E> extends Queue<E> {
  /**
  入栈,在头部追加元素
  @throw IllegalStateException 如果栈满了抛出该异常
  */
  void push(E e);
  /**
  返回头部元素,并从栈中删除
  @throw NosuchElementException 如果栈为空抛出此异常
  */
  E pop();
  /**
  查看栈头部元素,不修改栈,如果栈为空,返回 null
  */
  E peek();
}

public static void stack(){
  Deque<String> stack = new LinkedList<>();
  stack.push("a");
  stack.push("b");
  stack.push("c");
  while(stack.peek() != null){
    System.out.println(stack.poll());
  }
}

2.2.1 Stack

2.2.2 语义明确的API

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();

队列为空时，get/remove 会抛出异常，而 peek/poll 会返回 null。队列满时候 add 会抛出异常，offer 会返回 false

Deque 接口还有一个迭代器方法，可以从后往前遍历：

public static void iteration() {
  Deque<String> names = new LinkedList<>();
  names.addLast("ken");
  names.addLast("shaw");
  names.addLast("james");
  Iterator<String> iterator = names.descendingIterator();
  while(iterator.hasNext()){
    System.out.println(iterator.next());
  }
}