线性表 链表结构遍历

线性表是一种基础的数据结构，它由一系列元素组成，并按照特定的顺序排列。链表作为一种特殊的线性表，每个元素被称为节点，每个节点包含两个部分：数据域和指针域。数据域存储实际的数据，指针域指向下一个节点。

链表结构的遍历主要有两种常见的方法：

1. **前序遍历（先头遍历）**：从链表的头部开始，依次访问每一个节点，然后递归地访问下一个节点，直到遍历完整个链表。在Python中，可以使用while循环或递归函数实现。

def preorder_traversal(head):
    if head is not None:
        print(head.data)
        preorder_traversal(head.next)

2. **后序遍历（后尾遍历）**：首先访问链表的所有节点，最后返回到头部并访问。递归版本可能会稍有复杂，因为需要处理空节点的情况。

def postorder_traversal(head):
    if head is not None:
        postorder_traversal(head.next)
        print(head.data)

3. **中序遍历（有序遍历）**：对于排序后的链表，中序遍历会按照升序或降序展示元素。同样，递归法比较常见。

链表的遍历有助于我们对数据进行操作，如查找、插入和删除等。需要注意的是，在链表中没有随机访问的能力，只能通过索引（位置）逐个访问。