Python程序创建链表并显示链表中的元素

在Python中创建链表并显示链表中的元素是一项基本任务，既可以在面试基础类的问题中使用，也可以用于实际编程项目。本文将介绍如何使用Python创建链表并显示链表中的元素，帮助读者更好地理解链表数据结构及其在Python编程中的应用。

什么是链表？

链表是一种线性数据结构，由一系列节点组成，每个节点包含指向下一个节点的指针。链表有单向链表、双向链表和循环链表等不同类型，可以实现灵活的内存管理，应用场景包括哈希表、图表存储等。

单向链表

单向链表是链表中最简单的一种类型，每个节点包含一个数据项和一个指向下一个节点的指针。它不支持在中间插入节点，删除节点或者查找倒数第n个节点，但具有前插、后插和反转链表等特殊操作。我们可以使用Python创建一个单向链表的数据结构，根据用户输入进行链表节点的添加和遍历：

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

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

    def add_node(self, data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = new_node

    def print_list(self):
        curr = self.head
        while curr:
            print(curr.data,end=" ")
            curr = curr.next

if __name__ == '__main__':
    my_list = LinkedList()
    my_list.add_node(1)
    my_list.add_node(2)
    my_list.add_node(3)
    my_list.print_list()

上述代码中，我们实现了Node和LinkedList两个类。Node类是定义每个节点的数据结构，包含一个数据项data和一个指向下一个节点的指针next。LinkedList类是定义整个链表的数据结构，包含一个头指针head和两个方法，add_node方法用于添加节点，print_list方法用于遍历节点并输出节点数据。

我们对LinkedList类进行实例化，并添加三个节点，最后通过print_list方法输出链表中所有节点的数据值。运行代码，输出结果如下：

1 2 3

双向链表

双向链表是链表的另一种数据结构，每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针。使用双向链表可以支持在中间插入/删除节点以及查找倒数第n个节点等操作，相比于单向链表具有更强的灵活性。我们可以使用Python创建一个双向链表的数据结构，并实现在链表中查找倒数第n个节点的方法：

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

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

    def add_node(self, data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = new_node
            new_node.prev = curr

    def print_list(self):
        curr = self.head
        while curr:
            print(curr.data, end=" ")
            curr = curr.next

    def find_nth_node(self, n):
        curr = self.head
        length = 0
        while curr:
            length += 1
            curr = curr.next
        if length < n:
            return None
        curr = self.head
        for i in range(length-n):
            curr = curr.next
        return curr

上述代码中，我们同样实现了Node和LinkedList两个类，不同处在于Node类中包含两个指针prev和next，分别指向前一个节点和后一个节点。find_nth_node方法是双向链表特有的，用于在链表中查找倒数第n个节点。

我们对LinkedList类进行实例化，并添加三个节点，然后调用find_nth_node方法查找链表中倒数第2个节点的数据值。运行代码，输出结果如下：

```python
my_list = LinkedList()
my_list.add_node(1)
my_list.add_node(2)
my_list.add_node(3)
print(my_list.find_nth_node(2).data)

输出结果为：

循环链表

循环链表是指链表中的最后一个节点指向第一个节点，形成一个环形结构。与其他链表不同的是，在循环链表中，不存在尾节点。我们可以使用Python创建一个循环链表的数据结构，并实现在链表中反转链表的方法：

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

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

    def add_node(self, data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            new_node.next = self.head
        else:
            curr = self.head
            while curr.next != self.head:
                curr = curr.next
            curr.next = new_node
            new_node.next = self.head

    def print_list(self):
        if self.head == None:
            return
        curr = self.head
        while curr.next != self.head:
            print(curr.data, end=" ")
            curr = curr.next
        print(curr.data,end=" ")

    def reverse_list(self):
        if self.head == None:
            return
        prev = None
        curr = self.head
        while curr.next != self.head:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        curr.next = prev
        self.head.next = curr
        self.head = curr

if __name__ == '__main__':
    my_list = CircularLinkedList()
    my_list.add_node(1)
    my_list.add_node(2)
    my_list.add_node(3)
    my_list.print_list()
    my_list.reverse_list()
    print()
    my_list.print_list()

上述代码中，我们同样实现了Node和LinkedList两个类，CircularLinkedList类与LinkedList类相似，不同之处在于在添加节点时需要特别处理最后一个节点指向第一个节点的情况。reverse_list方法是实现链表反转的方法，需要注意在循环链表中，头指针需要特别处理。

我们对CircularLinkedList类进行实例化，并添加三个节点，调用print_list方法输出链表中所有节点的数据值，再调用reverse_list方法进行链表反转，再次输出链表中所有节点的数据值。运行代码，输出结果如下：