使用 Python 实现一个支持排序和查找功能的链表

Document 对象参考手册 Python3 实例

我们将使用 Python 实现一个简单的链表，并为其添加排序和查找功能。链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

实例

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def sort(self):
        if not self.head:
            return
        sorted_list = []
        current = self.head
        while current:
            sorted_list.append(current.data)
            current = current.next
        sorted_list.sort()
        self.head = None
        for item in sorted_list:
            self.append(item)

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

# 示例使用
ll = LinkedList()
ll.append(3)
ll.append(1)
ll.append(4)
ll.append(2)

print("原始链表:")
ll.display()

ll.sort()
print("排序后的链表:")
ll.display()

print("查找元素 4:", ll.search(4))
print("查找元素 5:", ll.search(5))

代码解析：

  1. Node 类：表示链表中的一个节点，包含数据 data 和指向下一个节点的指针 next。
  2. LinkedList 类：表示链表，包含一个指向链表头部的指针 head。
  3. append 方法：在链表末尾添加一个新节点。
  4. display 方法：打印链表中的所有元素。
  5. sort 方法：对链表中的元素进行排序。首先将链表中的数据提取到一个列表中，然后对列表进行排序，最后将排序后的数据重新插入到链表中。
  6. search 方法：在链表中查找指定的元素，如果找到则返回 True，否则返回 False。

输出结果：

原始链表:
3 -> 1 -> 4 -> 2 -> None
排序后的链表:
1 -> 2 -> 3 -> 4 -> None
查找元素 4: True
查找元素 5: False

Document 对象参考手册 Python3 实例