线性表–链表的建立和遍历
时间: 2024-09-29 12:03:12 浏览: 18
线性表中的链表是一种数据结构,它由一系列节点组成,每个节点包含两个部分:存储数据的元素值和指向下一个节点的指针。链表的建立通常分为两步:
1. **创建节点**:首先,需要创建一个节点类,包含数据域用于存储数据以及一个或多个链接字段(通常是next或prev),用于连接到其他节点。
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None # 或者 prev,取决于单向还是双向链表
```
2. **构建链表**:然后通过一个个节点的链接将它们串联起来。可以手动逐个添加新节点,也可以从头开始初始化一个空链表。
```python
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`实现无限循环遍历。