Python双向循环链表实例详解

本文介绍如何通过Python实现双向循环链表，让读者更好地理解链表的概念和应用。全文包含以下内容：

1. 什么是双向循环链表？
2. 如何实现双向循环链表？
3. 双向循环链表的应用场景
4. Python双向循环链表的示例

什么是双向循环链表？

双向循环链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两个指针，分别指向前驱节点和后继节点。头节点的前驱节点指向尾节点，尾节点的后继节点指向头节点，形成了一个循环结构。

相比于单向链表，双向循环链表可以快速地访问前驱节点，因此更加方便实现双向遍历和双向查找等操作。同时，在删除节点时也更加方便。

如何实现双向循环链表？

实现双向循环链表，需要定义节点类和链表类，具体代码如下：

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def add_first(self, value):
        node = Node(value)

        if self.size == 0:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node

        self.size += 1

    def add_last(self, value):
        node = Node(value)

        if self.size == 0:
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node

        self.size += 1

    def remove_first(self):
        if self.size == 0:
            raise Exception("Linked list is empty")
        elif self.size == 1:
            node = self.head
            self.head = self.tail = None
        else:
            node = self.head
            self.head = node.next
            self.head.prev = None

        self.size -= 1
        return node.data

    def remove_last(self):
        if self.size == 0:
            raise Exception("Linked list is empty")
        elif self.size == 1:
            node = self.head
            self.head = self.tail = None
        else:
            node = self.tail
            self.tail = node.prev
            self.tail.next = None

        self.size -= 1
        return node.data

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

上面代码中，我们定义了一个Node类来表示链表的节点。每个节点包含三个属性：data表示存储的数据，prev表示前驱节点，next表示后继节点。

我们还定义了一个DoublyLinkedList类来管理整个链表。其中，head和tail分别表示头结点和尾节点，size表示链表长度。

add_first方法和add_last方法分别在链表的头部和尾部添加节点。在添加节点时，需要判断链表是否为空，如果为空，则头结点和尾节点都指向新加入的节点；如果不为空，则需要更改头结点或者尾节点的前驱和后继指针。

remove_first方法和remove_last方法分别在链表的头部和尾部删除节点。在删除节点时，同样需要判断链表是否为空，如果为空则抛出异常；如果链表只有一个节点，则需要将头结点和尾节点都置为None；如果链表有多个节点，则需要找到要删除的节点，修改前驱和后继指针。

最后，我们实现了__iter__方法，以便支持对链表的迭代。

双向循环链表的应用场景

双向循环链表在实际应用中非常广泛，例如浏览器的“前进”和“后退”功能、游戏中的物品管理等等。

下面我们以实例的形式来说明如何使用双向循环链表，以此加深对该数据结构和算法的理解。

Python双向循环链表的示例

下面是一个简单的示例，我们使用双向循环链表来实现一个数码游戏。

在数码游戏中，玩家需要将九个数字拼成一个3x3的矩阵。玩家可以通过交换相邻的数字来完成拼图。这个过程中，我们需要实时记录拼图的状态，这时候就可以用到双向循环链表了。

class Puzzle:
    def __init__(self, numbers):
        self.board = DoublyLinkedList()
        self.moves = []
        for number in numbers:
            self.board.add_last(number)

    def move_left(self):
        index = 1
        current = self.board.head.next
        while current:
            if current.data == 0:
                break
            index += 1
            current = current.next

        if index % 3 == 1:
            raise Exception("Cannot move left")

        current.data, current.prev.data = current.prev.data, current.data
        self.moves.append("L")

    def move_right(self):
        index = 1
        current = self.board.head.next
        while current:
            if current.data == 0:
                break
            index += 1
            current = current.next

        if index % 3 == 0:
            raise Exception("Cannot move right")

        current.data, current.next.data = current.next.data, current.data
        self.moves.append("R")

    def move_up(self):
        index = 0
        current = self.board.head
        while current:
            if current.data == 0:
                break
            index += 1
            current = current.next

        if index < 3:
            raise Exception("Cannot move up")

        i = 0
        current = self.board.head
        while i < index - 3:
            current = current.next
            i += 1

        current.data, current.prev.data = current.prev.data, current.data
        self.moves.append("U")

    def move_down(self):
        index = 0
        current = self.board.head
        while current:
            if current.data == 0:
                break
            index += 1
            current = current.next

        if index > 5:
            raise Exception("Cannot move down")

        i = 0
        current = self.board.head
        while i < index + 3:
            current = current.next
            i += 1

        current.data, current.prev.data = current.prev.data, current.data
        self.moves.append("D")

    def print_board(self):
        for i, number in enumerate(self.board):
            print(number, end=" ")
            if i % 3 == 2:
                print()
        print()

上面这个代码中，我们首先定义了一个Puzzle类，这个类包含一个双向循环链表board来存储拼图状态。对于拼图中的每一块，我们都使用一个数字来表示，其中数字0表示空白块。

我们可以通过move_left、move_right、move_up和move_down方法来移动拼图的空白块，这里涉及到了判断拼图中每个块的位置关系，如果空白块可以移动，则交换空白块和它所在的块。我们用moves数组记录下每一步的移动方向。最后，我们还提供了print_board方法，用于打印当前拼图的状态。

现在我们可以通过以下代码来测试这个类的功能：

puzzle = Puzzle([2, 8, 3, 1, 6, 4, 7, 0, 5])

puzzle.move_right()
puzzle.print_board()
puzzle.move_right()
puzzle.print_board()
puzzle.move_down()
puzzle.print_board()
puzzle.move_down()
puzzle.print_board()
puzzle.move_left()
puzzle.print_board()
puzzle.move_up()
puzzle.print_board()
puzzle.move_left()
puzzle.print_board()
puzzle.move_up()
puzzle.print_board()

print(puzzle.moves)

以上就是Python实现双向循环链表的示例。本文中，我们首先介绍了什么是双向循环链表，然后讲解了如何使用Python来实现双向循环链表，最后，我们通过一个实际的数码游戏来展示双向循环链表的应用。