一、链表

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

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 = dataself.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.__headcount = 0while current != None:count += 1current = current.nextreturn count

2.5、遍历链表 

    def travel(self):# 遍历链表并打印每个节点的数据current = self.__headwhile 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.__headself.__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.__headcount = 0while count < pos - 1:count += 1pre = pre.nextnew_node.next = pre.next  # 将新节点的next指向当前节点的nextpre.next = new_node  # 将前一个节点的next指向新节点

2.4.3、尾节点

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

 

2.5、删除节点

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

2.6、查找节点

    def serch(self, data):# 查找链表中是否存在指定数据current = self.__headwhile current != None:if current.data == data:return True  # 找到数据，返回Trueelse:current = current.nextreturn False  # 遍历完成未找到数据，返回False

三、链表的特点

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

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

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

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

四、单向链表的缺点

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

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

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

举个例子:

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

五、完整代码 

class Node:def __init__(self, data):# 初始化节点，包含数据和指向下一个节点的指针self.data = dataself.next = Noneclass LinkList:def __init__(self, node=None):# 初始化链表，头指针指向第一个节点（默认为None）self.__head = nodedef is_empty(self):# 检查链表是否为空return self.__head == Nonedef length(self):# 计算链表的长度current = self.__headcount = 0while current != None:count += 1current = current.nextreturn countdef travel(self):# 遍历链表并打印每个节点的数据current = self.__headwhile current != None:print(current.data)current = current.nextdef add(self, data):# 在链表头部添加新节点new_node = Node(data)new_node.next = self.__headself.__head = new_nodedef append(self, data):# 在链表尾部添加新节点new_node = Node(data)if self.is_empty():self.__head = new_nodeelse:current = self.__headwhile current.next != None:current = current.nextcurrent.next = new_nodedef 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.__headcount = 0while count < pos - 1:count += 1pre = pre.nextnew_node.next = pre.next  # 将新节点的next指向当前节点的nextpre.next = new_node  # 将前一个节点的next指向新节点def remove(self, data):# 移除链表中指定数据的节点current = self.__headpre = Nonewhile current != None:if current.data == data:if current == self.__head:self.__head = current.next  # 如果是头节点，更新头指针else:pre.next = current.next  # 将前一个节点的next指向当前节点的nextbreakelse:pre = currentcurrent = current.nextdef serch(self, data):# 查找链表中是否存在指定数据current = self.__headwhile current != None:if current.data == data:return True  # 找到数据，返回Trueelse:current = current.nextreturn False  # 遍历完成未找到数据，返回Falseif __name__ == '__main__':linklist = LinkList()linklist.add(10)  # 添加节点10linklist.add(20)  # 添加节点20linklist.append(100)  # 在尾部添加节点100linklist.add(30)  # 添加节点30linklist.add(40)  # 添加节点40print(linklist.is_empty())  # 检查链表是否为空print(linklist.length())  # 输出链表长度print('*****************')linklist.remove(30)  # 移除节点30# linklist.travel()  # 遍历链表并打印节点数据print(linklist.serch(40))  # 查找节点40是否存在# linklist.travel()  # 遍历链表并打印节点数据

六、思维导图