怎么使用Python实现单链表

第一段：单链表基本概念以及节点实现

在设计一个单链表之前，我们需要知道单链表的基本概念，单链表是一种线性数据结构，它由多个节点组成，每个节点包含两部分数据：数据域和指针域。其中数据域用于存储数据，指针域则用于指向下一个节点。

为了实现单链表，我们需要先实现一个节点类。在Python中，我们可以使用类来实现节点。以下是一个基本的单链表节点类：

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

在这个实现中，我们定义了一个名为ListNode的类。该类包含两个属性，分别是val和next。其中，val属性用于存储节点的数据，next属性则用于指向下一个节点。在初始化一个新的节点时，我们需要提供节点的数据和它的下一个节点。

第二段：单链表创建与插入

有了节点的基础类，我们就可以实现一个单链表了。以下是单链表的创建方法：

class LinkedList:
    
    def __init__(self):
        self.head = None
        self.size = 0
        
    def addAtHead(self, val: int) -> None:
        """
        在链表头部添加一个节点。
        """
        newNode = ListNode(val)
        newNode.next = self.head
        self.head = newNode
        self.size += 1

在这个实现中，我们定义了一个名为LinkedList的类。该类包含两个属性，head和size。其中，head属性用于指向链表的头节点，size属性则存储链表的大小。在初始化一个新的链表时，我们需要将head属性设置为None，size属性设置为0。

我们还实现了addAtHead方法，该方法接受一个整数参数val，然后在链表头部添加一个新节点。在这个方法中，我们首先创建一个新的节点，然后将新节点的next属性设置为链表的头节点，最后将链表的头节点设置为新节点。为了维护链表的大小，我们还将size属性加1。

为了展示节点的插入，我们实现了一个addAtIndex方法：

class LinkedList:
    
    # ...

    def addAtIndex(self, index: int, val: int) -> None:
        """
        在指定索引处添加一个节点。
        """
        if index <= 0:
            self.addAtHead(val)
        elif index == self.size:
            self.addAtTail(val)
        elif index > self.size:
            return
        else:
            newNode = ListNode(val)
            curr = self.head
            for i in range(index - 1):
                curr = curr.next
            newNode.next = curr.next
            curr.next = newNode
            self.size += 1

在这个实现中，我们定义了一个addAtIndex方法。该方法接受两个参数，一个整数参数index和一个整数参数val。该方法将创建一个新节点，并将其插入到链表的指定位置。如果插入索引小于等于0，则将新节点插入到链表的头部。如果插入索引大于等于链表的大小，则不执行任何操作。否则，我们将遍历链表，直到找到指定索引之前的那个节点。然后我们插入新节点，并将它的next属性指向原来下标对应位置节点的next属性。为了维护链表的大小，我们还将size属性加1。

第三段： 单链表删除与遍历

以下是单链表删除操作实现：

class LinkedList:
    
    # ...

    def deleteAtIndex(self, index: int) -> None:
        """
        删除指定索引处的节点。
        """
        if index < 0 or index >= self.size:
            return
        if index == 0:
            self.head = self.head.next
        else:
            curr = self.head
            for i in range(index - 1):
                curr = curr.next
            curr.next = curr.next.next
        self.size -= 1

在这个实现中，我们定义了一个deleteAtIndex方法。该方法接受一个整数参数index，从单链表中删除指定索引的节点。如果删除索引小于0或者大于等于链表的大小，则不执行任何操作。如果删除索引为0，则将头节点指向下一个节点。否则，我们将遍历链表，直到找到指定索引的前一个节点。然后我们将它的next属性指向下个节点的next属性。为了维护链表的大小，我们还将size属性减1。

以下是单链表遍历操作实现：

class LinkedList:
    
    # ...

    def printList(self) -> None:
        """
        输出链表中所有节点的数值。
        """
        curr = self.head
        while curr:
            print(curr.val)
            curr = curr.next

在这个实现中，我们定义了一个printList方法，该方法遍历并输出链表中所有节点的数值。

第四段： 单链表使用案例

下面是一个使用单链表实现栈的示例：

class LinkedListStack:
    
    def __init__(self):
        self.linkedList = LinkedList()
        
    def push(self, val: int) -> None:
        """
        将一个元素压入栈顶。
        """
        self.linkedList.addAtHead(val)
    
    def pop(self) -> int:
        """
        弹出栈顶元素。如果栈为空，则返回-1。
        """
        if self.linkedList.size == 0:
            return -1
        val = self.linkedList.head.val
        self.linkedList.deleteAtIndex(0)
        return val
    
    def peek(self) -> int:
        """
        返回栈顶元素。如果栈为空，则返回-1。
        """
        if self.linkedList.size == 0:
            return -1
        return self.linkedList.head.val
    
    def isEmpty(self) -> bool:
        """
        返回栈是否为空。
        """
        return self.linkedList.size == 0

在这个实现中，我们定义了一个名为LinkedListStack的栈类。该类利用单链表实现了一个栈。在初始化一个新的栈时，我们需要创建一个新的LinkedList实例。

我们将push方法实现为在链表的头部添加一个新节点。我们将pop方法实现为弹出链表头节点并返回该节点的数值。我们还实现了peek方法和isEmpty方法，用于返回栈顶元素和判断栈是否为空。

使用单链表来实现数据结构，可以让我们更加灵活地处理不同类型的数据。通过链表节点之间的指针，我们可以实现自由的节点操作，从而设计出复杂的数据结构。