Java連結清單資料結構分析

Java連結清單我們用的比較多了。

LinkedList、LinkedHashSet、ListHashMap裡面底層都用到了連結清單，和數組同别的，可以認為是對數組的補充。

因為連結清單的頭節點、尾節點等特性，常常用來排序使用。可以用來實作棧，隊列等非線性。

連結清單由于查詢時候要從頭到尾周遊，是以查詢效率不如數組，但是連結清單的插入和删除速度更快。我們通常對頻繁使用插入和删除的集合推薦使用LinkedList、LinkedHashSet、ListHashMap

單向連結清單

雙向連結清單

下面是一種整型類型的連結清單實體類

public class ListNode {
  int val;
  ListNode next;

  public int getVal() {
    return val;
  }

  public void setVal(int val) {
    this.val = val;
  }

  public ListNode getNext() {
    return next;
  }

  public void setNext(ListNode next) {
    this.next = next;
  }

  @Override
  public String toString() {
    return "ListNode{" +
        "val=" + val +
        ", next=" + next +
        '}';
  }
}      

我們認識到連結清單實體類一般包括自己目前節點的值，第一個為頭節點，然後的參數為next，即為下一個節點。

連結清單通常由一連串節點組成，每個節點包含該節點的資料和指向上一節點或者下一節點的引用

增加：
add(E e)：在連結清單後添加一個元素；   通用方法
addFirst(E e)：在連結清單頭部插入一個元素；  特有方法
addLast(E e)：在連結清單尾部添加一個元素；  特有方法
push(E e)：與addFirst方法一緻  
offer(E e)：在連結清單尾部插入一個元素                                                                                                                                                  add(int index, E element)：在指定位置插入一個元素。      
offerFirst(E e)：JDK1.6版本之後，在頭部添加； 特有方法                                                                                                         offerLast(E e)：JDK1.6版本之後，在尾部添加； 特有方法

删除：
remove() ：移除連結清單中第一個元素;    通用方法  
remove(E e)：移除指定元素；   通用方法
removeFirst(E e)：删除頭，擷取元素并删除；  特有方法
removeLast(E e)：删除尾；  特有方法
pollFirst()：删除頭；  特有方法
pollLast()：删除尾；  特有方法
pop()：和removeFirst方法一緻，删除頭。 
poll()：查詢并移除第一個元素     特有方法    

查：
get(int index)：按照下标擷取元素；  通用方法
getFirst()：擷取第一個元素；  特有方法
getLast()：擷取最後一個元素； 特有方法
peek()：擷取第一個元素，但是不移除；  特有方法
peekFirst()：擷取第一個元素，但是不移除； 
peekLast()：擷取最後一個元素，但是不移除；
pollFirst()：查詢并删除頭；  特有方法
pollLast()：删除尾；  特有方法
poll()：查詢并移除第一個元素     特有方法