双向循环链表实现与扩展
链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。双向循环链表是链表的一种特殊形式，它不仅包含指向下一个节点的指针，还包含指向上一个节点的指针，并且链表的最后一个节点的指针指向第一个节点，形成一个循环。这种结构使得在链表中的任何位置插入或删除节点都变得非常灵活。
本文将围绕双向循环链表的数据结构，介绍其基本实现，并探讨一些扩展应用。
双向循环链表的基本实现
定义节点结构
我们需要定义链表的节点结构。每个节点包含数据部分和两个指针，分别指向前一个节点和后一个节点。
python
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
创建双向循环链表
接下来，我们创建一个双向循环链表类，它包含插入、删除、遍历等基本操作。
python
class DoublyCircularLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
new_node.next = new_node
new_node.prev = new_node
else:
tail = self.head.prev
tail.next = new_node
new_node.prev = tail
new_node.next = self.head
self.head.prev = new_node
def delete(self, node):
if node is None or self.head is None:
return
if node == self.head:
if self.head.next == self.head:
self.head = None
else:
self.head = self.head.next
self.head.prev = tail
tail.next = self.head
else:
node.prev.next = node.next
node.next.prev = node.prev
def display(self):
if self.head is None:
return
current = self.head
while True:
print(current.data, end=' ')
current = current.next
if current == self.head:
break
测试双向循环链表
python
dll = DoublyCircularLinkedList()
dll.insert(1)
dll.insert(2)
dll.insert(3)
dll.display() 输出: 1 2 3
dll.delete(dll.head.next)
dll.display() 输出: 1 3
双向循环链表的扩展应用
1. 实现栈和队列
双向循环链表可以用来实现栈和队列。以下是使用双向循环链表实现的栈和队列的代码示例。
python
class Stack:
def __init__(self):
self.dll = DoublyCircularLinkedList()
def push(self, data):
self.dll.insert(data)
def pop(self):
if self.dll.head is None:
return None
return self.dll.delete(self.dll.head)
def peek(self):
if self.dll.head is None:
return None
return self.dll.head.data
class Queue:
def __init__(self):
self.dll = DoublyCircularLinkedList()
def enqueue(self, data):
self.dll.insert(data)
def dequeue(self):
if self.dll.head is None:
return None
return self.dll.delete(self.dll.head)
2. 实现双向循环链表的排序
我们可以使用双向循环链表来实现排序算法，如归并排序。以下是使用归并排序对双向循环链表进行排序的代码示例。
python
def merge_sort(dll):
if dll.head is None or dll.head.next == dll.head:
return dll
middle = get_middle(dll.head)
next_to_middle = middle.next
middle.next = dll.head
dll.head.prev = middle
next_to_middle.prev = dll.head
left = DoublyCircularLinkedList()
left.head = dll.head
left.tail = middle
right = DoublyCircularLinkedList()
right.head = next_to_middle
right.tail = dll.tail
left = merge_sort(left)
right = merge_sort(right)
sorted_dll = DoublyCircularLinkedList()
sorted_dll = merge(left, right)
return sorted_dll
def get_middle(node):
if node is None:
return node
slow = node
fast = node
while fast.next != node and fast.next.next != node:
slow = slow.next
fast = fast.next.next
return slow
def merge(left, right):
if left.head is None:
return right
if right.head is None:
return left
if left.head.data <= right.head.data:
temp = left.head
left.head = left.head.next
left.tail.next = merge(left, right)
left.tail = right.tail
else:
temp = right.head
right.head = right.head.next
right.tail.next = merge(left, right)
right.tail = left.tail
return temp
3. 实现双向循环链表的查找
我们可以使用双向循环链表来实现查找算法，如二分查找。以下是使用二分查找在双向循环链表中查找元素的代码示例。
python
def binary_search(dll, target):
if dll.head is None:
return False
left = dll.head
right = dll.tail
while left != right and left.prev != right:
mid = left
for _ in range((right - left) // 2):
mid = mid.next
if mid.data == target:
return True
elif mid.data < target:
left = mid.next
else:
right = mid.prev
return False
总结
双向循环链表是一种灵活且强大的数据结构，它不仅可以用于实现基本的数据操作，还可以扩展到其他应用，如栈、队列、排序和查找等。我们了解了双向循环链表的基本实现和扩展应用，希望对您有所帮助。
Comments NOTHING