Python线性表种的单链表详解

Python线性表中的单链表详解

什么是单链表？

单链表是数据结构中最基本的链式存储结构，它通过每个节点中的指针指向下一个节点，实现了数据的连续储存。

单链表的实现

定义一个节点

单链表的每个节点需要记录两个信息：data 和 next，其中 data 表示节点中实际存储的数据，next 则代表下一个节点的地址。我们可以使用 class 来定义一个节点：

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

在定义一个节点时，需要注意两点：

1. 每个节点都要有一个 data 域，用来存储具体的数据；
2. 定义节点的 next 时，要将其初始化为 None，也就是指向一个空节点。

定义一个单链表

定义了节点之后，就可以定义单链表了。单链表需要记录两个信息：head 和 size，其中 head 代表链表中第一个节点的地址，size 表示链表的长度。

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

在定义链表时，需要注意两点：

1. 初始时，链表为空，因此链表的 head 为 None；
2. 初始时，链表的长度为 0。

单链表的基本操作

单链表作为一种数据结构，需要支持一些基本操作，包括：在链表的末尾添加一个元素、在链表的指定位置添加一个元素、获取链表的长度、获取链表中指定位置的元素等。下面将分别对这些操作进行说明。

在链表的末尾添加一个元素

在链表的末尾添加一个元素，是单链表最基本、最常用的操作之一。具体过程如下：

1. 对于空链表，将新节点作为链表的 head；
2. 对于非空链表，找到链表的尾节点，将新节点作为它的下一个节点；

    def add_last(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = new_node
        self.size += 1

在链表的指定位置添加一个元素

在链表的指定位置添加一个元素，需要找到这个元素的前一个元素位置，然后将新节点插入到其后边。如果插入位置为链表的头部，直接用新节点替换头节点即可。具体过程如下：

    def insert(self, index, data):
        if index < 0 or index > self.size:
            raise IndexError("索引越界")
        new_node = Node(data)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            cur = self.head
            for i in range(index-1):
                cur = cur.next
            new_node.next = cur.next
            cur.next = new_node
        self.size += 1

获取链表长度

链表的长度即为链表节点数，可以用 size 记录。代码如下：

    def get_size(self):
        return self.size

获取链表中指定位置的元素

从链表头部开始往后查找，直到找到目标节点。代码如下：

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("索引越界")
        cur = self.head
        for i in range(index):
            cur = cur.next
        return cur.data

示例

示例一：在单链表的尾部添加元素

linked_list = LinkedList()
linked_list.add_last(1)
linked_list.add_last(2)
linked_list.add_last(3)
assert linked_list.get_size() == 3
assert linked_list.get(0) == 1
assert linked_list.get(1) == 2
assert linked_list.get(2) == 3

在该示例中，我们定义了一个单链表，并在其末尾依次添加了三个元素，然后验证了链表的长度以及元素是否正确插入。

示例二：在单链表的指定位置添加元素

linked_list = LinkedList()
linked_list.add_last(1)
linked_list.add_last(3)
linked_list.insert(1, 2)
assert linked_list.get_size() == 3
assert linked_list.get(0) == 1
assert linked_list.get(1) == 2
assert linked_list.get(2) == 3

在该示例中，我们定义了一个单链表，并在其末尾依次添加了两个元素，然后在其第二个位置插入了一个值为 2 的元素，最后验证了链表的长度以及元素是否正确插入。