一、鏈表
????????鏈表是一種線性數據結構，由一系列按特定順序排列的節點組成，這些節點通過指針相互連接。每個節點包含兩部分：元素和指向下一個節點的指針。其中，最簡單的形式是單向鏈表，每個節點含有一個信息域和一個指針域，該指針指向鏈表中的下一個節點，最后一個節點則指向一個空值。
1.1、Python中的鏈表
?????????大部分都是用C語言實現鏈表，因為C有指針，可以很方便的控制內存，很輕易就可以實現鏈 表，在C/C++中，通常采用“指針+結構體”來實現鏈表。
?????????Python是一門動態語言，可以直接把對象賦值給新的變量，我們采用“引用+類”來實現 鏈表。
?????????結構：data為自定義的數據，next為下一個節點的地址。
?????????鏈表的種類：單向鏈表、雙向鏈表、單向循環鏈表、雙向循環鏈表。?
1.2、基本元素
節點：每個節點有兩個部分，左邊稱為值域，存放用戶數據；右邊部分稱為指針域，用來存 放指向下一個元素的指針。
Head：head節點永遠指向第一個節點。
Tail：tail節點永遠指向最后一個節點。
None：鏈表中最后一個節點的指針域為None。
二、基本操作
2.1、節點的創建
class Node:def __init__(self, data):# 初始化節點，包含數據和指向下一個節點的指針self.data = dataself.next = None 
2.2、初始化單向鏈表
class LinkList:def __init__(self, node=None):# 初始化鏈表，頭指針指向第一個節點（默認為None）self.__head = node2.3、判斷是否為空
def is_empty(self):# 檢查鏈表是否為空return self.__head == None2.4、鏈表長度
def length(self):# 計算鏈表的長度current = self.__headcount = 0while current != None:count += 1current = current.nextreturn count2.5、遍歷鏈表?
def travel(self):# 遍歷鏈表并打印每個節點的數據current = self.__headwhile current != None:print(current.data)current = current.next2.4、插入節點
2.4.1、頭節點
def add(self, data):# 在鏈表頭部添加新節點new_node = Node(data)new_node.next = self.__headself.__head = new_node
2.4.2、中間節點
def insert(self, pos, data):# 在指定位置插入新節點if pos > self.length() - 1:self.append(data) # 如果位置超出范圍，添加到尾部elif pos <= 0:self.add(data) # 如果位置小于等于0，添加到頭部else:new_node = Node(data)pre = self.__headcount = 0while count < pos - 1:count += 1pre = pre.nextnew_node.next = pre.next # 將新節點的next指向當前節點的nextpre.next = new_node # 將前一個節點的next指向新節點
2.4.3、尾節點
def append(self, data):# 在鏈表尾部添加新節點new_node = Node(data)if self.is_empty():self.__head = new_nodeelse:current = self.__headwhile current.next != None:current = current.nextcurrent.next = new_node
?
2.5、刪除節點
def remove(self, data):# 移除鏈表中指定數據的節點current = self.__headpre = Nonewhile current != None:if current.data == data:if current == self.__head:self.__head = current.next # 如果是頭節點，更新頭指針else:pre.next = current.next # 將前一個節點的next指向當前節點的nextbreakelse:pre = currentcurrent = current.next
2.6、查找節點
def serch(self, data):# 查找鏈表中是否存在指定數據current = self.__headwhile current != None:if current.data == data:return True # 找到數據，返回Trueelse:current = current.nextreturn False # 遍歷完成未找到數據，返回False三、鏈表的特點
1、動態數據集合：鏈表允許動態的添加和刪除元素，這使得它們在處理未知數量或頻繁變 化的數據集時非常有用。
2、元素順序：鏈表可以按照插入順序來保持元素的順序，這對于需要維護元素插入順序的 應用程序非常有用。
3、 內存效率：與數組相比，鏈表在內存使用上更為高效，因為它們不需要連續的內存空間。 鏈表通過節點之間的指針來連接元素，這樣可以更有效地利用內存空間。
4、避免數組擴容：數組在初始化時需要指定大小，如果超出大小，則需要擴容，這是一個 昂貴的操作。鏈表則可以避免這個問題，因為它們可以動態地增長。
四、單向鏈表的缺點
1、只能從頭遍歷到尾或者從尾遍歷到頭(一般從頭到尾)。
2、鏈表相連的過程是單向的。實現的原理是上一個鏈表中有一個指向下一個的引用。
3、?我們可以輕松的到達下一個節點, 但是回到前一個節點是很難的。但是, 在實際開發中, 經 常會遇到需要回到上一個節點的情況。
舉個例子:
????????假設一個文本編輯用鏈表來存儲文本。每一行用一個String對象存儲在鏈表的 一個節點中。當編輯器用戶向下移動光標時, 鏈表直接操作到下一個節點即可。但是當用 于將光標向上移動呢? 這個時候為了回到上一個節點, 我們可能需要從頭開始, 依次走到 想要的節點上。
五、完整代碼?
class Node:def __init__(self, data):# 初始化節點，包含數據和指向下一個節點的指針self.data = dataself.next = Noneclass LinkList:def __init__(self, node=None):# 初始化鏈表，頭指針指向第一個節點（默認為None）self.__head = nodedef is_empty(self):# 檢查鏈表是否為空return self.__head == Nonedef length(self):# 計算鏈表的長度current = self.__headcount = 0while current != None:count += 1current = current.nextreturn countdef travel(self):# 遍歷鏈表并打印每個節點的數據current = self.__headwhile current != None:print(current.data)current = current.nextdef add(self, data):# 在鏈表頭部添加新節點new_node = Node(data)new_node.next = self.__headself.__head = new_nodedef append(self, data):# 在鏈表尾部添加新節點new_node = Node(data)if self.is_empty():self.__head = new_nodeelse:current = self.__headwhile current.next != None:current = current.nextcurrent.next = new_nodedef insert(self, pos, data):# 在指定位置插入新節點if pos > self.length() - 1:self.append(data) # 如果位置超出范圍，添加到尾部elif pos <= 0:self.add(data) # 如果位置小于等于0，添加到頭部else:new_node = Node(data)pre = self.__headcount = 0while count < pos - 1:count += 1pre = pre.nextnew_node.next = pre.next # 將新節點的next指向當前節點的nextpre.next = new_node # 將前一個節點的next指向新節點def remove(self, data):# 移除鏈表中指定數據的節點current = self.__headpre = Nonewhile current != None:if current.data == data:if current == self.__head:self.__head = current.next # 如果是頭節點，更新頭指針else:pre.next = current.next # 將前一個節點的next指向當前節點的nextbreakelse:pre = currentcurrent = current.nextdef serch(self, data):# 查找鏈表中是否存在指定數據current = self.__headwhile current != None:if current.data == data:return True # 找到數據，返回Trueelse:current = current.nextreturn False # 遍歷完成未找到數據，返回Falseif __name__ == '__main__':linklist = LinkList()linklist.add(10) # 添加節點10linklist.add(20) # 添加節點20linklist.append(100) # 在尾部添加節點100linklist.add(30) # 添加節點30linklist.add(40) # 添加節點40print(linklist.is_empty()) # 檢查鏈表是否為空print(linklist.length()) # 輸出鏈表長度print('*****************')linklist.remove(30) # 移除節點30# linklist.travel() # 遍歷鏈表并打印節點數據print(linklist.serch(40)) # 查找節點40是否存在# linklist.travel() # 遍歷鏈表并打印節點數據六、思維導圖?
)
