用python写链表的基本功能
时间: 2023-05-29 11:04:27 浏览: 46
链表是一种常见的数据结构,它由若干个节点组成,每个节点包含数据和指向下一个节点的指针。链表的基本功能包括插入、删除、查找和遍历。
下面是一个用Python实现链表的代码示例:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def delete(self, data):
if self.head is None:
return
if self.head.data == data:
self.head = self.head.next
return
current_node = self.head
while current_node.next:
if current_node.next.data == data:
current_node.next = current_node.next.next
return
current_node = current_node.next
def search(self, data):
current_node = self.head
while current_node:
if current_node.data == data:
return True
current_node = current_node.next
return False
def traverse(self):
current_node = self.head
while current_node:
print(current_node.data, end=' ')
current_node = current_node.next
```
在这个实现中,我们定义了两个类,一个是Node类表示链表中的节点,另一个是LinkedList类表示整个链表。Node类包含了节点的数据和指向下一个节点的指针,LinkedList类则包含了链表的头节点和基本功能的实现。
在insert方法中,我们遍历链表找到最后一个节点,然后将新节点插入到最后一个节点的后面。在delete方法中,我们先判断链表是否为空,然后遍历链表寻找要删除的节点,将指针指向下一个节点即可。在search方法中,我们遍历链表寻找要查找的数据,如果找到了就返回True,否则返回False。在traverse方法中,我们遍历整个链表并输出每个节点的数据。
使用这个链表实现,我们可以进行一些基本的操作:
```python
# 创建一个新的链表
linked_list = LinkedList()
# 插入节点
linked_list.insert(3)
linked_list.insert(4)
linked_list.insert(5)
# 遍历链表
linked_list.traverse() # 输出: 3 4 5
# 查找节点
print(linked_list.search(4)) # 输出: True
print(linked_list.search(6)) # 输出: False
# 删除节点
linked_list.delete(4)
linked_list.traverse() # 输出: 3 5
```