双向链表的定义与基本操作

双向链表简介

双向链表（Doubly Linked List）是一种线性数据结构，其中每个节点不仅包含指向下一个节点的链接，还包含指向前一个节点的链接。这种双面性使得双向链表在插入、删除等操作上具有更高的灵活性和效率。

节点定义

每个节点包含三个部分：数据域、前驱指针和后继指针。以下是Python中节点类的实现：

class Node:
    def __init__(self, data=None):
        self.data = data  # 节点存储的数据
        self.prev = None   # 指向前驱节点
        self.next = None   # 指向后继节点

双向链表类定义

为了管理这些节点，我们定义了一个双向链表类，该类提供了多种常用操作，如添加、删除、查找等。

class DoublyLinkedList:
    def __init__(self):
        self.head = None  # 初始化头节点为空

    def is_empty(self):
        return self.head is None  # 判断链表是否为空

    def length(self):
        count = 0
        current = self.head
        while current is not None:
            count += 1
            current = current.next
        return count  # 返回链表长度

    def add(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node  # 将新节点添加到头部

    def append(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node
            new_node.prev = current  # 将新节点添加到尾部

    def insert(self, index, data):
        if index <= 0:
            self.add(data)
        elif index >= self.length():
            self.append(data)
        else:
            new_node = Node(data)
            current = self.head
            position = 0
            while position                 current = current.next
                position += 1
            new_node.prev = current
            new_node.next = current.next
            current.next.prev = new_node
            current.next = new_node  # 在指定位置插入节点

    def remove(self, data):
        current = self.head
        while current is not None:
            if current.data == data:
                if current == self.head:
                    self.head = current.next
                    if current.next is not None:
                        current.next.prev = None
                else:
                    current.prev.next = current.next
                    if current.next is not None:
                        current.next.prev = current.prev
                return True
            current = current.next
        return False  # 删除指定值的节点

    def search(self, data):
        current = self.head
        while current is not None:
            if current.data == data:
                return True
            current = current.next
        return False  # 查找指定值是否存在

    def traverse(self):
        current = self.head
        while current is not None:
            print(current.data, end='\t')
            current = current.next
        print()  # 遍历并打印链表中的所有元素

示例代码执行结果

通过以下代码可以创建一个双向链表，并演示其各种操作的结果：

if __name__ == '__main__':
    dll = DoublyLinkedList()
    dll.add(11)
    dll.add(22)
    print('初始链表:')
    dll.traverse()
    print('追加元素:')
    dll.append(100)
    dll.append(200)
    dll.traverse()
    print('指定位置插入:')
    dll.insert(-1, 44)
    dll.insert(2, 33)
    dll.traverse()
    print('删除节点:')
    dll.remove(44)
    dll.remove(200)
    dll.remove(33)
    dll.traverse()
    print('链表长度:', dll.length())
    print('查找节点22:', dll.search(22))