Python 中的連結列表

Aditya Raj 2023年1月30日 2022年5月17日
  1. 什麼是 Python 中的連結串列
  2. 在 Python 中如何建立連結串列
  3. 在 Python 中列印連結串列的所有元素
  4. 在 Python 中將元素插入到連結串列中
  5. 從 Python 中的連結串列中刪除一個元素
  6. 在 Python 中計算連結串列中的元素數
  7. 在 Python 中更新連結串列中的節點
  8. 在 Python 中為什麼使用連結串列
  9. Python 中的完整實現連結串列
  10. まとめ
Python 中的連結列表

Python 為我們提供了各種內建的資料結構。

但是,每種資料結構都有其侷限性。因此,我們需要自定義資料結構。

本文將討論一種稱為連結串列的自定義資料結構。我們還將在 Python 中實現一個連結串列,並對連結串列進行各種操作。

什麼是 Python 中的連結串列

顧名思義,連結串列是一種資料結構,其中包含使用連結連線的元素。

連結串列是使用稱為節點的物件建立的。每個節點包含兩個屬性——一個用於儲存資料,另一個用於連線到連結串列中的下一個節點。

你可以使用下圖瞭解節點的結構。

Python 中的節點

這裡,

  • Node 是包含屬性 datanext 的物件。
  • 屬性 data 儲存資料。
  • 屬性 next 指連結串列中的下一個節點。

如下圖所示,我們可以連線各個節點來建立一個連結串列。

Python 中的連結串列

這裡,

  • 我們建立了一個由四個節點組成的連結串列。
  • 第一個節點包含數字 10,第二個節點包含 20,第三個節點包含 30,最後一個節點包含 40。
  • 我們還建立了一個引用第一個節點的變數 Head。我們只將 Head 變數儲存在連結串列物件中。所有其他節點中的資料都是通過從 Head 引用的第一個節點開始遍歷連結串列獲得的。
  • 最後一個節點的 next 屬性指的是 None 物件。連結串列最後一個節點的 next 屬性將始終引用 None 物件。
  • 如果連結串列為空,則 Head 變數將引用 None 物件。

我們現在瞭解了連結串列的基本結構。讓我們在 Python 中實現一個連結串列。

在 Python 中如何建立連結串列

由於節點是連結串列的構建塊,我們將首先建立一個節點。為此,我們將定義一個具有屬性 datanextNode 類,如下所示。

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

在上面的例子中,你可以觀察到 Nodenext 屬性預設是指 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 中將元素插入到連結串列中

在連結串列中插入元素有四種情況。

  1. 連結串列在插入前可以為空。
  2. 我們必須在非空連結串列的開頭插入一個元素。
  3. 我們必須在連結串列的末尾插入一個元素。
  4. 我們必須在連結串列的給定位置插入一個元素。

讓我們討論如何在所有情況下將元素插入到連結串列中。

將元素插入空連結串列

要將元素插入空連結串列,我們將定義一個方法 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 中的連結串列中刪除一個元素

當我們試圖從連結串列中刪除一個元素時,可能有三種情況。

  1. 我們要刪除連結串列的第一個元素。
  2. 我們要刪除連結串列的最後一個元素。
  3. 我們必須刪除連結串列中任意位置的元素。

讓我們一一討論所有這些情況。

刪除連結串列的第一個元素

要刪除連結串列的第一個元素,我們將首先檢查連結串列是否為空。

為此,我們將檢查連結串列的 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。如果是,我們將通知使用者連結串列為空,我們沒有要刪除的元素。

如果列表中存在元素,我們將遵循以下過程。

  1. 將第一個節點分配給變數 current
  2. 將變數 previous 初始化為 None
  3. 使用 while 迴圈遍歷連結串列,將 current 變數處的節點分配給 previous 變數,將 current 變數前進到下一個節點,直到 current 變數到達最後一個節點.在這種情況下,分配給 current 的節點的 next 屬性變為 None
  4. 一旦當前變數到達最後一個節點,我們將把 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。如果是,我們將通知使用者連結串列為空,我們沒有要刪除的元素。

如果連結串列中存在元素,並且我們必須刪除任何其他位置的元素,我們將按照以下步驟操作。

  1. 將第一個節點分配給變數 current
  2. 將變數 previous 初始化為 None
  3. 將變數 count 初始化為 1。
  4. 使用 while 迴圈遍歷連結串列,在每次迭代中遞增 count,將 current 變數處的節點分配給 previous,並將 current 變數前進到下一個節點直到 count 變數具有要刪除的元素的位置,或者我們到達連結串列的末尾。此時,變數 current 將指向必須刪除的節點。
  5. 一旦計數等於要刪除元素的位置,可能有兩種情況。
  6. 如果我們仍然在 Head,在第一個位置,我們會將當前變數的 next 屬性引用的節點分配給 Head 屬性。之後,我們將刪除 current 變數。
  7. 如果我們不在第一個位置,我們將把 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 中更新連結串列中的節點

更新連結串列中某個節點的值可能有兩種情況。

  1. 我們需要替換一個值。
  2. 我們需要為連結串列中任意給定位置的元素分配一個新值。

替換連結串列中的值

要替換連結串列中的值,我們將從第一個節點開始,並使用 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 作為輸入並在執行所需操作後返回頭部的函式來實現每個操作。

但是,這將在執行期間需要更多資源。因此,我建議你使用本文中使用的方法。

相關文章 - Python Data Structure