算法基礎課二：數組和連結清單

數組結構

1. 線性表結構，每個元素，最多隻有前和後兩個方向，是連續記憶體空間存儲，要求相同的資料類型；
2. 數組，支援根據下标随機通路，時間複雜度為 O(1)，内部是根據 ( 記憶體首位址 + 下标 * 資料類型所占空間 )，定位到記憶體位址；
3. 插入，修改，删除操作，

插入和删除操作：
		空間複雜度 O(1) 
		最好時間複雜度 O(1) 隊尾插入或删除
		最壞時間複雜度 O(n) 隊頭插入或删除，因為涉及數組元素的整體複制
		平均時間複雜度 O(n)，(1+2+...+n)*(1/n) 即為 O(n) 
	修改操作：
		空間複雜度 O(1) 
		時間複雜度 O(1)，數組下标随機通路，修改值即可
           

1. 如果對數組元素的順序，沒有要求，向第 k 個位置插入元素，可以先将第 k 個位置的元素，移到數組末尾，然後給數組第 k 個位置，賦新值，那麼時間複雜度就是 O( 1 )；
2. 删除操作，如果有多次删除操作，可以考慮，前幾次删除，隻标記元素被删除，并不真正删除，和執行資料搬移，等到累積幾次删除後，才真正完成删除，進行資料搬移，這樣提高操作效率，和 JVM 中的标記清除的垃圾回收類似；
3. 在 java 中，不允許數組越界通路，通路不存在的數組下标，回抛出異常，下面示例，i = 3 時，會抛出異常；

psvm(...){    
		int i = 0;    
		int arr[3] = {0};    
		for(; i<=3; i++){        
			arr[i] = 0;        
			printf("hello world\n");    
		}    
	}
           

1. java 中的 ArrayList，将數組操作的細節封裝起來，如插入，删除資料時，搬移其他資料等，另外，支援動态擴容，每次擴容 1.5 倍；

連結清單結構

1. 連結清單，通過指針，将一組零散的記憶體塊串聯在一起，每個記憶體塊，稱為連結清單的結點，包含存儲資料 data，和下一個節點的指向 next，即下一個節點的位址；
2. 連結清單的插入和删除操作，隻需改變前後節點的指針，時間複雜度是 O ( 1 )，随機通路，需要周遊，時間複雜度是 O ( n )；
3. 雙向連結清單比單連結清單，插入和删除操作效率更高，可以向前或向後查找，空間換取時間；
4. 連結清單算法，需要考慮連結清單為空，連結清單隻有一個節點，隻有兩個節點，對頭，尾節點操作等邊界條件檢查；

數組和連結清單

1. 數組的插入和删除，都涉及資料搬移，效率低，而下标随機通路效率特别高，連結清單與之正好相反，是以連結清單适合頻繁插入和删除的場景，數組适合頻繁随機通路的場景；
2. 并且數組是連續存儲，對 cpu 緩存更友好，連結清單則不然；
3. 數組擴容不友好，連結清單天然支撐擴容；

算法操作

1. 連結清單實作 LRU 緩存淘汰，将最近最少使用的緩存淘汰；

緩存通路，首先連結清單查找：
		如果不存在，将緩存節點，存放在連結清單頭部，如果連結清單滿了，删除尾節點
		如果存在，命中緩存，先将緩存節點從該位置删除，新放入到連結清單頭部，保證連結清單頭部是最近使用的資料
		連結清單尾部，就是最近最少使用的資料，是以，緩存滿了，删除尾節點，就是删除最近最少使用
	時間複雜度是 o(n),查找是必須步驟
	緩存淘汰政策
		先進先出政策 FIFO（First In，First Out）
		最少使用政策 LFU（Least Frequently Used）
		最近最少使用政策 LRU（Least Recently Used）
           

1. 實作回文字元串的檢查

1. 單連結清單反轉

通過兩個節點指針，周遊連結清單，首先 A = null , B = head，然後 temp = B, B = B.next，temp.next = A, A = temp,
	直到 B = null 截止 
           

1. 連結清單中環的檢測

通過快慢指針，快指針一次走兩步，慢指針一次走一步，如果有環，兩個指針必定相遇，
	如果沒有環，兩者不會相遇，且都會執行到null
           

1. 兩個有序的連結清單合并

通過兩個指針，分别指向兩個連結清單頭，比較大小，将較小的節點，放入一個新連結清單中，然後累積該指針，然後繼續比較大小，
		直到一個指針走到連結清單尾，然後複制指針沒走完的連結清單，到新連結清單尾部，新連結清單即為合并的有序連結清單
           

1. 删除連結清單倒數第 n 個結點

倒數第 n 個節點，即距離最後一個節點有 n 個節點，如此使用兩個指針，一個指向連結清單頭，一個指向第 n 個節點，兩個指針	
		每次走一步，直到第二個指針走到連結清單尾，那麼第一個指針就是指向，倒數第 n 個節點
           

1. 求連結清單的中間結點

同樣使用兩個指針，都從連結清單頭開始，一個每次走一步，一個每次走兩步，這樣當走兩步的指針，走到連結清單尾部，
		此時第一個指針就剛好是連結清單中間節點
           

1. 具體代碼實作，檢視 …