实现一个自定义链表通常需要定义一个节点类和一个链表类。节点类用于存储数据和指向下一个节点的引用；链表类则包含管理链表的操作，例如插入、删除、遍历等。下面是一个简单的单链表实现。
1. 定义节点类

class Node:
    def __init__(self, data):
        self.data = data # 节点的数据
        self.next = None # 指向下一个节点的指针

2. 定义链表类

链表类包含管理节点的方法，比如插入节点、删除节点、查找节点、遍历等。

class LinkedList:
def __init__(self):
self.head = None # 链表的头节点

    def append(self, data):
        """在链表尾部添加新节点"""
        new_node = Node(data)
        if self.head is None: # 如果链表为空，新节点就是头节点
            self.head = new_node
            return
        last = self.head
        while last.next: # 遍历找到链表的最后一个节点
            last = last.next
        last.next = new_node # 将最后一个节点的 next 指向新节点

    def prepend(self, data):
        """在链表头部添加新节点"""
        new_node = Node(data)
        new_node.next = self.head # 新节点的 next 指向当前头节点
        self.head = new_node # 更新头节点

    def delete(self, key):
        """根据数据删除节点"""
        current = self.head
        if current and current.data == key: # 如果头节点就是要删除的节点
            self.head = current.next # 将头节点指向下一个节点
            current = None
            return
        prev = None
        while current and current.data != key: # 查找要删除的节点
            prev = current
            current = current.next
        if current is None: # 节点不存在
            return
        prev.next = current.next # 将前一个节点的 next 指向当前节点的 next
        current = None

    def find(self, key):
        """查找节点并返回 True 或 False"""
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def display(self):
        """显示链表中的所有节点"""
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print("->".join(map(str, elements)))

3. 测试链表

# 创建链表
ll = LinkedList()

# 添加节点
ll.append(10)
ll.append(20)
ll.prepend(5)
ll.display() # 输出: 5->10->20

# 删除节点
ll.delete(10)
ll.display() # 输出: 5->20

# 查找节点
print(ll.find(20)) # 输出: True
print(ll.find(10)) # 输出: False

解释

    Node 类：每个 Node 对象包含 data 和 next。data 是节点的数据，next 是指向下一个节点的指针。
    LinkedList 类：
        append 方法：在链表尾部添加节点。
        prepend 方法：在链表头部插入节点。
        delete 方法：找到要删除的数据并从链表中移除节点。
        find 方法：在链表中查找某个数据。
        display 方法：以链表的顺序输出所有节点的数据。

扩展

可以进一步实现双向链表（每个节点都有 prev 和 next）。
实现长度计数、反转链表、插入特定位置等其他功能。

ITPub博客

如何实现一个自定义的链表？

最新文章