了解单链表
单链表是数据结构中最基本的一种,它由一系列结点组成,每个结点包含两个部分:数据和指向下一个结点的指针。单链表的特点是插入和删除操作灵活,但在访问数据时效率较低,因为它不支持随机访问。
单链表的结构
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
单链表的基本操作
- 创建单链表
def create_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for value in values[1:]:
current.next = ListNode(value)
current = current.next
return head
- 遍历单链表
def traverse_list(head):
current = head
while current:
print(current.value, end=' ')
current = current.next
print()
- 查找元素
def search_element(head, value):
current = head
while current:
if current.value == value:
return True
current = current.next
return False
- 插入元素
def insert_element(head, value, position):
new_node = ListNode(value)
if position == 0:
new_node.next = head
return new_node
current = head
for _ in range(position - 1):
if current.next is None:
return None
current = current.next
new_node.next = current.next
current.next = new_node
return head
- 删除元素
def delete_element(head, position):
if position == 0:
return head.next
current = head
for _ in range(position - 1):
if current.next is None:
return None
current = current.next
if current.next is None:
return head
current.next = current.next.next
return head
实际应用案例解析
案例一:实现一个简单的待办事项列表
使用单链表来存储待办事项,可以方便地插入和删除待办事项。
# 省略了 ListNode 类的定义和 create_list 函数的实现
def add_task(head, task):
return insert_element(head, task, 0)
def delete_task(head, task):
return delete_element(head, 0)
案例二:实现一个简单的电话簿
使用单链表来存储电话簿,可以方便地插入和删除联系人信息。
# 省略了 ListNode 类的定义和 create_list 函数的实现
def add_contact(head, name, phone):
return insert_element(head, (name, phone), 0)
def delete_contact(head, name):
for i, (contact_name, _) in enumerate(traverse_list(head)):
if contact_name == name:
return delete_element(head, i)
return None
通过以上案例,我们可以看到单链表在实际应用中的强大之处。掌握单链表,将有助于我们在编程道路上走得更远。
