***** ## 單向鏈表 單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式，它的每個節點包含兩個域，一個信息域（元素域）和一個鏈接域。這個鏈接指向鏈表中的下一個節點，而最后一個節點的鏈接域則指向一個空值。  - 表元素域elem用來存放具體的數據。 - 鏈接域next用來存放下一個節點的位置（python中的標識） - 變量p指向鏈表的頭節點（首節點）的位置，從p出發能找到表中的任意節點。 ### 節點實現 ``` class SingleNode(object): """單鏈表的結點""" def __init__(self,item): # _item存放數據元素 self.item = item # _next是下一個節點的標識 self.next = None ``` ### 單鏈表的操作 - is_empty() 鏈表是否為空 - length() 鏈表長度 - travel() 遍歷整個鏈表 - append(item) 鏈表尾部添加元素 - add(item) 鏈表頭部添加元素 - insert(pos, item) 指定位置添加元素 - search(item) 查找節點是否存在 - remove(item) 刪除節點 ### 單鏈表的實現 ``` class SingleLinkList(object): """單鏈表""" def __init__(self, node=None): self.__head = node def is_empty(self): """判斷鏈表是否為空""" return self.__head == None def length(self): """鏈表長度""" # cur初始時指向頭節點 cur = self.__head count = 0 # 尾節點指向None，當未到達尾部時 while cur != None: count += 1 # 將cur后移一個節點 cur = cur.next return count def travel(self): """遍歷鏈表""" cur = self.__head while cur != None: print(cur.item) cur = cur.next print() ``` ### 頭部添加元素  ``` def add(self, item): """頭部添加元素""" # 先創建一個保存item值的節點 node = SingleNode(item) # 將新節點的鏈接域next指向頭節點，即_head指向的位置 node.next = self.__head # 將鏈表的頭_head指向新節點 self._head = node ``` ### 尾部添加元素 ``` def append(self, item): """尾部添加元素""" node = SingleNode(item) # 先判斷鏈表是否為空，若是空鏈表，則將_head指向新節點 if self.is_empty(): self.__head = node # 若不為空，則找到尾部，將尾節點的next指向新節點 else: cur = self._head while cur.next != None: cur = cur.next cur.next = node ``` ### 指定位置添加元素  ``` def insert(self, pos, item): """指定位置添加元素""" # 若指定位置pos為第一個元素之前，則執行頭部插入 if pos <= 0: self.add(item) # 若指定位置超過鏈表尾部，則執行尾部插入 elif pos > (self.length()-1): self.append(item) # 找到指定位置 else: node = SingleNode(item) count = 0 # pre用來指向指定位置pos的前一個位置pos-1，初始從頭節點開始移動到指定位置 pre = self._head while count < (pos-1): count += 1 pre = pre.next # 先將新節點node的next指向插入位置的節點 node.next = pre.next # 將插入位置的前一個節點的next指向新節點 pre.next = node ``` ### 刪除節點  ``` def remove(self,item): """刪除節點""" cur = self._head pre = None while cur != None: # 找到了指定元素 if cur.item == item: # 如果第一個就是刪除的節點 if not pre: # 將頭指針指向頭節點的后一個節點 self._head = cur.next else: # 將刪除位置前一個節點的next指向刪除位置的后一個節點 pre.next = cur.next break else: # 繼續按鏈表后移節點 pre = cur cur = cur.next ``` ### 查找節點是否存在 ``` def search(self,item): """鏈表查找節點是否存在，并返回True或者False""" cur = self.__head while cur != None: if cur.item == item: return True cur = cur.next return False ``` ### 鏈表與順序表的對比 鏈表失去了順序表隨機讀取的優點，同時鏈表由于增加了結點的指針域，空間開銷比較大，但對存儲空間的使用要相對靈活。 <table> <thead> <tr> <th>操作</th> <th style="text-align:center">鏈表</th> <th>順序表</th> </tr> </thead> <tbody> <tr> <td>訪問元素</td> <td style="text-align:center">O(n)</td> <td>O(1)</td> </tr> <tr> <td>在頭部插入/刪除</td> <td style="text-align:center">O(1)</td> <td>O(n)</td> </tr> <tr> <td>在尾部插入/刪除</td> <td style="text-align:center">O(n)</td> <td>O(1)</td> </tr> <tr> <td>在中間插入/刪除</td> <td style="text-align:center">O(n)</td> <td>O(n)</td> </tr> </tbody> </table> 注意雖然表面看起來復雜度都是 O(n)，但是鏈表和順序表在插入和刪除時進行的是完全不同的操作。鏈表的主要耗時操作是遍歷查找，刪除和插入操作本身的復雜度是O(1)。順序表查找很快，主要耗時的操作是拷貝覆蓋。因為除了目標元素在尾部的特殊情況，順序表進行插入和刪除時需要對操作點之后的所有元素進行前后移位操作，只能通過拷貝和覆蓋的方法進行。 ### 寫鏈表代碼建議 * 理解指針或引用的含義 * 警惕指針丟失 * 重點留意邊界條件處理 * 舉例畫圖，輔助思考 ## 如何實現LRU緩存淘汰算法? 緩存是一種提高數據讀取性能的技術，在硬件設計、軟件開發中都有著非常廣泛的應用，比如常見的 CPU 緩存、數據庫緩存、瀏覽器緩存等等。 <br>緩存的大小有限，當緩存被用滿時，哪些數據應該被清理出去，哪些數據應該被保留？這就需要緩存淘汰策略來決定。常見的策略有三種：先進先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。 <br>這些策略你不用死記，我打個比方你很容易就明白了。假如說，你買了很多本技術書，但有一天你發現，這些書太多了，太占書房空間了，你要做個大掃除，扔掉一些書籍。那這個時候，你會選擇扔掉哪些書呢？對應一下，你的選擇標準是不是和上面的三種策略神似呢？ <br>我的思路是這樣的：我們維護一個有序單鏈表，越靠近鏈表尾部的結點是越早之前訪問的。當有一個新的數據被訪問時，我們從鏈表頭開始順序遍歷鏈表。 1. 如果此數據之前已經被緩存在鏈表中了，我們遍歷得到這個數據對應的結點，并將其從原來的位置刪除，然后再插入到鏈表的頭部。 2. 如果此數據沒有在緩存鏈表中，又可以分為兩種情況： * 如果此時緩存未滿，則將此結點直接插入到鏈表的頭部； * 如果此時緩存已滿，則鏈表尾結點刪除，將新的數據結點插入鏈表的頭部。