线性表 链表结构遍历

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

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

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

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

相关问题

线性表–链表的建立和遍历

线性表中的链表是一种数据结构，它由一系列节点组成，每个节点包含两个部分：存储数据的元素值和指向下一个节点的指针。链表的建立通常分为两步：

1. **创建节点**：首先，需要创建一个节点类，包含数据域用于存储数据以及一个或多个链接字段（通常是next或prev），用于连接到其他节点。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None   # 或者 prev，取决于单向还是双向链表

2. **构建链表**：然后通过一个个节点的链接将它们串联起来。可以手动逐个添加新节点，也可以从头开始初始化一个空链表。

def create_list():
    head = Node(data_0)
    current = head
    for data in [data_1, data_2, ...]:
        new_node = Node(data)
        current.next = new_node
        current = new_node
    return head

对于遍历链表，有多种方法，常见的有：

- **顺序遍历**（也称为前序遍历）：从头节点开始，依次访问每个节点直到链表结束。
- ```python
while current is not None:
print(current.data)
current = current.next

- **反向遍历**：从尾部开始往头部走，如果链表是双向链表，则更方便。
- **循环遍历**：在Python的内置列表（linked list实现）中，可以使用`itertools.islice`配合`enumerate`实现无限循环遍历。