Python数据结构之链表详解

链表简介

链表是一种数据结构，其每个节点都包含一个指向下一个节点的指针。链表可以用来表示序列，集合或映射等数据结构。在Python中，链表通常由节点和链表类来实现。

单向链表

单向链表是一种链表，每个节点包含指向下一个节点的指针。在Python中，一个节点可以由一个简单的对象表示，而整个链表必须由相互链接的节点组成。

下面是一个示例代码，创建了一个简单的单向链表类：

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

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

在这个示例中，链表由head和tail表示。head是链表的第一个节点，tail是链表的最后一个节点。Node类包含data和next_node变量，表示节点的数据和指向下一个节点的指针。

下面是单向链表的操作函数：

class LinkedList:
    ...

    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:
            self.tail.next_node = new_node
            self.tail = new_node

    def find(self, data):
        current = self.head

        while current is not None:
            if current.data == data:
                return current

            current = current.next_node

        return None

    def delete(self, data):
        current = self.head
        previous = None

        while current is not None:
            if current.data == data:
                if previous is not None:
                    previous.next_node = current.next_node
                    if current.next_node is None:
                        self.tail = previous
                else:
                    self.head = current.next_node
                    if current.next_node is None:
                        self.tail = None
                return current

            previous = current
            current = current.next_node

        return None

在这些操作函数中，is_empty函数检查链表是否为空。append函数将新节点添加到链表的末尾。find函数在链表中查找值等于数据的节点。delete函数从链表中删除值等于数据的节点。

下面是单向链表的示例：

# 创建一个链表对象
my_list = LinkedList()

# 在链表末尾添加元素
my_list.append(1)
my_list.append(2)
my_list.append(3)

# 查找元素
node = my_list.find(2)

# 从链表中删除元素
my_list.delete(2)

双向链表

双向链表是一种链表，每个节点包含指向前一个节点和下一个节点的指针。在Python中，一个节点可以由一个简单的对象表示，而整个链表必须由相互链接的节点组成。

下面是一个示例代码，创建了一个简单的双向链表类：

class Node:
    def __init__(self, data=None, next_node=None, prev_node=None):
        self.data = data
        self.next_node = next_node
        self.prev_node = prev_node

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

在这个示例中，链表由head和tail表示。head是链表的第一个节点，tail是链表的最后一个节点。Node类包含data、next_node和prev_node变量，表示节点的数据、指向下一个节点的指针和指向前一个节点的指针。

下面是双向链表的操作函数：

class DoublyLinkedList:
    ...

    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_node = self.tail
            self.tail.next_node = new_node
            self.tail = new_node

    def find(self, data):
        current = self.head

        while current is not None:
            if current.data == data:
                return current

            current = current.next_node

        return None

    def delete(self, data):
        current = self.head

        while current is not None:
            if current.data == data:
                if current.prev_node is not None:
                    current.prev_node.next_node = current.next_node
                else:
                    self.head = current.next_node

                if current.next_node is not None:
                    current.next_node.prev_node = current.prev_node
                else:
                    self.tail = current.prev_node

                return current

            current = current.next_node

        return None

在这些操作函数中，is_empty函数检查链表是否为空。append函数将新节点添加到链表的末尾。find函数在链表中查找值等于数据的节点。delete函数从链表中删除值等于数据的节点。

下面是双向链表的示例：

# 创建一个链表对象
my_list = DoublyLinkedList()

# 在链表末尾添加元素
my_list.append(1)
my_list.append(2)
my_list.append(3)

# 查找元素
node = my_list.find(2)

# 从链表中删除元素
my_list.delete(2)

以上是针对“Python数据结构之链表详解”的完整攻略和两条示例说明，希望能对你有所帮助。