用Python实现带有头结点的链表（Linked List with Head Node）

2023-04-11 00:00:00 结点链表带有

链表是一种重要的数据结构，它可以用来存储一系列元素。链表包含一个头结点和若干个数据结点，每个数据结点都包含一个数据项和一个指向下一个数据结点的指针。头结点不包含任何数据项，只包含一个指向第一个数据结点的指针。

Python的链表可以使用类来实现，数据结点可以定义为类中的一个对象，头节点也是一个对象，可以在链表初始化的时候创建。下面是一个简单的实现示例：

class ListNode:
    def __init__(self, val=None):
        self.val = val
        self.next = None

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

    def append(self, val):
        new_node = ListNode(val)
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node

    def show(self):
        cur = self.head.next
        while cur:
            print(cur.val, end=" ")
            cur = cur.next
        print()

这个示例中，链表的构造函数会创建一个空的头结点。append()函数可以在链表末尾添加一个新的节点。show()函数可以按顺序输出链表中的所有数据项。下面是一个简单的例子：

lst = LinkedList()
lst.append('p')
lst.append('i')
lst.append('d')
lst.append('a')
lst.append('n')
lst.append('c')
lst.append('o')
lst.append('d')
lst.append('e')
lst.show() # 输出 p i d a n c o d e

需要注意的是，Python中的链表实现并没有严格遵循C语言中的传统，C语言的链表不存在头结点，头结点可以视为链表的特殊节点。

相关文章