菊花链（Daisy Chain）是一种数据结构，通常用于实现链式数据结构，如链表、队列、栈等。在菊花链中，每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。这种结构使得数据可以在链表中高效地插入和删除。
以下是菊花链的一些关键概念和操作：
关键概念
- 节点（Node）：链表的每个元素，包含数据和两个指针（前驱和后继）。
- 头节点（Head）：链表的第一个节点。
- 尾节点（Tail）：链表的最后一个节点。
操作
-
创建节点（Create Node）：
python class Node: def __init__(self, data): self.data = data self.prev = None self.next = None -
插入节点（Insert Node）：
- 在链表头部插入节点：
python def insert_at_head(head, data): new_node = Node(data) if head is None: return new_node new_node.next = head head.prev = new_node return new_node -
在链表尾部插入节点：
python def insert_at_tail(head, data): new_node = Node(data) if head is None: return new_node current = head while current.next is not None: current = current.next current.next = new_node new_node.prev = current return head -
删除节点（Delete Node）：
- 删除链表头部节点：
python def delete_from_head(head): if head is None: return None data = head.data if head.next is not None: head.next.prev = None else: head = None return data - 删除链表尾部节点：
python def delete_from_tail(head): if head is None: return None current = head while current.next is not None: current = current.next if current.prev is not None: current.prev.next = None else: head = None return data
示例
以下是一个简单的菊花链实现示例：
```python class Node: def init(self, data): self.data = data self.prev = None self.next = None
class DaisyChain: def init(self): self.head = None self.tail = None
def insert_at_head(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_tail(self, data):
new_node = Node(data)
if self.tail is None:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def delete_from_head(self):
if self.head is None:
return None
data = self.head.data
if self.head.next is not None:
self.head.next.prev = None
else:
self.head = None
return data
def delete_from_tail(self):
if self.tail is None:
return None
data = self.tail.data
if self.tail.prev is not None:
self.tail.prev.next = None
else:
self.tail = None
return data
示例使用
daisy_chain = DaisyChain() daisy_chain.insert_at_head(1) daisy_chain.insert_at_tail(2) daisy_chain.insert_at_tail(3) print(daisy_chain.delete_from_head()) # 输出: 1 print(daisy_chain.delete_from_tail()) # 输出: 3 ```
这个示例展示了如何在菊花链中插入和删除节点。通过这种方式，可以高效地在链表的头部和尾部进行操作。
