class Node: def init(self, value): self.value = value self.prev = None self.next = None class DoublyLinkedList: def init(self): self.head = Node(None) def is_empty(self): return self.head.next == None def insert(self, value): new_node = Node(value) current_node = self.head while current_node.next != None: current_node = current_node.next current_node.next = new_node new_node.prev = current_node def get_length(self): count = 0 current_node = self.head while current_node.next != None: count += 1 current_node = current_node.next return count def insert_at(self, value, position): if position < 1 or position > self.get_length() + 1: print('Invalid position') return new_node = Node(value) current_node = self.head for i in range(position - 1): current_node = current_node.next new_node.prev = current_node new_node.next = current_node.next current_node.next.prev = new_node current_node.next = new_node def append(self, value): new_node = Node(value) current_node = self.head while current_node.next != None: current_node = current_node.next current_node.next = new_node new_node.prev = current_node def remove(self, value): current_node = self.head.next while current_node != None: if current_node.value == value: current_node.prev.next = current_node.next if current_node.next != None: current_node.next.prev = current_node.prev return current_node = current_node.next print('Value not found') def find(self, value): current_node = self.head.next while current_node != None: if current_node.value == value: return current_node current_node = current_node.next print('Value not found') def traverse_prev(self): current_node = self.head.next while current_node != None: print(current_node.value) current_node = current_node.prev def traverse_next(self): current_node = self.head.next while current_node != None: print(current_node.value) current_node = current_node.next #测试 dll = DoublyLinkedList() # (1)初始化一个双链表DLL。 print(dll.is_empty()) # (2)判断DLL是否为空。 dll.insert(14) #(3)将值为14、94、84、56、11的结点依次链入DLL中。 dll.insert(94) dll.insert(84) dll.insert(56) dll.insert(11) print(dll.get_length()) # (4)获取DLL的长度。 dll.insert_at(6, 3) # (5)将值为6的结点插至DLL中第3个位置。 dll.append(23) # (6)在DLL末端插入值为23的结点。 dll.remove(14) # (7)删除DLL中第1个位置的结点。 print(dll.find(94).value) # (8)查找DLL中值为94的结点。 dll.traverse_prev() # (9)按prev域依次遍历DLL中所有结点。 dll.traverse_next() # (10)按next域依次遍历DLL中所有结点。

这是一个双向链表的Python代码，包含了节点类和双向链表类。

节点类包含了值、前驱和后继三个属性；

双向链表类有头部节点，以及判断链表是否为空、插入元素、获取链表长度、在指定位置插入元素、在末尾添加元素、删除元素、查找元素、正向遍历和反向遍历等方法。

相关问题

class Node: def __init__(self, value): self.value = value self.next = None class CircularLinkedList: def __init__(self): self.head = None def add(self, value): node = Node(value) if not self.head: self.head = node node.next = node else: curr = self.head while curr.next != self.head: curr = curr.next curr.next = node node.next = self.head def remove(self, node): if not self.head: return if self.head == node: if self.head.next == self.head: self.head = None else: curr = self.head while curr.next != self.head: curr = curr.next curr.next = self.head.next self.head = self.head.next else: prev = self.head curr = self.head.next while curr != self.head: if curr == node: prev.next = curr.next break prev = curr curr = curr.next def josephus(n, m): lst = CircularLinkedList() for i in range(1, n + 1): lst.add(i) count = 1 curr = lst.head while lst.head and lst.head.next != lst.head: if count == m: print(curr.value, end=' ') next_node = curr.next lst.remove(curr) curr = next_node count = 1 else: curr = curr.next count += 1 for node in lst.head, lst.head.next: print(node.value, end=' ')

这段代码实现了约瑟夫问题（Josephus Problem），其中 CircularLinkedList 是一个循环链表，add() 方法用于向链表中添加元素，remove() 方法用于删除指定的节点，josephus() 方法则用于解决约瑟夫问题，并返回最后留下的元素。

具体来说，假设有 n 个人围成一圈，从第一个人开始报数，报到 m 的人出圈，接着从出圈的下一个人开始重新报数，再次报到 m 的人出圈，直到剩下最后一个人为止。该问题的解法就是遍历循环链表，每次找到报数为 m 的节点，将其从链表中删除，直到链表中只剩下一个或者两个节点。最后输出剩下节点的值即可。

一个缓存结构需要实现如下功能。 set(key, value)：将记录(key, value)插入该结构 get(key)：返回key对应的value值 但是缓存结构中最多放K条记录，如果新的第K+1...

实现一个缓存结构可以使用哈希表和双向链表的组合来实现。哈希表用于快速查询key是否存在以及对应的value值，而双向链表用于维护缓存数据的顺序。

具体实现方法如下：

1. 定义一个双向链表节点类，包含key、value、前驱节点和后继节点四个属性。

2. 定义一个哈希表，用于存储每个key对应的节点。

3. 定义一个双向链表，用于维护缓存数据的顺序。链表头表示最近使用的缓存，链表尾表示最久未使用的缓存。

4. 实现set(key, value)方法。当插入一个新的记录时，首先判断是否已经存在该key值，如果存在则更新value值，否则新建一个节点，并将其插入到哈希表和双向链表的头部。如果缓存已满，需要删除最久未使用的缓存，即链表尾部的节点，并从哈希表中删除该节点对应的key值。

5. 实现get(key)方法。当查询一个记录时，首先在哈希表中查找是否存在该key值，如果存在，则将该节点移动到链表头部，并返回对应的value值。如果不存在，则返回-1或抛出异常等错误提示。

代码实现如下：

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.move_to_head(node)
        return node.value

    def set(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_head(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self.add_to_head(node)
            if len(self.cache) > self.capacity:
                node = self.remove_tail()
                del self.cache[node.key]

    def add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def move_to_head(self, node):
        self.remove_node(node)
        self.add_to_head(node)

    def remove_tail(self):
        node = self.tail.prev
        self.remove_node(node)
        return node

在上述代码中，LRUCache类实现了一个缓存结构，使用双向链表和哈希表实现了set和get两个方法。其中，add_to_head方法将一个节点插入到链表头部，remove_node方法删除一个节点，move_to_head方法将一个节点移动到链表头部，remove_tail方法删除链表尾部的节点。在set方法中，当缓存已满时，使用remove_tail方法删除最久未使用的节点，并从哈希表中删除该节点对应的key值。