Python线性表-单链表

1. 什么是线性表

线性表是计算机科学中常用的一种数据结构，它由一系列节点组成，每个节点包含数据元素与指向下一个节点的引用。线性表中的节点按照一定的顺序排列，每个节点只能有一个直接前驱节点和一个直接后继节点，不存在分叉。线性表可以用来表示一些具有顺序关系的数据集合，比如数字序列、字符串等。

Python中的线性表可以用列表或者链表来实现。

2. 单链表的概念

单链表是一种常见的链表形式，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的引用。单链表的最后一个节点的指针指向空值，表示链表结束。链表的第一个节点通常称为头节点。

2.1 单链表的基本操作

2.1.1 创建单链表

可以通过遍历数据构建一个单链表。下面是一个示例代码：

# 定义单链表节点类
class ListNode:
    def __init__(self, data):
        self.data = data
        self.next = None
# 创建一个单链表
def create_linked_list(data):
    # 头节点
    head = ListNode(None)
    # 当前节点
    current = head
    
    # 遍历数据构建链表
    for item in data:
        current.next = ListNode(item)
        current = current.next
    
    return head.next

在这个示例中，我们定义了一个单链表节点类`ListNode`，包含数据和指向下一个节点的引用。`create_linked_list`函数遍历输入的数据，创建一个单链表。

2.1.2 插入节点

插入节点是指在链表的特定位置上插入一个新的节点。可以在链表的头部、尾部、或指定位置插入节点。

下面是一个在链表头部插入节点的示例代码：

# 在链表头部插入节点
def insert_node_at_head(head, data):
    new_node = ListNode(data)
    new_node.next = head.next
    head.next = new_node
# 调用示例
head = create_linked_list([1, 2, 3])
insert_node_at_head(head, 0)

2.1.3 删除节点

删除节点是指将链表中的某个节点从链表中删除掉。同样可以根据节点在链表中的位置进行删除操作。

下面是一个删除链表尾部节点的示例代码：

# 删除链表尾部节点
def delete_node_at_tail(head):
    current = head
    while current.next.next is not None:
        current = current.next
    current.next = None
# 调用示例
head = create_linked_list([1, 2, 3])
delete_node_at_tail(head)

2.1.4 遍历链表

遍历链表是指按顺序访问链表中的每个节点，并对节点进行操作。可以通过循环遍历的方式实现。

下面是一个遍历链表并打印节点值的示例代码：

# 遍历链表并打印节点值
def traverse_linked_list(head):
    current = head.next
    while current is not None:
        print(current.data)
        current = current.next
# 调用示例
head = create_linked_list([1, 2, 3])
traverse_linked_list(head)

3. 总结

单链表是一种常见的线性表数据结构，它的插入、删除和遍历操作是其最基本的操作。通过以上示例代码，我们可以了解到单链表的基本使用方法及其相关的操作。

使用单链表可以方便地对线性数据进行插入和删除操作，但是由于单链表的节点之间的连接是单向的，如果需要在某个节点之前插入或删除节点，需要遍历到该节点的前驱节点。在一些场景下，单链表的操作会比较复杂和耗时，因此在实际应用中，需要根据具体情况选择合适的数据结构。