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