怎么用Python代碼實現雙鏈表

怎么用Python代碼實現雙鏈表

雙鏈表（Doubly Linked List）是一種常見的數據結構，它允許在鏈表中進行雙向遍歷。與單鏈表不同，雙鏈表的每個節點不僅包含指向下一個節點的指針，還包含指向前一個節點的指針。這使得在雙鏈表中插入、刪除和遍歷操作更加靈活。

本文將介紹如何使用Python代碼實現一個簡單的雙鏈表，并演示一些基本的操作。

雙鏈表的基本結構

雙鏈表的每個節點包含三個部分： 1. 數據域：存儲節點的數據。 2. 前驅指針：指向前一個節點。 3. 后繼指針：指向下一個節點。

在Python中，我們可以使用類來表示雙鏈表的節點和鏈表本身。

定義節點類

首先，我們定義一個Node類來表示雙鏈表的節點：

class Node:
    def __init__(self, data):
        self.data = data  # 數據域
        self.prev = None  # 前驅指針
        self.next = None  # 后繼指針

定義雙鏈表類

接下來，我們定義一個DoublyLinkedList類來表示雙鏈表本身。這個類將包含一些基本的操作，如插入、刪除和遍歷。

class DoublyLinkedList:
    def __init__(self):
        self.head = None  # 鏈表的頭節點
        self.tail = None  # 鏈表的尾節點

    def is_empty(self):
        """判斷鏈表是否為空"""
        return self.head is None

    def append(self, data):
        """在鏈表尾部添加節點"""
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def prepend(self, data):
        """在鏈表頭部添加節點"""
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def delete(self, data):
        """刪除鏈表中第一個匹配的節點"""
        current = self.head
        while current:
            if current.data == data:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next

                if current.next:
                    current.next.prev = current.prev
                else:
                    self.tail = current.prev

                return True  # 刪除成功
            current = current.next
        return False  # 未找到匹配的節點

    def display(self):
        """打印鏈表中的所有節點"""
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

雙鏈表的基本操作

1. 插入操作

雙鏈表的插入操作可以在鏈表的頭部或尾部進行。我們已經在DoublyLinkedList類中實現了append和prepend方法。

• append(data)：在鏈表尾部插入一個新節點。
• prepend(data)：在鏈表頭部插入一個新節點。

2. 刪除操作

雙鏈表的刪除操作可以通過delete方法實現。該方法會刪除鏈表中第一個匹配的節點。

3. 遍歷操作

雙鏈表的遍歷操作可以通過display方法實現。該方法會打印出鏈表中所有節點的數據。

示例代碼

下面是一個使用雙鏈表的示例代碼：

# 創建一個雙鏈表
dll = DoublyLinkedList()

# 在鏈表尾部添加節點
dll.append(1)
dll.append(2)
dll.append(3)

# 在鏈表頭部添加節點
dll.prepend(0)

# 打印鏈表
dll.display()  # 輸出: 0 <-> 1 <-> 2 <-> 3 <-> None

# 刪除節點
dll.delete(2)

# 打印鏈表
dll.display()  # 輸出: 0 <-> 1 <-> 3 <-> None

總結

本文介紹了如何使用Python代碼實現一個簡單的雙鏈表，并演示了插入、刪除和遍歷等基本操作。雙鏈表由于其雙向遍歷的特性，在某些場景下比單鏈表更加靈活和高效。通過掌握雙鏈表的基本操作，你可以更好地理解和應用這種數據結構。