建立双向链表,并在双向链表上实现插入、删除和查找操作
时间: 2024-04-23 18:03:43 浏览: 133
双向链表是一种常见的数据结构,它可以在 O(1) 时间内实现插入和删除操作,并且可以双向遍历链表。
以下是一个简单的双向链表的实现,包括插入、删除和查找操作:
```python
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
cur_node = self.head
while cur_node.next is not None:
cur_node = cur_node.next
cur_node.next = new_node
new_node.prev = cur_node
def delete(self, data):
cur_node = self.head
while cur_node is not None:
if cur_node.data == data:
if cur_node.prev is not None:
cur_node.prev.next = cur_node.next
else:
self.head = cur_node.next
if cur_node.next is not None:
cur_node.next.prev = cur_node.prev
return
else:
cur_node = cur_node.next
def find(self, data):
cur_node = self.head
while cur_node is not None:
if cur_node.data == data:
return True
else:
cur_node = cur_node.next
return False
```
在上面的代码中,我们定义了一个 `Node` 类来表示双向链表中的节点,包括节点存储的数据、前驱节点和后继节点。然后,我们定义了 `DoublyLinkedList` 类来表示双向链表。在 `DoublyLinkedList` 类中,我们实现了插入、删除和查找操作。
在 `insert` 方法中,我们首先创建一个新节点,并将其插入到链表的末尾。如果链表为空,则将新节点作为头节点。否则,我们遍历整个链表,直到找到链表的最后一个节点,然后将新节点插入到链表的末尾。
在 `delete` 方法中,我们遍历整个链表,查找要删除的节点。如果找到了该节点,则将其从链表中删除。如果要删除的节点是头节点,则将头指针指向下一个节点。否则,我们将前驱节点的 `next` 指针指向要删除节点的后继节点,将后继节点的 `prev` 指针指向要删除节点的前驱节点。
在 `find` 方法中,我们遍历整个链表,查找存储指定数据的节点。如果找到了这个节点,则返回 True,否则返回 False。
在使用双向链表时,我们需要注意以下几点:
- 双向链表有两个指针,因此需要更多的内存来存储它们。
- 在插入和删除节点时,需要更新前驱节点和后继节点的指针。
- 双向链表可以双向遍历,因此可以从前往后或从后往前遍历链表。
- 如果双向链表只有一个指针指向头节点,则可以将其视为单向链表。
阅读全文