Python 中的連結列表
- 什麼是 Python 中的連結串列
- 在 Python 中如何建立連結串列
- 在 Python 中列印連結串列的所有元素
- 在 Python 中將元素插入到連結串列中
- 從 Python 中的連結串列中刪除一個元素
- 在 Python 中計算連結串列中的元素數
- 在 Python 中更新連結串列中的節點
- 在 Python 中為什麼使用連結串列
- Python 中的完整實現連結串列
- まとめ
Python 為我們提供了各種內建的資料結構。
但是,每種資料結構都有其侷限性。因此,我們需要自定義資料結構。
本文將討論一種稱為連結串列的自定義資料結構。我們還將在 Python 中實現一個連結串列,並對連結串列進行各種操作。
什麼是 Python 中的連結串列
顧名思義,連結串列是一種資料結構,其中包含使用連結連線的元素。
連結串列是使用稱為節點的物件建立的。每個節點包含兩個屬性——一個用於儲存資料,另一個用於連線到連結串列中的下一個節點。
你可以使用下圖瞭解節點的結構。
這裡,
Node
是包含屬性data
和next
的物件。- 屬性
data
儲存資料。 - 屬性
next
指連結串列中的下一個節點。
如下圖所示,我們可以連線各個節點來建立一個連結串列。
這裡,
- 我們建立了一個由四個節點組成的連結串列。
- 第一個節點包含數字 10,第二個節點包含 20,第三個節點包含 30,最後一個節點包含 40。
- 我們還建立了一個引用第一個節點的變數
Head
。我們只將Head
變數儲存在連結串列物件中。所有其他節點中的資料都是通過從Head
引用的第一個節點開始遍歷連結串列獲得的。 - 最後一個節點的
next
屬性指的是None
物件。連結串列最後一個節點的next
屬性將始終引用None
物件。 - 如果連結串列為空,則
Head
變數將引用None
物件。
我們現在瞭解了連結串列的基本結構。讓我們在 Python 中實現一個連結串列。
在 Python 中如何建立連結串列
由於節點是連結串列的構建塊,我們將首先建立一個節點。為此,我們將定義一個具有屬性 data
和 next
的 Node
類,如下所示。
class Node:
def __init__(self, data):
self.data = data
self.next = None
myNode = Node(10)
print("The data in the node is:", myNode.data)
print("The next attribute in the node is:", myNode.next)
輸出:
The data in the node is: 10
The next attribute in the node is: None
在上面的例子中,你可以觀察到 Node
的 next
屬性預設是指 None
。當我們將它插入到連結串列中時,我們將 next
屬性分配給連結串列中的節點,我們將在前面討論。
我們必須建立一個具有 Head
屬性的物件來建立一個連結串列。我們可以定義 LinkedList
類,如下所示。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4
print("The elements in the linked list are:")
print(myLinkedList.Head.data, end=" ")
print(myLinkedList.Head.next.data, end=" ")
print(myLinkedList.Head.next.next.data, end=" ")
print(myLinkedList.Head.next.next.next.data)
輸出:
The linked list is:
10 20 30 40
在上面的例子中,我們建立了一個連結串列。
之後,我們使用給定的資料手動建立節點,將它們一一新增到連結串列中,並列印出來。稍後,我們將學習使用 Python 的 while
迴圈將元素插入到連結串列中。
現在讓我們討論如何在不手動訪問所有節點的情況下列印連結串列的所有元素。
在 Python 中列印連結串列的所有元素
我們將使用 while
迴圈來列印所有連結串列元素。
從 Head
指標開始,我們將首先使用節點的 data
屬性列印當前節點中的資料。之後,我們將使用 next
指標移動到下一個節點。
我們將遵循這個過程,直到到達連結串列的末尾(即,節點的 next
屬性被發現為 None
)。如下所示,你可以在 printList()
方法中實現整個邏輯。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
10 20 30 40
在 Python 中將元素插入到連結串列中
在連結串列中插入元素有四種情況。
- 連結串列在插入前可以為空。
- 我們必須在非空連結串列的開頭插入一個元素。
- 我們必須在連結串列的末尾插入一個元素。
- 我們必須在連結串列的給定位置插入一個元素。
讓我們討論如何在所有情況下將元素插入到連結串列中。
將元素插入空連結串列
要將元素插入空連結串列,我們將定義一個方法 insertIntoEmptyList()
,該方法接受元素作為輸入引數,並將包含輸入元素的節點新增到連結串列中。
為此,我們將在 insertIntoEmptyList()
中建立一個節點,輸入元素為 data
。建立節點後,我們將節點分配給 Head
屬性。
這樣,新節點將成為連結串列的第一個節點。該方法可以如下實現。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertIntoEmptyList(self, element):
newNode = Node(element)
self.Head = newNode
myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
10
在連結串列的開頭插入元素
為了在非空列表的開頭插入一個元素,我們將定義一個方法 insertAtBeginning()
,它將一個元素作為輸入並將其新增到連結串列的開頭。在 insertAtBeginning()
方法中,我們將首先建立一個以輸入元素作為資料的節點。
之後,我們將新建立的節點的 next
屬性指向連結串列的 Head
屬性指向的節點。接下來,我們將新建立的節點分配給 Head
屬性。
這樣,新節點將被插入到連結串列的開頭。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertIntoEmptyList(self, element):
newNode = Node(element)
self.Head = newNode
def insertAtBeginning(self, element):
newNode = Node(element)
newNode.next = self.Head
self.Head = newNode
myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
30 20 10
如下所示,我們可以結合上述方法建立一個方法,在連結串列的開頭插入一個元素。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertAtBeginning(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
newNode = Node(element)
newNode.next = self.Head
self.Head = newNode
myLinkedList = LinkedList()
myLinkedList.insertAtBeginning(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
30 20 10
我們將 insertIntoEmptyList()
方法合併到 insertAtBeginning()
方法中,因為插入空連結串列本質上意味著我們在連結串列的開頭插入一個元素。
在連結串列末尾插入元素
在空列表的末尾插入元素類似於在連結串列的開頭插入元素。
要在連結串列的末尾插入一個元素,我們將首先檢查連結串列是否為空。如果發現連結串列為空,我們可以簡單地將包含新元素的節點分配給 Head
屬性,就像我們在 insertAtBeginning()
方法中所做的那樣。
否則,我們將使用 while
迴圈遍歷連結串列直到結束。我們將從 Head
開始並使用節點的 next
屬性繼續移動到下一個節點,直到我們發現節點的 next
屬性指向 None
。
一旦我們到達一個其 next
屬性指向 None
的節點,我們就在最後一個節點。現在,我們將使用輸入資料建立一個新節點,並將該節點分配給連結串列最後一個節點的下一個屬性。
這樣,新元素將被插入到連結串列的末尾。你可以在方法 insertAtEnd()
中實現整個邏輯,如下所示。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertAtEnd(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
current = self.Head
while current.next is not None:
current = current.next
newNode = Node(element)
current.next = newNode
myLinkedList = LinkedList()
myLinkedList.insertAtEnd(10)
myLinkedList.insertAtEnd(20)
myLinkedList.insertAtEnd(30)
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
10 20 30
在連結串列的給定位置插入元素
我們將使用一個計數器變數和一個 while
迴圈在連結串列中的給定位置插入一個元素。
我們將從 Head 指標開始,並使用 while
迴圈繼續移動到下一個節點。在每次迭代中,我們還將遞增計數器變數。
一旦我們到達給定位置之前的節點,我們就會退出 while
迴圈。此外,如果我們到達連結串列的末尾,我們將退出迴圈。否則,程式會出錯。
之後,如果我們還在 Head
,我們必須將元素新增到連結串列的第一個位置;我們將給定位置的節點分配給包含新節點元素的 next
指標。接下來,我們將新元素的節點分配給連結串列的 Head
。
如果我們不必在第一個位置插入元素,我們會將給定位置的節點分配給包含新元素的節點的 next
指標。接下來,我們將新節點分配給位於 position-1
的節點的 next
屬性。
這樣,新元素將插入給定位置。如下所示,你可以在 insertAtPosition()
方法中實現整個邏輯。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(20, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(30, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
10
The elements in the linked list are:
10 20
The elements in the linked list are:
10 20 30
The elements in the linked list are:
10 40 20 30
從 Python 中的連結串列中刪除一個元素
當我們試圖從連結串列中刪除一個元素時,可能有三種情況。
- 我們要刪除連結串列的第一個元素。
- 我們要刪除連結串列的最後一個元素。
- 我們必須刪除連結串列中任意位置的元素。
讓我們一一討論所有這些情況。
刪除連結串列的第一個元素
要刪除連結串列的第一個元素,我們將首先檢查連結串列是否為空。
為此,我們將檢查連結串列的 Head
是否指向 None
。如果是,我們將通知使用者連結串列為空,我們沒有要刪除的元素。
否則,我們會將第一個節點分配給一個臨時變數。之後,我們將連結串列的第二個節點分配給 Head
屬性。
然後,我們將使用 del
語句刪除儲存在臨時變數中的第一個節點。如下所示,你可以在 deleteFromBeginning()
方法中實現整個邏輯。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteFromBeginning(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
node = self.Head
self.Head = self.Head.next
del node
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
40 20 30
The elements in the linked list are:
20 30
刪除連結串列的最後一個元素
要刪除連結串列的最後一個元素,我們將首先檢查連結串列是否為空。
為此,我們將檢查連結串列的 Head
是否指向 None
。如果是,我們將通知使用者連結串列為空,我們沒有要刪除的元素。
如果列表中存在元素,我們將遵循以下過程。
- 將第一個節點分配給變數
current
。 - 將變數
previous
初始化為None
。 - 使用
while
迴圈遍歷連結串列,將current
變數處的節點分配給previous
變數,將current
變數前進到下一個節點,直到current
變數到達最後一個節點.在這種情況下,分配給current
的節點的next
屬性變為None
。 - 一旦當前變數到達最後一個節點,我們將把
None
分配給previous
變數的next
屬性,並刪除分配給current
變數的節點。
我們可以通過執行上述步驟刪除連結串列的最後一個元素。如下所示,你可以在 deleteFromLast()
方法中實現整個邏輯。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteFromLast(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
while current.next is not None:
previous = current
current = current.next
previous.next = None
del current
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
10 40 20
The elements in the linked list are:
10 40
刪除連結串列中任意給定位置的元素
要刪除連結串列中任何給定位置的元素,我們將首先檢查連結串列是否為空。
為此,我們將檢查連結串列的 Head
是否指向 None
。如果是,我們將通知使用者連結串列為空,我們沒有要刪除的元素。
如果連結串列中存在元素,並且我們必須刪除任何其他位置的元素,我們將按照以下步驟操作。
- 將第一個節點分配給變數
current
。 - 將變數
previous
初始化為None
。 - 將變數
count
初始化為 1。 - 使用
while
迴圈遍歷連結串列,在每次迭代中遞增count
,將current
變數處的節點分配給previous
,並將current
變數前進到下一個節點直到count
變數具有要刪除的元素的位置
,或者我們到達連結串列的末尾。此時,變數 current 將指向必須刪除的節點。 - 一旦計數等於要刪除元素的位置,可能有兩種情況。
- 如果我們仍然在
Head
,在第一個位置,我們會將當前變數的next
屬性引用的節點分配給Head
屬性。之後,我們將刪除current
變數。 - 如果我們不在第一個位置,我們將把
current
變數的下一個節點分配給分配給previous
變數的節點的下一個屬性。我們將刪除分配給current
變數的節點。這樣,給定位置的元素將被刪除。
我們可以在下面討論的 deleteAtPosition()
方法中實現上述邏輯。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteAtPosition(self, position):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
count = 1
while current.next is not None and count < position:
previous = current
current = current.next
count += 1
if current == self.Head:
self.Head = current.next
del current
else:
previous.next = current.next
del current
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(2)
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
40 20 30
The elements in the linked list are:
40 30
在 Python 中計算連結串列中的元素數
要計算連結串列中元素的數量,我們只需將變數 count
初始化為 0。
之後,我們將從 Head
開始並使用 while
迴圈移動到下一個節點,直到到達連結串列的末尾。在 while
迴圈的每次迭代中,我們將 count
增加 1。
執行完 while
迴圈後,我們將在變數 count
中獲得連結串列中元素的數量。你可以按照下面的 countElements()
方法來實現此邏輯。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def countElements(self):
count = 0
current = self.Head
while current is not None:
count += 1
current = current.next
print("Number of elements in the linked list are:", count)
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.countElements()
輸出:
The elements in the linked list are:
10 40 20 30
Number of elements in the linked list are: 4
在 Python 中更新連結串列中的節點
更新連結串列中某個節點的值可能有兩種情況。
- 我們需要替換一個值。
- 我們需要為連結串列中任意給定位置的元素分配一個新值。
替換連結串列中的值
要替換連結串列中的值,我們將從第一個節點開始,並使用 while
迴圈遍歷連結串列。
我們將檢查 current
節點是否包含每個節點要替換的值。如果是,我們將用新值替換當前節點中的值。
通過這種方式,我們可以更新連結串列中任何元素的第一次出現,如 replaceElement()
方法所示。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def replaceElement(self, old_element, new_element):
current = self.Head
while current is not None:
if current.data == old_element:
current.data = new_element
break
current = current.next
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(30, 100)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(20, 150)
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
10 40 20 100
The elements in the linked list are:
10 40 150 100
更新連結串列中給定位置的元素
要更新連結串列中給定位置的元素,我們將首先檢查連結串列是否為空。如果是,可能有兩種情況。
如果連結串列為空並且我們必須更新第一個位置以外的元素,我們將通知使用者無法完成。
如果連結串列為空並且我們必須更新第一個位置的元素,我們將使用給定元素建立一個新節點並將該節點分配給連結串列的 Head
。否則,我們將變數 counter
初始化為 1。
之後,我們將使用 while
迴圈遍歷連結串列。在 while
迴圈的每次迭代中,我們將移動到連結串列中的下一個節點,將變數 counter
加 1,並檢查我們是否已經到達需要更新的元素位置。
如果到達需要更新的位置,我們會更新連結串列當前節點中的值並通知使用者。
如果我們無法到達需要更新的位置並且 while
迴圈終止,我們將通知使用者沒有足夠的元素並且我們無法更新值。這個邏輯可以在 updateAtPosition()
方法中實現,如下所示。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def updateAtPosition(self, new_element, position):
if self.Head is None and position != 1:
print("No element to update in the linked list.")
return
elif self.Head is None and position == 1:
newNode = Node(new_element)
self.Head = newNode
return
count = 1
current = self.Head
while current.next is not None and count < position:
count += 1
current = current.next
if count == position:
current.data = new_element
elif current.next is None:
print("Not enough elements in the linked list.")
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(100, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(150, 12)
print("The elements in the linked list are:")
myLinkedList.printList()
輸出:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
10 40 100 30
Not enough elements in the linked list.
The elements in the linked list are:
10 40 100 30
在 Python 中為什麼使用連結串列
- 如果你不需要隨機訪問元素,連結串列可能是更好的選擇。當我們有數百萬個元素要儲存並且不需要隨機訪問時,你應該在 Python 中使用連結串列而不是普通列表。
- 與列表中存在的元素數量相比,列表的實際大小非常大。列表的實際大小大約是其中存在的元素數量的 1.5 倍。它確保我們有足夠的記憶體將元素插入到列表中。但是,連結串列不需要額外的空格。
- 當我們將一個元素插入到連結串列中時,只需要儲存。列表還需要連續的記憶體位置。相反,連結串列的節點可以出現在實體記憶體中的任何位置。它們使用參考連線。
- 你可以使用連結串列有效地實現堆疊和佇列資料結構。另一方面,使用列表實現佇列的時間複雜度很高。
Python 中的完整實現連結串列
以下是使用本文討論的所有方法在 Python 中實現連結串列的完整執行程式碼。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtBeginning(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
newNode = Node(element)
newNode.next = self.Head
self.Head = newNode
def insertAtEnd(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
current = self.Head
while current.next is not None:
current = current.next
newNode = Node(element)
current.next = newNode
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteFromBeginning(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
node = self.Head
self.Head = self.Head.next
del node
def deleteFromLast(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
while current.next is not None:
previous = current
current = current.next
previous.next = None
del current
def deleteAtPosition(self, position):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
count = 1
while current.next is not None and count < position:
previous = current
current = current.next
count += 1
if current == self.Head:
self.Head = current.next
del current
else:
previous.next = current.next
del current
def countElements(self):
count = 0
current = self.Head
while current is not None:
count += 1
current = current.next
print("Number of elements in the linked list are:", count)
def replaceElement(self, old_element, new_element):
current = self.Head
while current is not None:
if current.data == old_element:
current.data = new_element
break
current = current.next
def updateAtPosition(self, new_element, position):
if self.Head is None and position != 1:
print("No element to update in the linked list.")
return
elif self.Head is None and position == 1:
newNode = Node(new_element)
self.Head = newNode
return
count = 1
current = self.Head
while current.next is not None and count < position:
count += 1
current = current.next
if count == position:
current.data = new_element
elif current.next is None:
print("Not enough elements in the linked list.")
まとめ
在本文中,我們討論了連結串列資料結構及其在 Python 中的實現。我們還實現了連結串列中各種操作的方法。
在本文中,我們已經使用方法實現了所有操作。你還可以使用以連結串列的 Head
作為輸入並在執行所需操作後返回頭部的函式來實現每個操作。
但是,這將在執行期間需要更多資源。因此,我建議你使用本文中使用的方法。