Python----数据结构（单链表：节点，是否为空，长度，遍历，添加，删除，查找）

一、链表

        链表是一种线性数据结构，由一系列按特定顺序排列的节点组成，这些节点通过指针相互连接。每个节点包含两部分：元素和指向下一个节点的指针。其中，最简单的形式是单向链表，每个节点含有一个信息域和一个指针域，该指针指向链表中的下一个节点，最后一个节点则指向一个空值。

1.1、Python中的链表

•        大部分都是用C语言实现链表，因为C有指针，可以很方便的控制内存，很轻易就可以实现链 表，在C/C++中，通常采用“指针+结构体”来实现链表。

•        Python是一门动态语言，可以直接把对象赋值给新的变量，我们采用“引用+类”来实现 链表。

•        结构：data为自定义的数据，next为下一个节点的地址。

•        链表的种类：单向链表、双向链表、单向循环链表、双向循环链表。 

1.2、基本元素

节点：每个节点有两个部分，左边称为值域，存放用户数据；右边部分称为指针域，用来存 放指向下一个元素的指针。

Head：head节点永远指向第一个节点。

Tail：tail节点永远指向最后一个节点。

None：链表中最后一个节点的指针域为None。

二、基本操作

2.1、节点的创建 class Node: def __init__(self, data): # 初始化节点，包含数据和指向下一个节点的指针 self.data = data self.next = None

2.2、初始化单向链表 class LinkList: def __init__(self, node=None): # 初始化链表，头指针指向第一个节点（默认为None） self.__head = node 2.3、判断是否为空 def is_empty(self): # 检查链表是否为空 return self.__head == None 2.4、链表长度 def length(self): # 计算链表的长度 current = self.__head count = 0 while current != None: count += 1 current = current.next return count 2.5、遍历链表  def travel(self): # 遍历链表并打印每个节点的数据 current = self.__head while current != None: print(current.data) current = current.next 2.4、插入节点 2.4.1、头节点 def add(self, data): # 在链表头部添加新节点 new_node = Node(data) new_node.next = self.__head self.__head = new_node

2.4.2、中间节点 def insert(self, pos, data): # 在指定位置插入新节点 if pos > self.length() - 1: self.append(data) # 如果位置超出范围，添加到尾部 elif pos <= 0: self.add(data) # 如果位置小于等于0，添加到头部 else: new_node = Node(data) pre = self.__head count = 0 while count < pos - 1: count += 1 pre = pre.next new_node.next = pre.next # 将新节点的next指向当前节点的next pre.next = new_node # 将前一个节点的next指向新节点

2.4.3、尾节点 def append(self, data): # 在链表尾部添加新节点 new_node = Node(data) if self.is_empty(): self.__head = new_node else: current = self.__head while current.next != None: current = current.next current.next = new_node

 

2.5、删除节点 def remove(self, data): # 移除链表中指定数据的节点 current = self.__head pre = None while current != None: if current.data == data: if current == self.__head: self.__head = current.next # 如果是头节点，更新头指针 else: pre.next = current.next # 将前一个节点的next指向当前节点的next break else: pre = current current = current.next

2.6、查找节点 def serch(self, data): # 查找链表中是否存在指定数据 current = self.__head while current != None: if current.data == data: return True # 找到数据，返回True else: current = current.next return False # 遍历完成未找到数据，返回False 三、链表的特点

1、动态数据集合：链表允许动态的添加和删除元素，这使得它们在处理未知数量或频繁变 化的数据集时非常有用。

2、元素顺序：链表可以按照插入顺序来保持元素的顺序，这对于需要维护元素插入顺序的 应用程序非常有用。

3、 内存效率：与数组相比，链表在内存使用上更为高效，因为它们不需要连续的内存空间。 链表通过节点之间的指针来连接元素，这样可以更有效地利用内存空间。

4、避免数组扩容：数组在初始化时需要指定大小，如果超出大小，则需要扩容，这是一个 昂贵的操作。链表则可以避免这个问题，因为它们可以动态地增长。

四、单向链表的缺点

1、只能从头遍历到尾或者从尾遍历到头(一般从头到尾)。

2、链表相连的过程是单向的。实现的原理是上一个链表中有一个指向下一个的引用。

3、 我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的。但是, 在实际开发中, 经 常会遇到需要回到上一个节点的情况。

举个例子:

        假设一个文本编辑用链表来存储文本。每一行用一个String对象存储在链表的 一个节点中。当编辑器用户向下移动光标时, 链表直接操作到下一个节点即可。但是当用 于将光标向上移动呢? 这个时候为了回到上一个节点, 我们可能需要从头开始, 依次走到 想要的节点上。

五、完整代码  class Node: def __init__(self, data): # 初始化节点，包含数据和指向下一个节点的指针 self.data = data self.next = None class LinkList: def __init__(self, node=None): # 初始化链表，头指针指向第一个节点（默认为None） self.__head = node def is_empty(self): # 检查链表是否为空 return self.__head == None def length(self): # 计算链表的长度 current = self.__head count = 0 while current != None: count += 1 current = current.next return count def travel(self): # 遍历链表并打印每个节点的数据 current = self.__head while current != None: print(current.data) current = current.next def add(self, data): # 在链表头部添加新节点 new_node = Node(data) new_node.next = self.__head self.__head = new_node def append(self, data): # 在链表尾部添加新节点 new_node = Node(data) if self.is_empty(): self.__head = new_node else: current = self.__head while current.next != None: current = current.next current.next = new_node def insert(self, pos, data): # 在指定位置插入新节点 if pos > self.length() - 1: self.append(data) # 如果位置超出范围，添加到尾部 elif pos <= 0: self.add(data) # 如果位置小于等于0，添加到头部 else: new_node = Node(data) pre = self.__head count = 0 while count < pos - 1: count += 1 pre = pre.next new_node.next = pre.next # 将新节点的next指向当前节点的next pre.next = new_node # 将前一个节点的next指向新节点 def remove(self, data): # 移除链表中指定数据的节点 current = self.__head pre = None while current != None: if current.data == data: if current == self.__head: self.__head = current.next # 如果是头节点，更新头指针 else: pre.next = current.next # 将前一个节点的next指向当前节点的next break else: pre = current current = current.next def serch(self, data): # 查找链表中是否存在指定数据 current = self.__head while current != None: if current.data == data: return True # 找到数据，返回True else: current = current.next return False # 遍历完成未找到数据，返回False if __name__ == '__main__': linklist = LinkList() linklist.add(10) # 添加节点10 linklist.add(20) # 添加节点20 linklist.append(100) # 在尾部添加节点100 linklist.add(30) # 添加节点30 linklist.add(40) # 添加节点40 print(linklist.is_empty()) # 检查链表是否为空 print(linklist.length()) # 输出链表长度 print('*****************') linklist.remove(30) # 移除节点30 # linklist.travel() # 遍历链表并打印节点数据 print(linklist.serch(40)) # 查找节点40是否存在 # linklist.travel() # 遍历链表并打印节点数据 六、思维导图