連結清單（Linked List）
動态數組（Dynamic Array Or ArrayList）有一個明顯的缺點
- 可能會造成記憶體空間的大量浪費
能否用到多少記憶體就配置設定多少記憶體
- 連結清單可以做到這一點
連結清單是一種鍊式存儲的線性表，所有元素的記憶體位址不一定是連續的
連結清單的設計
連結清單LinkedList包括元素個數size以及頭結點first兩個成員變量
每一個節點中又包括本節點特征元素element以及對下一個節點的引用next
接口設計
連結清單的大部分接口和動态數組是一緻的
- 由于ArrayList與LinkedList的方法基本一緻，但是很多方法的實作是完全不同的。是以可以使用一個接口聲明所有的方法，使得這兩個類可以通過實作同一個List接口,實作同樣的功能。
/**
* 清單方法接口
* 接口隻是聲明，不需要實作
* @author l
*
* @param <E>
*/
public interface List<E> {
//接口類由于供實作他的類使用，是以預設都是public
static final int ELEMENT_NOT_FOUND = 0;
/**
* 元素的數量
*/
int size();
/**
* 是否為空
* @return
*/
boolean isEmpty();
/**
* 是否包含某個元素
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到最後面
* @param element
*/
void add(E element);
/**
* 傳回index位置對應的元素
* @param index
* @return
*/
E get(int index);
/**
* 設定index位置的元素
* @param index
* @param element
* @return
*/
E set(int index, E element);
/**
* 在index位置添加元素
* @param index
* @param element
*/
void add(int index, E element);
/**
* 删除index位置對應的元素
* @param index
* @return
*/
E remove(int index);
/**
* 檢視元素的位置
* @return
*/
int indexOf(E element);
/**
* 清除所有元素
*/
void clear();
//====以下是一些工具方法=========//
/**
* 確定索引正确
*/
void ensureRangeInternal(int index);
/**
* 確定插入時索引正确
*/
void ensureRangeOnAdd(int index); - 由于List定義的方法中，有一些方法的實作是完全一樣的，這些方法在兩個類中重複實作很備援，但是接口List又無法實作，這時我們就可以定義一個抽象類AbstractList實作接口List,并将在連結清單和動态數組中相同的實作方法在抽象類中實作，根據Java中抽象類的特性，其他不同實作的方法完全可以不用管，交給子類實作即可，是以可以讓ArrayList與LinkedList都繼承AbstractList,這樣就隻需要重寫需要的方法即可。
/**
* 抽象類用于抽取公共代碼，有些方法可以交給子類實作
* @author lidengyin
*
*/
public abstract class AbstractList<E> implements List<E>{
//也是公共代碼的一部分要對子類可用
protected static int size = 0;
/**
* 元素數量
*/
@Override
public int size() {
return size;
// TODO Auto-generated method stub
}
/**
* 是否為空
*/
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return size == 0;
}
/**
* 是否包含某個元素
*/
@Override
public boolean contains(E element) {
// TODO Auto-generated method stub
return indexOf(element) == List.ELEMENT_NOT_FOUND;
}
/**
* 添加元素到最後面
*/
@Override
public void add(E element) {
add(size, element);
// TODO Auto-generated method stub
}
/**
* 確定索引正确
*/
@Override
public void ensureRangeInternal(int index) {
// TODO Auto-generated method stub
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("inex out of bound");
}
}
/**
* 確定添加時索引正确
* @param index
*/
@Override
public void ensureRangeOnAdd(int index) {
// TODO Auto-generated method stub
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("index out of bound");
}
} - 在動态數組的設計中，我們用到了常量ELEMENT_NOT_FOUND，這個常量現在應該放在哪裡呢？首先抽象類abstract是不能new的，其次abstract抽象類隻是為了抽取公共代碼，對外界不可見的，但是常量如果是由子類調用，則對外可見，是以不能放在抽象類，，其次如果放在子類中，那麼回造成備援，是以最好還是放在接口List中，并且這樣如果判斷contiains,那麼直接判斷List.ELEMENT即可，不必自己在定義一個數字-1，List是一個接口，接口是供實作的，是以變量預設是public
- 其次對于變量size,由于我們抽取到abstract類中的代碼需要size變量，是以需要将他放在抽象類中，又由于也是公共代碼的一部分需要提供給子類使用，是以該變量不能私有，而是protected最好。
清空元素-clear()
實作方法
puvlic void clear(){
head = null;
size = 0;
} next需要設定為null嗎;
不需要，因為head設定為null,則第一個元素不再被引用，則第一個元素可以被回收，同樣第一個元素回收後，第二個元素不再被引用可以被回收，以此類推連結清單的記憶體都會被回收，不需要額外設定null;
添加元素 add(int index, E element)
添加元素考慮兩種情況
添加首部情況
如果我們是添加首部，那麼應該使得head指向建立的節點，并使得建立節點的指向的下一個節點是head,注意并不是head.next,我這裡就是有點短路了，以為是head.next，我還在想怎麼不考慮是空連結清單的情況，确實是傻了
if(index == 0){
head = new Node(element, head);
} 其他部分添加情況
其他部分的添加就比較簡單了，隻要擷取index-1個節點，新節點指向index-1節點的下一個節點，index-1節點再指向新節點即可。
pre.next = new Node(element, pre.next); node方法用于擷取index位置的節點
- 由于很多方法需要擷取某一個index的節點，但是get傳回的E類型的元素，是以就需要寫一個私有方法，進行實作。這裡我開始把檢查索引的方法沒有放在裡面，在聽老師講了一遍才把他放了進來，也确實是這樣。
- 這個循環是比較有意思的，因為不是數組沒有序号，是以我們需要根據索引來判斷循環多少次得到這個節點。
public Node<E> note(int index){
ensureRangeInternal(index);
Note newHead = head;
for(int i = 0; i < index; i ++){
newHead = newHead.next;
}
return newHead;
} 删除元素 remove(int index)
删除元素也要考慮兩種情況
删除首部
删除首部我們就不需要考慮空連結清單的情況了陰我我們在ensureRangeInternal中可以保證排除空連結清單的情況，那麼排除空連結清單後，我們隻需要将連結清單首部指向該首部的引用即可。
if(index == 0){
head = head.next;
} 删除其他部分
其他部分的話還是先拿到prev,然後prev.next=prev.next.next即可
Node<E> prev = node(index-1);
prev.next = prev.next.next; 推薦神奇的網站
https://visualgo.net/zh
附上自己寫的LinkedList代碼
package com.ldy;
import java.awt.HeadlessException;
import java.security.PublicKey;
import java.util.Iterator;
/**
* 連結清單實作
* @author lidengyin
* 由于父類是抽象類，是以必須是實作父類沒有實作的方法
*/
public class LinkedList<E> extends AbstractList<E>{
private Node<E> head;
/**
* 由于隻是在Linkist内部使用，是以隻需要實作一個内部類即可
* 内部類中不要聲明private
* @author l
*
* @param <E>
*/
private static class Node<E>{
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
/**
* 傳回index位置的元素
*/
@Override
public E get(int index) {
Node<E> node = node(index);
// TODO Auto-generated method stub
return node.element;
}
@Override
public E set(int index, E element) {
//擷取節點
Node<E> node = node(index);
//擷取舊元素
E oldElement = node.element;
//覆寫舊元素
node.element = element;
// TODO Auto-generated method stub
return oldElement;
}
@Override
public void add(int index, E element) {
// TODO Auto-generated method stub
//確定添加時索引正确
ensureRangeOnAdd(index);
//判斷是否為空連結清單
//添加在首部
if (index == 0) {
head = new Node<E>(element, head);
}else {
//找到索引所在節點
Node<E> prev = node(index-1);
prev.next = new Node<E>(element, prev.next);
//如果是添加在尾部，也是可以滿足的。
}
size ++;
}
/**
* 删除index位置對應的元素
*/
@Override
public E remove(int index) {
// TODO Auto-generated method stub
//確定索引正确
ensureRangeInternal(index);
size --;
//擷取原有節點；
E oldElement;
//如果是第一個頭部
if (index == 0) {
oldElement = head.element;
head = head.next;
}else {
//找到前驅節點
Node<E> prev = node(index-1);
//得到原有節點内容
oldElement= prev.next.element;
//删除原有節點
prev.next = prev.next.next;
}
return oldElement;
}
/**
* 檢視元素位置
*/
@Override
public int indexOf(E element) {
// TODO Auto-generated method stub
//如果連結清單為空，就可以報錯了
if (head == null) {
throw new NullPointerException();
}
//自定義連結清單則element是null是有可能的。
Node<E> newHead = head;
//如果連結清單為空
if(element == null) {
for(int i = 0; i < size; i ++) {
if (newHead.element == null) {
return i;
}
newHead = newHead.next;
}
}else {
//如果連結清單不為空
for(int i = 0; i < size; i ++) {
if (newHead.element.equals(element)) {
return i;
}
newHead = newHead.next;
}
}
//傳回沒有找到
return ELEMENT_NOT_FOUND;
}
/**
* 清除所有元素
*/
@Override
public void clear() {
// TODO Auto-generated method stub
//切斷對第一個元素的引用，則第一個元素回收，
//那麼第二個元素引用也會消失，則第二個元素回收
//以此類推，全都會回收。
head = null;
size = 0;
}
//===========内部工具類=============//
/**
* 擷取該索引處Node
* @param index
* @return
*/
private Node<E> node(int index) {
ensureRangeInternal(index);
Node<E> newHead = head;
for(int i = 0; i< index; i ++) {
newHead = newHead.next;
}
return newHead;
}
@Override
public String toString() {
// TODO Auto-generated method stub
Node<E> newHead = head;
StringBuilder builder = new StringBuilder();
builder.append("size:").append(size).append(",[");
for(int i = 0;i<size; i ++) {
if(i != 0) {
builder.append(",");
}
builder.append(newHead.element);
newHead = newHead.next;
}
builder.append("]");
return builder.toString();
}
} leetcode_237_删除連結清單中的節點
https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
題目告訴我們無法通路head節點，就是在告訴我們，無法拿到目标節點的前驅節點， 隻能通過用後繼節點覆寫目标的節點的方式解題。
我們要覆寫一個節點不是說直接改變位址引用，這樣是做不出來的，而是将節點中所有的元素實作覆寫。比如
public class ListNode{
int val;
ListNode next;
} 我們就需要用後繼節點的val元素覆寫原來的val,同時用後繼節點的next覆寫原來的位址引用。即，
public void deleteNode(ListNode node){
node.val = node.next.val;
node.next = node.next.next;
} _206_反轉連結清單_遞歸
https://leetcode-cn.com/problems/reverse-linked-list/submissions/
根據題目描述，我們先選擇用遞歸的方式解決。
我的思路是，既然整個連結清單都需要反轉，那麼每一段長度遞減的連結清單也都需要反轉，這就有了遞歸的理論基礎，每一個反轉後的小連結清單加上遞增連結清單的頭部作為字迹的尾部即可，這樣不斷反推就可以得到反轉連結清單。
比如說1，加上遞增連結清單21的頭部2作為自己的尾部就是反轉連結清單12，再比如說321，已經反轉的12加上頭部3作為自己的尾部就是反轉連結清單123.
是以我們首先要做的就是遞推到隻剩一個節點，這樣本身就已經翻轉了，然後開始不斷加尾部反推。代碼如下：
public ListNode reverseList(ListNode head) {
//如果是空連結清單，或者隻有一個節點的連結清單直接傳回
if (head == null || head.next == null) {
return head;
}
//找到連結清單的尾部，作為新節點的頭節點
//這裡要知道，head.next才是尾節點，傳回的就是尾節點
//也就是新連結清單的首節點
ListNode newHead = reverseList(head.next);
//設定尾節點
// ListNode oldEnd = head.next;
// ListNode newEnd = oldEnd.next = head;
//如果以後忘了就看上面的注釋的兩行，這樣就可以避免從新的頭部開始循環。
head.next.next = head;
//尾節點的後繼肯定是null
head.next = null;
//傳回新節點的頭節點
return newHead;
} 這裡還有幾個關鍵點
- 首先當空連結清單和隻有一個節點的連結清單本身就是反轉的，直接傳回就行
- 其次，反轉連結清單增加自己的尾部，有兩種方式，一種是利用while循環，從首部周遊到尾部；這樣多了一個循環耗時；另一種方式是利用head節點，我們反轉節點的尾部是oldEnd = head.next,我們需要新增的尾部是head節點，那麼使得(head.next).next = head即可完成。減少時間損耗。
- 最後尾部即head，他的後繼節點依舊是oldEnd,成了一個環形，是以必須将head的後繼設定為null.
_206_反轉連結清單_疊代
https://leetcode-cn.com/problems/reverse-linked-list/submissions/
老師這張圖真的是非常形象了，看的很清楚，自己再把思路複述一遍。
疊代的思路也很簡單，應該說是拆拆拆，
-
我們需要三個指針， head, second以及newHead
first指向連結清單頭部，second指向head的後繼節點，newHead作為新連結清單的首部。
- 開始的時候先讓second指向first的後繼節點，然後将head的後繼節點指向newHead, newHead一開始為空，second一開始也為空，然後将newHead指向first節點，将first指向second節點
- 以上的文字說明就是不斷拆原來的連結清單，構造新連結清單的過程，隻要head不是null，就可以不斷的循環，直到構造完成。
- 這裡我開始的時候時second不是空，是以還在循環之外寫了一些代碼，現在看來是不必要的。
代碼如下
/**
* 疊代的思路也很簡單
* 應該說我們也還是需要三個指針，head,second,newHead
* first指針指向連結清單頭部，second指針指向連結清單的第二個節點
* 開始的時候讓first的後繼節點置空，
* newFirst指向first節點，
* 然後讓first指向second節點，second節點指向後繼節點
* first節點的後繼節點指向newFirst,NewFirst指向First
* 從這裡開始就開始重複，直到first節點為空
* @param head
* @return
*/
public ListNode reverseList(ListNode head) {
//疊代性能一般都比遞歸要高，因為一個是O（N）一個是O(N^2)
if(head == null || head.next == null) return head;
ListNode second = null;
ListNode newHead = null;
while(head != null) {
second = head.next;
head.next = newHead;
newHead = head;
head = second;
}
return newHead;
} _141_環形連結清單
https://leetcode-cn.com/problems/linked-list-cycle/submissions/
環形連結清單用快慢指針解決，思路還是很簡單的
我們将第一個指針指向頭部，第二個指針指向頭部後繼節點，第一個指針一次走一個機關，第二個指針一次走兩個機關，如果有環的話，就像是在跑圈，跑得快的和跑的慢的，總會套圈相遇
/**
* 環形連結清單
* 環形連結清單用快慢指針解決，思路還是很簡單的
* 我們将第一個指針指向頭部，第二個指針指向頭部後繼節點
* 第一個指針一次走一個機關，第二個指針一次走兩三個機關，
* 如果有環的化，就像是跑圈，跑得快的和跑的慢的，總會套圈相遇
* @param head
* @return
*/
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode first = head;
ListNode second = head.next;
//隻要兩個指針指向節點的val相同就可以認為是有環
while(second != null && second.next != null) {
// if(second.val == first.val && second.next == first.next) {
// return true;
// }
if(first == second) return true;
first = first.next;
second = second.next.next;
}
return false;
} 快指針走兩步，而不是走三步甚至四步的原因
- 可以想象一下，如果快慢指針間隔5步，那麼下一輪次慢指針走一步，快指針走兩步，雙方距離縮短到4，那麼繼續下一輪雙- 方輪次縮短到3，繼續2，1直到相遇，也就是說快指針走兩步可以保證一定相遇
- 如果快指針走三步，會發生什麼呢？假設距離還是5，那麼下一輪慢指針走一步，快指針走三步，距離縮短到3，再下一輪縮短到1，在下一輪縮短到-1，也就是說發生了套圈！相遇需要的時間就多了。
- 慢指針走兩步，快指針走三步呢？這個效果好像是一樣的，但是循環控制條件就要寫的更多了。