鏈表是節點的集合。第一個節點(Node)一般被稱為Head。最后一個節點的Next屬性必須指向 None ，表明是鏈表的結尾。

在大多數編程語言中，鏈表和數組在內存中的存儲方式存在明顯差異。數組要求內存空間是連續的，鏈表可以不連續。

然而，在 Python 中，list是動態數組。所以在Python中列表和鏈表的內存使用非常相似。

鏈表和數組在以下的操作中也有本質區別：

1.插入元素：數組中插入元素時，插入位置之后的所有元素都需要往后移動一位，所以數組中插入元素最壞時間復雜度是 O(n)鏈表可以達到 O(1) 的時間復雜度。

2. 刪除元素：數組需要將刪除位置之后的元素全部往前移動一位，最壞時間復雜度是 O(n)，鏈表可以達到 O(1) 的時間復雜度。

3.隨機訪問元素：數組可以通過下標直接訪問元素，時間復雜度為O(1)。鏈表需要從頭結點開始遍歷，時間復雜度為O(n)。

4.獲取長度： 數組獲取長度的時間復雜度為O(1)，鏈表獲取長度也只能從頭開始遍歷，時間復雜度為O(n)。
實現鏈表

class LinkedList:def __init__(self):self.head = None

在LinkedList中，需要存儲的唯一信息是鏈表的開始位置(鏈表的頭部)。接下來，創建另一個類Node來表示鏈表的每個節點：

class Node:def __init__(self, data):self.data = dataself.next = None

我們可以給剛創建的兩個類添加 __repr__ 方法, 在創建實例的時候輸出更多有用的信息：

class LinkedList:def __init__(self):self.head = None def __repr__(self):node = self.headnodes = []while node is not None:nodes.append(node.data)node = node.nextnodes.append("None")return " -> ".join(nodes)

我們可以給剛創建的兩個類添加 __repr__ 方法, 在創建實例的時候輸出更多有用的信息

class Node:def __init__(self, data):self.data = dataself.next = Nonedef __repr__(self):return self.data

創建測試類, 測試上面的代碼

from LinkedList import LinkedList from Node import Node if __name__ == '__main__':llist = LinkedList()print(llist)first_node = Node('a')llist.head = first_nodeprint(llist)second_node = Node('b')third_node = Node('c')first_node.next = second_nodesecond_node.next = third_nodeprint(llist)

修改__init__ 方法，可以傳入列表快速創建LinkedList

def __init__(self, nodes=None):self.head = Noneif nodes is not None:node = Node(data=nodes.pop(0))self.head = nodefor elem in nodes:node.next = Node(data=elem)node = node.next

創建__iter__ 方法，遍歷鏈表

def __iter__(self):node = self.headwhile node is not None:yield nodenode = node.next from LinkedList import LinkedList if __name__ == '__main__':llist = LinkedList(['a','b','c','d','e'])print(llist) for node in llist:print(node)

實現鏈表，添加節點

在頭部添加Node：在鏈表的開頭添加一個Node，不必遍歷鏈表，只需將新的Node的next屬性指向 self.head ，并將新的node設置為新的 self.head

def add_first(self, node):node.next = self.headself.head = node from LinkedList import LinkedList from Node import Node if __name__ == '__main__':llist = LinkedList()print(llist)llist.add_first(Node('b'))print(llist)llist.add_first(Node('a'))print(llist)

在尾部添加Node：必須遍歷鏈表，與list不同，list可以直接獲取長度， 鏈表只有從第一個Node，不斷的去獲取下一個Node 才能知道鏈表的尾部。

def add_last(self, node):if self.head is None:self.head = nodereturnfor current_node in self:passcurrent_node.next = node from LinkedList import LinkedList from Node import Node if __name__ == '__main__':llist = LinkedList(['a','b','c','d'])print(llist)llist.add_last(Node('e'))print(llist)llist.add_last(Node('f'))print(llist)

在指定元素后添加Node：遍歷鏈表找到目標Node， 把目標Node的下一個元素， 賦值給要添加Node的next屬性, 然后修改目標Node的next屬性, 指向新添加的Node, 當鏈表為空以及目標元素不存在時拋出異常。

def add_after(self, target_node_data, new_node):if self.head is None:raise Exception("List is empty") for node in self:if node.data == target_node_data:new_node.next = node.nextnode.next = new_nodereturnraise Exception("Node with data '%s' not found" % target_node_data)

在指定元素后添加Node：遍歷鏈表找到目標Node， 把目標Node的下一個元素， 賦值給要添加Node的next屬性, 然后修改目標Node的next屬性, 指向新添加的Node, 當鏈表為空以及目標元素不存在時拋出異常。

from LinkedList import LinkedList from Node import Node if __name__ == '__main__':llist = LinkedList()llist.add_after("a", Node("b"))llist = LinkedList(['a','b','c','d'])print(llist)llist.add_after("c", Node("cc"))print(llist)llist.add_after("f", Node("g"))

在指定元素前添加Node：遍歷鏈表找到目標Node，還需要記錄當前節點的前一個節點。

def add_before(self, target_node_data, new_node):if self.head is None:raise Exception("List is empty")if self.head.data == target_node_data:return self.add_first(new_node)prev_node = self.headfor node in self:if node.data == target_node_data:prev_node.next = new_nodenew_node.next = nodereturnprev_node = noderaise Exception("Node with data '%s' not found" % target_node_data) from LinkedList import LinkedList from Node import Node if __name__ == '__main__’:llist = LinkedList()llist.add_before("a", Node("b"))llist = LinkedList(["b", "c"])print(llist)llist.add_before('b',Node('a'))print(llist)llist.add_before("b", Node("aa"))llist.add_before("c", Node("bb"))print(llist)llist.add_before("n", Node("m"))

刪除Node：遍歷鏈表找到目標Node，將目標Node的前一個Node的next屬性,指向目標Node的next節點。

def remove_node(self, target_node_data):if self.head is None:raise Exception("List is empty")if self.head.data == target_node_data:self.head = self.head.nextreturnprevious_node = self.headfor node in self:if node.data == target_node_data:previous_node.next = node.nextreturnprevious_node = node raise Exception("Node with data '%s' not found" % target_node_data) from LinkedList import LinkedList from Node import Node if __name__ == '__main__’:llist = LinkedList(["a", "b", "c", "d", "e"])print(llist)llist.remove_node("a")print(llist)llist.remove_node('e')print(llist)

總結

以上是生活随笔為你收集整理的Python中的链表和数组如何区分？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。