重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 開篇
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 復(fù)雜度分析(一)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 復(fù)雜度分析(二)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 數(shù)組
前章提到鏈表也屬于線性表結(jié)構(gòu)。
可想而知，鏈表在內(nèi)存中存儲(chǔ)的形式也是類似于一條直線進(jìn)行延伸的。
從內(nèi)存圖中可看出，鏈表數(shù)據(jù)結(jié)構(gòu)的內(nèi)存分配情況并不連續(xù)，作為線性表結(jié)構(gòu)的關(guān)鍵就在于每個(gè)數(shù)據(jù)結(jié)點(diǎn)都是由 數(shù)據(jù)塊 和 指針塊 組成。
- 數(shù)據(jù)塊 ： 用于存儲(chǔ)真正的數(shù)據(jù)
- 指針塊 ： 用于存儲(chǔ)下一個(gè)結(jié)點(diǎn)的內(nèi)存首地址
例如上圖Node1結(jié)點(diǎn)中的指針塊存儲(chǔ)的就是Node2的首地址1003（這里假設(shè)一個(gè)結(jié)點(diǎn)僅占用1個(gè)字節(jié)）
單向鏈表
單鏈表的方向是固定的，指針始終指向下一個(gè)結(jié)點(diǎn)，當(dāng)沒有結(jié)點(diǎn)時(shí)，最后一個(gè)結(jié)點(diǎn)稱之尾結(jié)點(diǎn)，它的指針塊會(huì)存儲(chǔ)null；而第一個(gè)結(jié)點(diǎn)稱之首結(jié)點(diǎn)，只要知道首結(jié)點(diǎn)，就可以獲取到該鏈表中任意結(jié)點(diǎn)數(shù)據(jù)。
鏈表的插入與刪除
與數(shù)組一樣，鏈表也支持插入、刪除、查詢操作。我們知道數(shù)組的插入、刪除操作需要大量的數(shù)據(jù)遷移工作，時(shí)間復(fù)雜度為：O(n)。而在鏈表中插入和刪除結(jié)點(diǎn)就非常簡(jiǎn)單。
插入操作
如果需要在Node1和Node2中間插入Node8結(jié)點(diǎn)，只需要兩步：
- ①修改Node1的指針塊存儲(chǔ)Node8的首地址；
- ②再讓Node8的指針塊存儲(chǔ)原Node1指針塊中取出的地址。
通過上面操作，在沒有進(jìn)行位移數(shù)據(jù)的情況下， 插入操作的時(shí)間復(fù)雜度為：O(1)。
刪除操作
同理，刪除Node2結(jié)點(diǎn)也只需兩步：
- ①修改Node1的指針塊存儲(chǔ)Node3的首地址；
- ②清空Node2的指針塊。
So. 刪除操作的時(shí)間復(fù)雜度也是：O(1)。
查詢操作
有利就有弊，與數(shù)組恰恰相反，鏈表因?yàn)椴皇沁B續(xù)的內(nèi)存塊，就無法通過尋址公式計(jì)算出每個(gè)結(jié)點(diǎn)的首地址，所以查詢一個(gè)結(jié)點(diǎn)就必須從鏈表的首結(jié)點(diǎn)挨個(gè)查詢下去，直到找到為止，即時(shí)間復(fù)雜度為：O(n)。
循環(huán)鏈表
循環(huán)列表是一種特殊單向鏈表，它的尾結(jié)點(diǎn)指針塊不再存儲(chǔ)null，而是指向首結(jié)點(diǎn)的首地址。
這種鏈表的優(yōu)點(diǎn)在處理環(huán)型數(shù)據(jù)時(shí)更加合適，比如著名的：約瑟夫問題。
約瑟夫環(huán)
N個(gè)人圍成一圈，從第一個(gè)開始報(bào)數(shù)，第M個(gè)將被殺掉，最后剩下一個(gè)人時(shí)游戲結(jié)束，求人員被殺掉的順序。
例如：N=6，M=5，被殺掉的順序是：5 -> 4 -> 6 -> 2 -> 3 , 最終幸運(yùn)者： 1。
首先，創(chuàng)建一個(gè)Node類，該類的數(shù)據(jù)塊存儲(chǔ)人員編號(hào)，next指向下一個(gè)人員結(jié)點(diǎn)；
class Node {
public int data; // 人員編號(hào)
public Node next; // 下一個(gè)人結(jié)點(diǎn)
public Node(int data) {
this.data = data;
}
}
再創(chuàng)建人員，并組成環(huán)；
// 1、創(chuàng)建結(jié)點(diǎn)，并組成環(huán)
Node firstNode = new Node(1);
Node preNode = firstNode;
for (int i = 1; i < n; i++) {
Node temp = new Node(i + 1);
preNode.next = temp;
preNode = temp;
}
preNode.next = firstNode;
最后開始報(bào)數(shù)，只要報(bào)到m-1的人，它的下一位就出局，代碼如下：
// 2、開始報(bào)數(shù)
Node node = firstNode;
while (node != node.next) {
for (int i = 1; i < m-1; i++) {
node = node.next;
}
//當(dāng)報(bào)數(shù)到m-1時(shí)，下一個(gè)人員就是出局者
Node outNode = node.next;
System.out.println("出局：" + outNode.data);
//報(bào)數(shù)m-1的人指向 m+1人員
node.next = outNode.next;
outNode.next = null;
//準(zhǔn)備下一輪
node = node.next;
}
System.out.println("幸運(yùn)者：" + node.data);
輸出：
出局：5
出局：4
出局：6
出局：2
出局：3
幸運(yùn)者：1
時(shí)間復(fù)雜度：O(m * n)
雙向鏈表
和單向鏈表不同，雙向鏈表有兩個(gè)指針塊，一個(gè)和單向鏈表一樣指向下一個(gè)結(jié)點(diǎn)的next指針，一個(gè)是指向上一個(gè)結(jié)點(diǎn)的pre指針。
了解單向鏈表的數(shù)據(jù)結(jié)構(gòu)后，雙向鏈表就不難理解，與單項(xiàng)鏈表相比，雙向鏈表的優(yōu)缺點(diǎn)如下：
缺點(diǎn)
首先，由于每個(gè)結(jié)點(diǎn)比單向鏈表都多一個(gè)指針塊，內(nèi)存占用肯定大于單向鏈表。
優(yōu)點(diǎn)
前驅(qū)指針的存在，當(dāng)需要獲取前結(jié)點(diǎn)需求時(shí)，時(shí)間復(fù)雜度就僅僅為O(1)，而單向鏈表就不得不重新從首結(jié)點(diǎn)遍歷，時(shí)間復(fù)雜度為O(n)，這種設(shè)計(jì)我們稱之為：用空間換時(shí)間。
關(guān)于實(shí)際情況中的雙鏈表操作的優(yōu)點(diǎn)
- 之前提到單向鏈表的刪除操作時(shí)間復(fù)雜度是O(1)，但實(shí)際開發(fā)中的刪除需求可能會(huì)是刪除某個(gè)結(jié)點(diǎn)（Node對(duì)象）。這時(shí)，單鏈表就無法將上結(jié)點(diǎn)和下結(jié)點(diǎn)直接連接起來（沒有前驅(qū)指針），就必須重頭遍歷鏈表找到上結(jié)點(diǎn)，單向鏈表刪除操作時(shí)間復(fù)雜度就變?yōu)椋?strong>O(n)；而雙向鏈表就不存在這個(gè)問題，依舊可以保持高效的時(shí)間復(fù)雜度：O(1)。
同理，當(dāng)要插入結(jié)點(diǎn)在某個(gè)結(jié)點(diǎn)前時(shí)，單向鏈表依舊無法獲取上結(jié)點(diǎn)進(jìn)行連接，所以插入操作時(shí)間復(fù)雜度變?yōu)椋?strong>O(n)；而雙向鏈表依舊為：O(1)。
如果鏈表數(shù)據(jù)是有序的，在查詢上雖然兩者時(shí)間復(fù)雜度都是O(n)，但實(shí)際上雙向鏈表可以支持更快查詢。雙向鏈表可以把每次查詢到的結(jié)點(diǎn)記錄下來，當(dāng)下次查詢值大于當(dāng)前就可以繼續(xù)向后查詢，反之向前查詢，從而節(jié)省大部分時(shí)間。
LinkedList底層就是通過雙向鏈表實(shí)現(xiàn)。
雙向循環(huán)鏈表
跟循環(huán)鏈表一樣，把雙向鏈表的首尾相連起來，將雙向和循環(huán)的優(yōu)缺點(diǎn)結(jié)合起來就是：雙向循環(huán)鏈表
鏈表 VS 數(shù)組
時(shí)間復(fù)雜度對(duì)比
- 數(shù)組 插入 O(n)
- 鏈表 插入 O(1)
- 數(shù)組 刪除 O(n)
- 鏈表 刪除 O(1)
- 數(shù)組 查詢 O(1)
- 鏈表 查詢 O(n)
鏈表和數(shù)組的對(duì)比不能局限于時(shí)間復(fù)雜度，在特定的場(chǎng)景下選擇適合的數(shù)據(jù)結(jié)構(gòu)，才能編寫出高效的算法。
數(shù)組的缺點(diǎn)是內(nèi)存大小連續(xù)且固定，比如在內(nèi)存僅剩100K，但并不連續(xù)，那么在創(chuàng)建一個(gè)100K的數(shù)組時(shí)就會(huì)導(dǎo)致“內(nèi)存不足（out of memory）”，而鏈表就可以正常創(chuàng)建。
反過來說，正因?yàn)閿?shù)組是連續(xù)的內(nèi)存區(qū)域，有利于CPU的緩存機(jī)制，可以提前預(yù)讀到CPU中，提高訪問效率；而鏈表中的數(shù)據(jù)由于都是單內(nèi)存區(qū)，就無法提前預(yù)讀。并且如果過多的對(duì)鏈表結(jié)點(diǎn)進(jìn)行插入、刪除操作，可能會(huì)導(dǎo)致JVM頻繁的GC，產(chǎn)生更多的內(nèi)存碎片。
LRU淘汰算法
LRU淘汰算法屬于緩存策略一種，一般緩存策略分為三種：
- 1、先進(jìn)先出策略 FIFO
- 2、最少使用策略 LFU
- 3、最近最少使用策略 LRU
了解過鏈表后，可以很容易的使用雙向鏈表實(shí)現(xiàn)一個(gè)最近最少使用策略的LRU緩存機(jī)制，步奏如下：
- 我們將需緩存的數(shù)據(jù)倒序存入鏈表中（先進(jìn)的在末尾）
- 當(dāng)有新數(shù)據(jù)到來時(shí)，遍歷緩存數(shù)據(jù)：
- 已在緩存中： 就將該結(jié)點(diǎn)在原先位置刪除，再插入到首結(jié)點(diǎn)
- 不在緩存中：
- 緩存大小充足，就將該數(shù)據(jù)插入首結(jié)點(diǎn)
- 緩存大小不充足，刪除尾結(jié)點(diǎn)，再插入首結(jié)點(diǎn)
這樣設(shè)計(jì)的緩存策略，由于每次存儲(chǔ)數(shù)據(jù)都要檢查結(jié)點(diǎn)是否存在，所以時(shí)間復(fù)雜度為O(n)。
以下為緩存Data類型數(shù)據(jù)的LRU淘汰算法實(shí)現(xiàn)：
// Data 數(shù)據(jù)類
class Data {
public String id;
public int data;
public Data(String id, int data) {
this.id = id;
this.data = data;
}
public void print() {
System.out.print("{id : '" + id + "' , data : " + data + "}");
}
}
雙向鏈表：
// 結(jié)點(diǎn)類
class Node {
public Node pre;
public Data data;
public Node next;
public Node(Data data) {
this.data = data;
}
}
LruCache實(shí)現(xiàn)類：
// Lru緩存策略容器
class LruCache {
private Node first;
private int size;
private int maxSize;
public LruCache(int maxSize) {
this.maxSize = maxSize;
}
public void add(Data data) {
//校驗(yàn)數(shù)據(jù)是否合法
if (data.id == null) return;
//查詢結(jié)點(diǎn)是否已經(jīng)緩存
Node tempNode = first;
Node last = null;
while (tempNode != null) {
if (tempNode.data.id.equals(data.id)) {
if (tempNode.pre != null) {
tempNode.pre.next = tempNode.next;
}
//已緩存，移動(dòng)到頭部位置
tempNode.next = first;
first.pre = tempNode;
first = tempNode;
first.pre = null;
return;
} else {
//未緩存，記錄尾結(jié)點(diǎn)
if (tempNode.next != null) {
tempNode = tempNode.next;
} else {
last = tempNode;
break;
}
}
}
//超過初始化大小，刪除尾結(jié)點(diǎn)
if (size + 1 > maxSize && last != null) {
last.pre.next = null;
size--;
}
//添加新結(jié)點(diǎn)到頭部
Node newNode = new Node(data);
newNode.pre = null;
newNode.next = first;
if (first != null) {
first.pre = newNode;
}
first = newNode;
size++;
}
public Data get(String id) {
Node tempNode = first;
while (tempNode != null) {
if (tempNode.data.id.equals(id)) {
return tempNode.data;
}
tempNode = tempNode.next;
}
return null;
}
public void print() {
Node tempNode = first;
while (tempNode != null) {
System.out.print(tempNode.data.data + "\t");
tempNode = tempNode.next;
}
System.out.println();
}
}
測(cè)試：創(chuàng)建一個(gè)大小為3的緩存空間，并存入一組數(shù)據(jù)，查看存儲(chǔ)情況
LruCache cache = new LruCache(3);
Data data1 = new Data("1", 111);
Data data2 = new Data("2", 222);
Data data3 = new Data("3", 333);
Data data4 = new Data("4", 444);
cache.add(data1);
cache.add(data2);
cache.add(data3);
// 數(shù)據(jù)空間已滿，添加data4會(huì)移除data1
cache.add(data4);
// 重復(fù)添加data2，data2將移至首結(jié)點(diǎn)
cache.add(data2);
cache.print();
Data data = cache.get("3");
data.print();
輸出：
222 444 333
{id : '3' , data : 333}