Python双向循环链表实现方法分析

什么是双向循环链表

双向循环链表是一种数据结构，它有两个指针，分别指向前后两个节点，每个节点还有两个指针分别指向前一个和后一个节点，这个可以看做一个圆圈，所以被称为循环链表。与普通链表不同的是，双向循环链表的每个节点有两个指针，这使得双向循环链表在某些场景下比普通链表更加方便。

双向循环链表的实现

定义节点类

首先我们需要定义一个节点类，该类包含一个 element 属性表示节点元素，以及 prev 和 next 属性分别表示前一个节点和后一个节点。

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

定义双向链表类

接下来我们需要定义一个双向链表类，该类包含一个 head 属性表示链表头节点，以及一个 tail 属性表示链表尾节点。我们还需要定义若干方法来增删查改双向链表中的节点。

class DoubleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        return self.head is None

    def insert_head(self, elem):
        """在链表头部插入元素"""
        node = Node(elem)
        if self.is_empty():
            self.head = node
            self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node

    def insert_tail(self, elem):
        """在链表尾部插入元素"""
        node = Node(elem)
        if self.is_empty():
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node

    def remove(self, elem):
        """删除指定元素"""
        cur_node = self.head
        while cur_node:
            if cur_node.element == elem:
                if cur_node == self.head:
                    self.head = cur_node.next
                    if self.head:
                        self.head.prev = None
                else:
                    cur_node.prev.next = cur_node.next
                    if cur_node != self.tail:
                        cur_node.next.prev = cur_node.prev
                    else:
                        self.tail = cur_node.prev
                return True
            else:
                cur_node = cur_node.next
        return False

    def find(self, elem):
        """查找指定元素"""
        cur_node = self.head
        while cur_node:
            if cur_node.element == elem:
                return True
            else:
                cur_node = cur_node.next
        return False

    def show(self):
        """显示链表元素"""
        cur_node = self.head
        while cur_node:
            print(cur_node.element, end=' ')
            cur_node = cur_node.next
        print()

双向链表的应用示例

示例1：将元素插入到链表头部

double_linked_list = DoubleLinkedList()
double_linked_list.insert_head(10)
double_linked_list.insert_head(20)
double_linked_list.insert_head(30)
double_linked_list.show()      # 30 20 10

示例2：将元素插入到链表尾部

double_linked_list = DoubleLinkedList()
double_linked_list.insert_tail(10)
double_linked_list.insert_tail(20)
double_linked_list.insert_tail(30)
double_linked_list.show()      # 10 20 30

总结

双向循环链表是一种常见的数据结构，它是单向链表的扩展版，具有更强大的查找和操作能力。在实现双向循环链表时，需要先定义节点类，再通过节点类来实现双向链表类。