python实现双链表

实现双链表需要明确双链表的特点：每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。双链表的操作包括插入、删除、查找等。接下来，我将详细讲解如何在Python中实现双链表。

1. 定义节点类

class Node:
    def __init__(self, data):
        self.data = data  # 数据
        self.prev = None  # 前一个节点的指针
        self.next = None  # 后一个节点的指针

在这段代码中，我们定义了一个节点类，这个类包含三个成员变量。其中，data代表节点中存储的数据，prev代表前一个节点的指针，next代表后一个节点的指针。

2. 定义双链表类

class DoubleLinkedList:
    def __init__(self):
        self.head = None  # 头节点
        self.tail = None  # 尾节点
        self.length = 0   # 链表长度

    # 插入节点
    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail  # 新节点的prev指向尾节点
            self.tail.next = new_node  # 尾节点的next指向新节点
            self.tail = new_node       # 更新尾节点
        self.length += 1

    # 删除节点
    def delete(self, data):
        current = self.head
        while current is not None:
            if current.data == data:
                if current == self.head:
                    self.head = current.next
                    if self.head is not None:
                        self.head.prev = None
                    else:
                        self.tail = None
                elif current == self.tail:
                    self.tail = current.prev
                    self.tail.next = None
                else:
                    current.prev.next = current.next
                    current.next.prev = current.prev
                self.length -= 1
                return
            current = current.next

    # 遍历节点
    def traverse(self):
        current = self.head
        while current is not None:
            print(current.data)
            current = current.next

在这段代码中，我们定义了一个双链表类，这个类包含三个成员变量：head代表头节点、tail代表尾节点、length代表链表长度。这个类还包含了三个方法：

• insert(data)：插入节点
• delete(data)：删除节点
• traverse()：遍历节点

3. 示例说明

示例1：用双链表实现数字加1

假设现在有一个整数链表，链表每个节点存储一位数字，头节点代表数字的最高位，尾节点代表数字的最低位。现在需要用双链表实现这个数字加1的功能。例如，输入链表1->2->3->4，输出链表1->2->3->5。代码如下：

class Solution:
    def plusOne(self, head: ListNode) -> ListNode:
        current = head
        carry = 1
        while current is not None:
            current.val += carry
            if current.val > 9:
                current.val = 0
            else:
                carry = 0
                break
            current = current.next
        if carry == 1:
            new_node = ListNode(1)
            new_node.next = head
            head = new_node
        return head

在这个示例中，我们定义了一个Solution类，这个类包含了一个plusOne()方法，用于实现数字加1的功能。在plusOne()方法中，我们首先遍历整个链表，对每个节点进行加1操作，当节点的值大于9时，将该节点的值设为0，并将carry置为1。当遍历完整个链表后，如果carry仍为1，说明需要在链表头插入一个值为1的节点。最后返回链表头。

示例2：用双链表实现LRU缓存

LRU缓存是一种常用的缓存算法，它的原理是将最近没有使用的缓存淘汰掉。我们可以用双链表实现LRU缓存的功能。例如，输入一组缓存数据，大小为3，访问顺序为1->2->3->4->1->2->5，输出淘汰掉的缓存和最终缓存的顺序。代码如下：

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity  # 缓存容量
        self.cache = DoubleLinkedList()  # 双链表存储缓存
        self.keys = {}  # 哈希表存储键值对

    def get(self, key: int) -> int:
        if key in self.keys:
            self.cache.delete(key)
            self.cache.insert(key)
            return self.keys[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.keys:
            self.cache.delete(key)
            self.cache.insert(key)
            self.keys[key] = value
        else:
            if self.cache.length == self.capacity:
                remove_key = self.cache.head.data
                self.cache.delete(remove_key)
                del self.keys[remove_key]
            self.cache.insert(key)
            self.keys[key] = value

    def traverse(self):
        self.cache.traverse()

# 示例
cache = LRUCache(3)
cache.put(1, 'A')
cache.put(2, 'B')
cache.put(3, 'C')
cache.put(4, 'D')
cache.put(1, 'A')
cache.put(2, 'B')
cache.put(5, 'E')
cache.traverse()

在这个示例中，我们定义了一个LRUCache类，这个类包含了三个方法：

• get(key)：获得键值对
• put(key, value)：存储键值对
• traverse()：遍历链表（测试用）

在put()方法中，我们首先判断输入的key是否已经存在于哈希表中。如果存在，我们就将这个key对应的节点移动到链表尾部，并更新哈希表中的值。如果不存在，我们就在链表尾部插入新节点，同时在哈希表中新建一个键值对。另外，如果缓存已经满了，我们就淘汰链表头部的节点。在get()方法中，我们只需要判断输入的key是否存在于哈希表中即可。

在这个示例中，我们用LRUCache类（缓存大小为3）存储了一组键值对（1->A、2->B、3->C、4->D、1->A、2->B、5->E）。我们将缓存的遍历结果输出，即可看到最终缓存的顺序。注意，在这个示例中，对于哪些需要删除的缓存数据，被淘汰的缓存顺序输出为：4->1->2。