单链表的遍历方式和应用场景

# 1. **引言**

链表数据结构在计算机科学中扮演着重要的角色，它是一种经典的线性数据结构，与数组不同的是，链表并不需要一块连续的内存空间来存储数据，而是通过指针将节点连接起来。相比之下，链表的插入和删除操作更为灵活高效。在实际应用中，链表常用于实现树、图等更复杂的数据结构，也被广泛应用于算法和面试题中。

与数组相比，链表的访问效率较低且不支持随机访问，但链表的插入和删除操作更为方便。在内存分配方面，链表可以动态增长，不受固定大小限制。因此，选择何种数据结构取决于具体需求，链表只是众多数据结构中的一种选择。

# 2. 单链表的基本操作

#### 2.1 创建单链表

在进行链表操作之前，首先需要创建单链表。常见的方式包括头插法和尾插法。

##### 2.1.1 头插法

头插法是指每次插入新节点都将其插入到链表的头部。这样可以保证新节点成为链表的第一个节点，实现时需要注意指针的变换。

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

def create_linked_list_head(arr):
    dummy = Node()
    for val in arr:
        new_node = Node(val)
        new_node.next = dummy.next
        dummy.next = new_node
    return dummy.next

##### 2.1.2 尾插法

尾插法是指每次插入新节点都将其插入到链表的尾部。这样可以保证新节点成为链表的最后一个节点，实现时需要找到链表的尾节点。

def create_linked_list_tail(arr):
    dummy = Node()
    tail = dummy
    for val in arr:
        new_node = Node(val)
        tail.next = new_node
        tail = new_node
    return dummy.next

#### 2.2 插入节点

在单链表中插入节点是常见的操作，包括在头部插入、尾部插入和指定位置插入。

##### 2.2.1 在头部插入

在链表头部插入节点时，需要考虑头节点的更新操作。

def insert_at_head(head, val):
    new_node = Node(val)
    new_node.next = head
    return new_node

##### 2.2.2 在尾部插入

在链表尾部插入节点时，需要找到尾节点进行插入操作。

def insert_at_tail(head, val):
    if not head:
        return Node(val)
    cur = head
    while cur.next:
        cur = cur.next
    cur.next = Node(val)
    return head

##### 2.2.3 在指定位置插入

在指定位置插入节点时，需要找到插入位置的前一个节点进行插入操作。

def insert_at_position(head, pos, val):
    if pos == 0:
        new_node = Node(val)
        new_node.next = head
        return new_node
    cur = head
    for _ in range(pos - 1):
        cur = cur.next
    new_node = Node(val)
    new_node.next = cur.next
    cur.next = new_node
    return head

#### 2.3 删除节点

单链表中的节点删除操作有删除头节点、尾节点和指定节点。

##### 2.3.1 删除头节点

删除链表头节点时，只需将头指针指向下一个节点即可。

def delete_at_head(head):
    if not head:
        return None
    return head.next

##### 2.3.2 删除尾节点

删除链表尾节点时，需要找到尾节点的前一个节点进行删除操作。

def delete_at_tail(head):
    if not head or not head.next:
        return