数据结构之单链表
单链表（Singly Linked List）是一种基本的线性数据结构，它由一系列节点（Node）组成，每个节点包含两部分：
- 数据域（Data）：存储数据的部分。
- 指针域（Next）：指向链表中下一个节点的指针。
1. 单链表的基本概念
单链表是一种动态数据结构，它的特点是每个节点包含一个指针，指向下一个节点。链表的第一个节点称为头节点，最后一个节点指向 null，表示链表的结束。
单链表的结构图
头节点 -> 节点1 -> 节点2 -> 节点3 -> ... -> 节点n -> null
- 头节点：链表的第一个节点，它是我们访问链表的入口。
- 尾节点：链表的最后一个节点，它的
next指针指向null。
2. 单链表的基本操作
单链表常见的操作包括：
- 插入操作：在链表的指定位置插入节点。
- 删除操作：删除链表中的指定节点。
- 查找操作：查找链表中的某个节点。
- 遍历操作：遍历链表中的所有节点。
2.1. 节点结构的定义
首先，我们需要定义一个节点结构体（Node），包含数据域和指针域：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val # 数据域
self.next = next # 指针域
2.2. 单链表的插入操作
- 在头部插入节点：插入一个新节点到链表的头部，头指针指向新节点。
def insert_at_head(head, val):
new_node = ListNode(val)
new_node.next = head
return new_node # 返回新的头节点
- 在尾部插入节点：插入一个新节点到链表的尾部。
def insert_at_tail(head, val):
new_node = ListNode(val)
if not head: # 链表为空，直接将新节点作为头节点
return new_node
current = head
while current.next:
current = current.next
current.next = new_node # 将尾节点的指针指向新节点
return head
- 在指定位置插入节点：在链表的任意位置插入一个节点。
def insert_at_position(head, val, position):
new_node = ListNode(val)
if position == 0: # 在头部插入
new_node.next = head
return new_node
current = head
count = 0
while current and count < position - 1:
current = current.next
count += 1
if current is None: # 如果位置超过链表长度，返回原链表
return head
new_node.next = current.next
current.next = new_node
return head
2.3. 单链表的删除操作
- 删除头节点：删除链表的第一个节点，更新头指针。
def delete_head(head):
if head is None:
return None # 链表为空，返回空
return head.next # 返回新的头节点
- 删除指定节点：删除链表中某个位置的节点。
def delete_at_position(head, position):
if position == 0: # 删除头节点
return delete_head(head)
current = head
count = 0
while current and count < position - 1:
current = current.next
count += 1
if current is None or current.next is None: # 如果位置不合法
return head
current.next = current.next.next # 删除指定位置的节点
return head
2.4. 查找操作
- 查找指定值的节点：遍历链表，查找值为
val的节点。
def find_node(head, val):
current = head
while current:
if current.val == val:
return current
current = current.next
return None # 如果没有找到，返回 None
2.5. 遍历操作
遍历整个链表，打印每个节点的值。
def print_linked_list(head):
current = head
while current:
print(current.val, end=" -> ")
current = current.next
print("None")
3. 单链表的优缺点
优点
- 动态大小：与数组相比，链表的大小是动态变化的，可以根据需要随时增加或删除节点。
- 插入删除操作效率高：在链表的头部或中间插入删除节点时，时间复杂度为 O(1)，不需要移动大量元素。
- 内存利用率高：节点分散存储，内存利用率较高。
缺点
- 随机访问效率低：由于链表是线性结构，要访问链表中的某个节点需要从头遍历到目标节点，时间复杂度为 O(n)。
- 额外的空间开销：每个节点除了存储数据，还需要额外的指针域，占用更多的内存。
- 不支持反向遍历：单链表只能从头到尾顺序访问，无法进行反向遍历。
4. 单链表的应用
单链表作为基本的数据结构，在很多场景中都有广泛的应用：
- 实现队列和栈：通过单链表可以实现队列（FIFO）和栈（LIFO）等数据结构。
- 内存管理：操作系统中常用链表来实现动态内存分配和管理。
- 图的邻接表表示：图的邻接表可以通过链表来实现，用于表示图中的每一个节点和它的邻接节点。
- LRU 缓存：通过链表实现 LRU（Least Recently Used）缓存，可以高效地进行插入、删除和查找操作。
5. 总结
单链表作为一种基础的数据结构，具有插入和删除高效的特点，特别适用于需要动态变化数据的场景。尽管其随机访问效率较低，但它在很多实际应用中仍然占据重要地位。掌握单链表的基本操作和应用是学习其他复杂数据结构的基础。
发表回复