1-1 单链表基本操作
时间: 2023-11-10 15:07:06 浏览: 50
单链表是一种常用的数据结构,它由一系列节点组成,每个节点由一个数据元素和一个指向下一个节点的指针组成。
单链表的基本操作包括:
1. 创建一个空链表
2. 在链表头部插入一个节点
3. 在链表尾部插入一个节点
4. 在指定位置插入一个节点
5. 删除链表中的指定节点
6. 查找链表中的指定节点
7. 获取链表的长度
8. 遍历链表并输出元素
下面是单链表的基本操作的示例代码:
```python
# 定义单链表节点类
class ListNode:
def __init__(self, data):
self.data = data
self.next = None
# 定义单链表类
class LinkedList:
def __init__(self):
self.head = None
# 在链表头部插入一个节点
def insert_at_head(self, data):
new_node = ListNode(data)
if not self.head:
self.head = new_node
else:
new_node.next = self.head
self.head = new_node
# 在链表尾部插入一个节点
def insert_at_tail(self, data):
new_node = ListNode(data)
if not self.head:
self.head = new_node
else:
cur = self.head
while cur.next:
cur = cur.next
cur.next = new_node
# 在指定位置插入一个节点
def insert_at_position(self, data, position):
if position <= 0 or not self.head:
self.insert_at_head(data)
else:
new_node = ListNode(data)
cur = self.head
for _ in range(position-1):
if not cur.next:
break
cur = cur.next
new_node.next = cur.next
cur.next = new_node
# 删除链表中的指定节点
def delete_node(self, data):
if not self.head:
return
if self.head.data == data:
self.head = self.head.next
else:
cur = self.head
while cur.next:
if cur.next.data == data:
cur.next = cur.next.next
break
cur = cur.next
# 查找链表中的指定节点
def find_node(self, data):
cur = self.head
while cur:
if cur.data == data:
return True
cur = cur.next
return False
# 获取链表的长度
def get_length(self):
count = 0
cur = self.head
while cur:
count += 1
cur = cur.next
return count
# 遍历链表并输出元素
def traverse(self):
cur = self.head
while cur:
print(cur.data, end=' ')
cur = cur.next
print()
# 创建一个空链表
linked_list = LinkedList()
# 在链表头部插入节点
linked_list.insert_at_head(1)
linked_list.insert_at_head(2)
linked_list.insert_at_head(3)
# 在链表尾部插入节点
linked_list.insert_at_tail(4)
linked_list.insert_at_tail(5)
# 在指定位置插入节点
linked_list.insert_at_position(6, 2)
# 删除节点
linked_list.delete_node(3)
# 查找节点
is_found = linked_list.find_node(4)
print(is_found)
# 获取链表长度
length = linked_list.get_length()
print(length)
# 遍历链表并输出元素
linked_list.traverse()
```