数据结构之单链表

单链表(Singly Linked List)是一种基本的线性数据结构,它由一系列节点(Node)组成,每个节点包含两部分:

  1. 数据域(Data):存储数据的部分。
  2. 指针域(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. 单链表的插入操作

  1. 在头部插入节点:插入一个新节点到链表的头部,头指针指向新节点。
def insert_at_head(head, val):
    new_node = ListNode(val)
    new_node.next = head
    return new_node  # 返回新的头节点
  1. 在尾部插入节点:插入一个新节点到链表的尾部。
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
  1. 在指定位置插入节点:在链表的任意位置插入一个节点。
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. 单链表的删除操作

  1. 删除头节点:删除链表的第一个节点,更新头指针。
def delete_head(head):
    if head is None:
        return None  # 链表为空,返回空
    return head.next  # 返回新的头节点
  1. 删除指定节点:删除链表中某个位置的节点。
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. 查找操作

  1. 查找指定值的节点:遍历链表,查找值为 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. 单链表的优缺点

优点

  1. 动态大小:与数组相比,链表的大小是动态变化的,可以根据需要随时增加或删除节点。
  2. 插入删除操作效率高:在链表的头部或中间插入删除节点时,时间复杂度为 O(1),不需要移动大量元素。
  3. 内存利用率高:节点分散存储,内存利用率较高。

缺点

  1. 随机访问效率低:由于链表是线性结构,要访问链表中的某个节点需要从头遍历到目标节点,时间复杂度为 O(n)。
  2. 额外的空间开销:每个节点除了存储数据,还需要额外的指针域,占用更多的内存。
  3. 不支持反向遍历:单链表只能从头到尾顺序访问,无法进行反向遍历。

4. 单链表的应用

单链表作为基本的数据结构,在很多场景中都有广泛的应用:

  1. 实现队列和栈:通过单链表可以实现队列(FIFO)和栈(LIFO)等数据结构。
  2. 内存管理:操作系统中常用链表来实现动态内存分配和管理。
  3. 图的邻接表表示:图的邻接表可以通过链表来实现,用于表示图中的每一个节点和它的邻接节点。
  4. LRU 缓存:通过链表实现 LRU(Least Recently Used)缓存,可以高效地进行插入、删除和查找操作。

5. 总结

单链表作为一种基础的数据结构,具有插入和删除高效的特点,特别适用于需要动态变化数据的场景。尽管其随机访问效率较低,但它在很多实际应用中仍然占据重要地位。掌握单链表的基本操作和应用是学习其他复杂数据结构的基础。