Python数据结构之链表详解( 二 ) _链表

def __str__(self):return str(self.data)2. 单链表的实现通常，“链表”是指单链表，单链表由许多结点组成，其中每个结点都有只有一个指向直接后继的 next 指针，链表中最后一个节点的链接为 None，表示链表结束。访问数据元素只能由链表头依次到链表尾，而不能做逆向访问，这是一种最简单的链表。而其它链表类型(包括双向链表、循环链表等)将在之后小节中进行讲解。
单链表分为带头结点和不带头结点两种类型。因为链表中的第一个结点没有直接前驱，它的地址需要放在链表的头指针变量中；而其它结点的地址放入直接前驱结点的指针域中。在链表中插入和删除结点时，对第一个结点和其它结点的处理是不同的。因此为了操作方便，就在链表的头部加入一个“头结点”，其指针域中存放第一个数据结点的地址，头指针变量中存放头结点的地址。下图 (a) 中表示不带头结点的链表，其头指针 linked_list 指向第一个数据结点，而图 (b) 中表示不带头结点的链表头指针 linked_list 指向头结点，头结点的指针域指向第一个数据结点：

文章插图

Note：在接下来的实现的单链表基本操作中，若不特别说明，采用带有头结点的链表。
2.1 单链表的初始化【Python数据结构之链表详解】单链表表的初始化建立一个空的带头结点的单链表，其表长 length 初始化为 0，此时链表中没有元素结点，只有一个头结点，其指针域为空：

class SinglyLinkedList:def __init__(self):self.length = 0# 初始化头结点head_node = Node()# 头指针指向头结点self.head = head_node

创建单链表 SinglyLinkedList 对象的时间复杂度为O(1) 。
2.2 获取单链表长度由于我们在链表中使用 length 跟踪链表中的项数，因此求取单链表长度只需要重载 len 从对象返回 length 的值，因此时间复杂度为O(1)：
def __len__(self):return self.length2.3 读取指定位置元素为了实现读取链表指定位置元素的操作，我们将重载 getitem 操作。我们已经知道单链表中的结点只能顺序存取，即访问前一个结点后才能接着访问后一个结点。因此要访问单链表中第i个元素值，必须从头指针开始遍历链表，依次访问每个结点，直到访问到第i个结点为止。因此操作的复杂度为O(n) 。同时，我们希望确保索引在可接受的索引范围内，否则将引发 IndexError 异常：

def __getitem__(self, index):if index > self.length - 1 or index < 0:raise IndexError("SinglyLinkedList assignment index out of range")else:count = -1current = self.headwhile count < index:current = current.nextcount += 1return current.data

我们也可以实现修改指定位置元素的操作，只需要重载 setitem 操作，其复杂度同样为O(n)：

def __setitem__(self, index, value):if index > self.length - 1 or index < 0:raise IndexError("SinglyLinkedList assignment index out of range")else:count = -1current = self.headwhile count < index:current = current.nextcount += 1current.data = https://www.isolves.com/it/cxkf/yy/Python/2022-07-29/value

2.4 查找指定元素当查找指定元素时，需要设置一个跟踪链表结点的指针 current，初始时 current 指向链表中的第一个数据结点，然后顺着 next 域依次指向每个结点，每指向一个结点就判断其值是否等于指定值 value，若是则返回该结点索引；否则继续往后搜索，如果链表中无此元素，则引发 ValueError 异常，其时间复杂度为O(n)：

def locate(self, value):count = -1current = self.headwhile current != None and current.data != value:count += 1current = current.nextif current and current.data =https://www.isolves.com/it/cxkf/yy/Python/2022-07-29/= value:return countelse:raise ValueError("{} is not in sequential list".format(value))

2.5 在指定位置插入新元素单链表结点的插入只需要修改结点指针域的值，使其指向新的链接位置，而无需移动任何元素。例如我们要在链表中索引为 i ii 处插入一个新结点，必须首先找到所插位置的前一个结点 i − 1 i-1i−1，再进行插入，设指针 previous 指向待插位置的前驱结点，指针 current 指向插入前链表中索引为 i ii 的结点，同时也是待插位置的后继结点，指针 new_node 指向待插新结点，插入操作过程如下所示：