鏈表

這里首先解釋一下什么是鏈表：
（1）鏈表是一種數(shù)據(jù)結(jié)構(gòu)懂诗；
（2）鏈表中的節(jié)點(diǎn)擁有指向另一個(gè)節(jié)點(diǎn)的數(shù)據(jù)值赢乓；
（3）如果一個(gè)節(jié)點(diǎn)擁有指向后繼節(jié)點(diǎn)的引用，這樣的鏈表稱為單向鏈表年枕；如果擁有指向前繼節(jié)點(diǎn)的引用和后繼結(jié)點(diǎn)的引用，那么這個(gè)鏈表就是雙向鏈表乎完；

LinkedList鏈表集合：

（1）LinkedList直接實(shí)現(xiàn)了Deque（雙向隊(duì)列）接口熏兄、Deque接口繼承了Queue（隊(duì)列）、使其可以作為雙向鏈表這種數(shù)據(jù)結(jié)構(gòu)來(lái)使用树姨、操作元素摩桶。
（2）LinkedList以鏈表的形式存儲(chǔ)數(shù)據(jù)、對(duì)增刪元素有很高的效率帽揪、查詢效率較低硝清、尤其是隨機(jī)訪問(wèn)、效率不忍直視转晰。
（3）使用輸出輸入流對(duì)LinkedList進(jìn)行讀寫時(shí)候芦拿；會(huì)先講LinkedList的capacity讀取/寫入到流中、然后將元素一一讀取/寫入查邢。
（4）堆棧和隊(duì)列都可以 用鏈表數(shù)據(jù)結(jié)構(gòu)來(lái)描述蔗崎；
（5）LinkedList不同于ArrayList和Vector集合類之處在于，他能根據(jù)任意一個(gè)元素獲取他的前一個(gè)后一個(gè)元素扰藕。

LinkedList特有的方法：

• 增：
  （1）void addFirst(E object) 添加一個(gè)元素到鏈表的最首部缓苛；
  （2）void addLast(E object) 添加一個(gè)元素到鏈表的最尾部；
  （3）boolean offer(E o) 添加一個(gè)元素到鏈表的最尾部邓深；
  （4）boolean offerFirst(E e) 添加一個(gè)元素到鏈表的最首部
  （5）boolean offerLast(E e) 添加一個(gè)元素到鏈表的最尾部未桥；
  （6）void push(E e) 添加一個(gè)元素到鏈表的最首部；

• 查：
  （1）E get(int index) 返回鏈表的第index位的元素芥备；
  （2）E getFirst() 返回鏈表的第一個(gè)元素钢属；
  （3）E getLast() 返回鏈表的最后一個(gè)元素；
  （4）E peek() 返回鏈表的第一個(gè)元素门躯；
  （5）E peekFirst() 返回鏈表的第一個(gè)元素淆党；
  （6）E peekLast() 返回鏈表的最后一個(gè)元素；
  注意這里沒(méi)有g(shù)et（Object o）方法

• 刪：
  （1）E poll() 返回鏈表的第一個(gè)元素并刪除這個(gè)元素讶凉；
  （2）E pollFirst() 返回鏈表的第一個(gè)元素并刪除這個(gè)元素染乌；
  （3）E pollLast() 返回鏈表的最后一個(gè)元素并刪除這個(gè)元素；
  （4）E pop() 返回鏈表的第一個(gè)元素并刪除這個(gè)元素懂讯；
  （5）boolean removeFirstOccurrence(Object o)荷憋；刪除鏈表中第一個(gè)o元素；
  （6）boolean removeLastOccurrence(Object o);刪除鏈表中最后一個(gè)o元素褐望；

• Iterator/ListIterator
  對(duì)于所有的List集合都擁有這兩個(gè)迭代器方法勒庄；
  但是對(duì)于LinkedList集合類串前，他提供了這兩個(gè)迭代器特有的方法；
  （1）Iterator<E> descendingIterator() 实蔽；返回一個(gè)Iterator迭代器荡碾，這個(gè)迭代器迭代的方法是從最后一個(gè)元素向前開始迭代；API的解釋是“Returns an iterator over the elements in this deque in reverse （反轉(zhuǎn)）sequential order.”
  （2）提供了一個(gè)特有的ListIterator構(gòu)造函數(shù)：ListIterator<E> listIterator(int index)局装；這個(gè)迭代器坛吁，可以從集合的index角標(biāo)元素開始迭代，迭代方法可以是向后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:  ");
    //設(shè)置從鏈表尾部進(jìn)行迭代：
    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:  ");
    //設(shè)置從鏈表尾部進(jìn)行迭代：
    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();
  }
    }
  

總結(jié)：

LinkedList提供了眾多的增刪操作，實(shí)際應(yīng)用中我們可能使用不了這么多方法宣增，當(dāng)時(shí)我們可以根據(jù)返回值玫膀，操作對(duì)象是堆還是隊(duì)列，來(lái)選擇特定的方法爹脾；
模擬隊(duì)列先進(jìn)先出模式：

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

模擬堆：先進(jìn)后出

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