No.3.2 LinkedList链表集合

链表

这里首先解释一下什么是链表：
（1）链表是一种数据结构；
（2）链表中的节点拥有指向另一个节点的数据值；
（3）如果一个节点拥有指向后继节点的引用，这样的链表称为单向链表；如果拥有指向前继节点的引用和后继结点的引用，那么这个链表就是双向链表；

LinkedList链表集合：

（1）LinkedList直接实现了Deque（双向队列）接口、Deque接口继承了Queue（队列）、使其可以作为双向链表这种数据结构来使用、操作元素。
（2）LinkedList以链表的形式存储数据、对增删元素有很高的效率、查询效率较低、尤其是随机访问、效率不忍直视。
（3）使用输出输入流对LinkedList进行读写时候；会先讲LinkedList的capacity读取/写入到流中、然后将元素一一读取/写入。
（4）堆栈和队列都可以用链表数据结构来描述；
（5）LinkedList不同于ArrayList和Vector集合类之处在于，他能根据任意一个元素获取他的前一个后一个元素。

LinkedList特有的方法：

增：
（1）void addFirst(E object) 添加一个元素到链表的最首部；
（2）void addLast(E object) 添加一个元素到链表的最尾部；
（3）boolean offer(E o) 添加一个元素到链表的最尾部；
（4）boolean offerFirst(E e) 添加一个元素到链表的最首部
（5）boolean offerLast(E e) 添加一个元素到链表的最尾部；
（6）void push(E e) 添加一个元素到链表的最首部；
查：
（1）E get(int index) 返回链表的第index位的元素；
（2）E getFirst() 返回链表的第一个元素；
（3）E getLast() 返回链表的最后一个元素；
（4）E peek() 返回链表的第一个元素；
（5）E peekFirst() 返回链表的第一个元素；
（6）E peekLast() 返回链表的最后一个元素；
注意这里没有get（Object o）方法
删：
（1）E poll() 返回链表的第一个元素并删除这个元素；
（2）E pollFirst() 返回链表的第一个元素并删除这个元素；
（3）E pollLast() 返回链表的最后一个元素并删除这个元素；
（4）E pop() 返回链表的第一个元素并删除这个元素；
（5）boolean removeFirstOccurrence(Object o)；删除链表中第一个o元素；
（6）boolean removeLastOccurrence(Object o);删除链表中最后一个o元素；
Iterator/ListIterator
对于所有的List集合都拥有这两个迭代器方法；
但是对于LinkedList集合类，他提供了这两个迭代器特有的方法；
（1）Iterator<E> descendingIterator() ；返回一个Iterator迭代器，这个迭代器迭代的方法是从最后一个元素向前开始迭代；API的解释是“Returns an iterator over the elements in this deque in reverse （反转）sequential order.”
（2）提供了一个特有的ListIterator构造函数：ListIterator<E> listIterator(int index)；这个迭代器，可以从集合的index角标元素开始迭代，迭代方法可以是向后hasNext（），和向前hasPervious（）；

迭代LinkedList的方法：

public class LinkedListDemo {
  public static void main(String[] args) {
    LinkedList<Integer> link = new LinkedList<>();
    link.add(1);//尾部
    link.push(2);//首部
    link.offer(3);//尾部
    System.out.println("----------使用listItertor从后往前迭代---------------");
    listItertor_Method_1(link);
    System.out.println("----------使用listItertor从前往后迭代----------------");
    listItertor_Method_2(link);//从前往后迭代
    System.out.println("----------用Itertor从后往前迭代---------------");
    Itertor_Method_1(link);
    System.out.println("----------用Itertor从前往后迭代---------------");
    Itertor_Method_2(link);
}
public static void listItertor_Method_1(LinkedList list){
  System.out.print("listIterator use pervious:  ");
  //设置从链表尾部进行迭代：
  for(ListIterator it = list.listIterator(list.size());it.hasPrevious();){
      System.out.print(it.previous() +" ");
  }
  System.out.println();
}
public static void listItertor_Method_2(LinkedList list){
  System.out.print("listIterator use next:  ");
  //设置从链表尾部进行迭代：
  for(ListIterator it = list.listIterator();it.hasNext();){
      System.out.print(it.next() +" ");
  }
  System.out.println();
}
public static void Itertor_Method_1(LinkedList list){
  System.out.print("Iterator use descendingIterator: ");
  for(Iterator it = list.descendingIterator();it.hasNext();){
      System.out.print( it.next()+ " ");
  }
  System.out.println();
}
public static void Itertor_Method_2(LinkedList list){
  System.out.print("Iterator use iterator:  ");
  for(Iterator it = list.iterator();it.hasNext();){
      System.out.print(it.next() + " ");
  }
  System.out.println();
}
  }

总结：

LinkedList提供了众多的增删操作，实际应用中我们可能使用不了这么多方法，当时我们可以根据返回值，操作对象是堆还是队列，来选择特定的方法；
模拟队列先进先出模式：

public class DuiLie {
  private LinkedList list;

public DuiLie(){
    list = new LinkedList();
}

public void myGet(){
    System.out.println(list.peek());
}
public void myPut(Object o){
    list.addLast(o);
}
public boolean isNull(){
    return list.isEmpty();
}
}

模拟堆：先进后出

public class Dui {
private LinkedList list ;
public Dui(){
    list = new LinkedList();
}
public void myGet(){
    System.out.println(list.getLast());
}
public void myPut(Object o){
    list.addLast(o);
}
public boolean isNull(){
    return list.isEmpty();
}
}

No.3.2 LinkedList链表集合