Python数据结构之链表

一、链表

1、目的

解决顺序表存储数据有上限，并且插入和删除操作效率低的问题。

2、概念

链表：链式存储的线性表，使用随机的物理内存存储逻辑上连续的数据。

链表的组成：由一个个结点组成

结点：由数据域和链接域组成，是链表的基本单位。

数据域：存储数据元素的区域。

链接域：记录下一个结点所在位置的区域。

头结点：虚设的一个节点，链接域专门记录链表第一个节点位置，数据域专门记录链表的长度。

3、链表的种类

单向链表、双向链表、循环链表

二、单向链表

1、单向链表的概念

只能通过头结点或链表的头，单向的访问后继节点的链表叫单向链表

2、节点和链表类的格式

⑴包含存储数据元素的数据域

#封装普通节点的类
class Node:#构造函数 定义节点的属性def __init__(self, value):self.value = value #普通节点的数据域self.next = None #普通节点的链接域 刚构造的节点该位置域为空

⑵有一个存储下一个节点的位置域

#封装链表的类（封装头结点）
class LinkList:#构造函数def __init__(self, node = None):self.size = 0 #头结点的数据域为0 链表的长度为0self.head = node #头结点的链接域指向None

3、单向链表的相关操作（成员函数的封装）

⑴判空

函数功能：判断链表是否有节点（除了头节点）。思路：头结点的链接域指向空，则说明链表为空

函数的返回值：逻辑值（真、假）--->1,0 ---->返回值int

函数名：符合命名规则

参数列表：链表

    #判空def is_empy(self):return self.size == 0 #判断链表长度是否为0#或者判断head是否为None

⑵头插

函数功能：将一个节点以头插的方式插入到头结点的后面。思路：（如上图）

函数名：符合命名规则

参数列表：self 链表、要插入的数据

注意事项：

• 需要申请节点封装数据
• 插入成功，链表长度自增

    #头插def add_head(self, value):#创建一个新的节点node = Node(value)#头插node.next = self.headself.head = node#插入成功 链表长度自增self.size += 1

头插效果

⑶遍历

函数功能：从头到尾打印出链表中每个节点的数据域的数据

函数返回值：无

函数名：符合命名规则

参数列表：self 链表

注意事项：判空

    #遍历def show(self):#判空if self.is_empy():print("该链表为空！")returnelse:q = self.headwhile q:print("%d"%(q.value),end=" ")q = q.next #改变q的指向print()

⑷尾插

函数功能：将新的节点增加到链表的尾部。思路：（如上图）

函数返回值：无

函数名：符合命名规则

参数列表：self 链表，要插入的数据

注意事项：插入成功，链表自增

    #尾插def add_tail(self, value):#可以判空  空的话 直接将head=node#创建一个节点node = Node(value)#找到链表的最后一个节点p = self.headi=1while i<self.size:p=p.nexti+=1#尾插p.next = node#尾插成功 链表长度自增self.size += 1

尾插效果

⑸任意位置插

函数功能：在指定的位置插入一个节点 思路：如上图

函数返回值：无

函数名：符合命名规则

参数列表：self链表、要插入的位置、要插入的数据

注意事项：

• 判断要插入的位置是否合理
• 成功插入 ；链表长度自增
• 如果是第一个位置，做头插

    #任意位置插入数据def add_index(self, index, value):#判断位置是否合理if index<0 or index>self.size+1:print("插入失败")returnelse:p=self.headif index == 0: #当插入的是第一个位置  头插self.add_head(value)else:# 找到要插入位置的前一个节点p = self.headi=1while i<index:p=p.nexti+=1#创建一个新的节点node=Node(value)#插入node.next=p.nextp.next=node#插入成功 链表自增self.size+=1

在5号位插入22

⑹头删

函数功能：删除链表的第一个节点（除头节点）。思路：（如上图）

函数的返回值：逻辑值（真、假）或者 无

函数名：符合命名规则

参数列表：链表、要删除的数据

注意事项：判断链表是否为空

    #头删def del_head(self):#判空if self.is_empy():print("删除失败，该列表手中为空。")returnelse:#确认被删除元素deleted_value = self.head.valueself.head = self.head.nextself.size -= 1#删除成功 长度自减print(f"删除成功，{deleted_value}已被删除！")

头删

⑺尾删

函数功能：删除链表的最后一个节点。思路：（如上图）

函数的返回值：逻辑值（真、假）或者 无

函数名：符合命名规则

参数列表：链表、要删除的数据

注意事项：

• 判断链表是否为空
• 如果链表只有一个节点的情况

    #尾删def del_tail(self):#判空if self.is_empy():print("删除失败，该链表为空！")elif self.size == 1: #当链表只有一个节点时#确认被删除元素deleted_value = self.head.valueself.head = Noneself.size -= 1print(f"删除成功，{deleted_value}已被删除！")else:#找到最后一个节点的前一个节点q = self.headwhile q.next.next:q = q.next#确认被删除元素deleted_value = q.next.value#删除q.next = None #或  q.next = q.next.nextself.size -= 1#删除成功 长度自减print(f"删除成功，{deleted_value}已被删除！")

尾删

⑻任意位置删

函数功能：在指定的位置删除一个节点 思路：（如上图）

函数返回值：逻辑值（真、假）或者 无

函数名：符合命名规则

参数列表：self链表、要删除的位置、要删除的数据

注意事项：

• 判断要删除的位置是否合理
• 成功删除 ；链表长度自减
• 如果是第一个位置，做头删

    #按位置删除def del_at(self, index):#判断位置是否合理if index < 0 or index >= self.size:print("删除失败，位置无效！")elif index == 0:  #当插入的是第一个位置  头删self.del_head()else:# 找到要删除位置的前一个节点p = self.headfor _ in range(index - 1):p = p.next#确认被删除元素deleted_value = p.next.value#删除p.next = None#删除成功 链表自减self.size -= 1print(f"删除成功，{deleted_value}已被删除！")

删除3号位的数据

⑼按位置修改

函数功能：在指定的位置修改一个节点 思路：（如上图）

函数返回值：无

函数名：符合命名规则

参数列表：self 顺序表，要修改的位置、修改的数据

注意事项：

• 判空

• 修改的位置是否合理

    #按位置修改def modify_at(self, index, value):#判断位置是否合理if index < 0 or index >= self.size:print("修改失败，位置无效！")else:# 找到要修改位置的节点p = self.headfor _ in range(index):# 修改p = p.nextp.value = valueprint(f"修改成功，位置{index + 1}的数据修改为{value}。")

把3号位的数据修改为33

⑽按值修改

函数功能：链表按值修改。思路：（如上图）

函数的返回值：逻辑值（真、假） --->int 成功返回1，失败返回0

函数名：符合命名规则

参数列表：self 顺序表、旧值、新值

注意事项：需要判断链表是否合法，链表是否为空，新旧值是否相等

    #按值修改def modify_by_value(self, old_value, new_value):# 找到要修改位置的节点p = self.headfound = Falsewhile p:#寻找旧值if p.value == old_value:#把旧值修改成新值p.value = new_valuefound = Truep = p.nextif found:print(f"修改成功，将值{old_value}修改为{new_value}。")else:print(f"修改失败，值{old_value}未找到。")

把40修改为44

⑾按值查找返回位置

函数功能：链表按值查找返回当前值的位置。思路：（如上图）

函数的返回值：---->int 查找成功返回位置（下标）,查找失败0

函数名：符合命名规则

参数列表：self 顺序表、要查找的元素（数据）

注意事项：需要判断顺序表是否合法，顺序表是否为空

    #按值查找返回位置def find_value(self, value):# 找到要查找位置的节点p = self.headindex = 0while p:#返回值if p.value == value:return index + 1p = p.nextindex += 1return -1

查找30在列表的什么位置

⑿链表的反转：

函数功能：反转单链表的节点顺序，使头尾节点互换。思路：如上图

函数的返回值：无

函数名：符合命名规则

参数列表：self 顺序表

注意事项：

• 空链表或单节点链表反转后与原链表一致，但打印成功消息。
• 反转操作会更改链表结构，不可撤销。

    #链表的反转def reverse(self):#初始化一个临时变量`node`为None，用于存储反转后的链表头node = None#`p`指向链表的当前头节点，遍历过程中会逐步向后移动p = self.headwhile p:#暂存当前节点的下一个节点，用于后续移动next_node = p.next#反转当前节点的指针方向，使其指向反转后的部分p.next = nodenode = pp = next_node#最终更新链表的头节点为反转后的头节点self.head = nodeprint("链表反转成功！")

反转链表

三、链表应用：

1、菜单界面

⑴主菜单

主菜单

⑵添加菜单

添加菜单

⑶删除菜单

删除菜单

⑷修改菜单

修改菜单

2、完整代码

#判断输入是否为整数
def get_int(prompt):while True:try:value = int(input(prompt))return valueexcept ValueError:print("无效输入，请输入一个整数。")#判断输入是否在合理的范围内
def get_valid_int(prompt, min_val, max_val):while True:try:value = int(input(prompt))if min_val <= value <= max_val:return valueelse:print(f"输入不在范围{min_val}-{max_val}之间，请重新输入。")except ValueError:print("无效输入，请输入一个整数。")#判断选择是否合理
def get_choice(prompt, min_val, max_val):while True:try:value = int(input(prompt))if min_val <= value <= max_val:return valueelse:print("无法处理您的指令，请重新输入。")except ValueError:print("无效输入，请输入一个整数。")#封装普通节点的类
class Node:#构造函数 定义节点的属性def __init__(self, value):self.value = value #普通节点的数据域self.next = None #普通节点的链接域 刚构造的节点该位置域为空#封装链表的类（封装头结点）
class LinkList:#构造函数def __init__(self, node = None):self.size = 0 #头结点的数据域为0 链表的长度为0self.head = node #头结点的链接域指向None#判空def is_empy(self):return self.size == 0 #判断链表长度是否为0#或者判断head是否为None#头插def add_head(self, value):#创建一个新的节点node = Node(value)#头插node.next = self.headself.head = node#插入成功 链表长度自增self.size += 1#尾插def add_tail(self, value):#可以判空  空的话 直接将head=node#创建一个节点node = Node(value)#找到链表的最后一个节点p = self.headi=1while i<self.size:p=p.nexti+=1#尾插p.next = node#尾插成功 链表长度自增self.size += 1#任意位置插入数据def add_index(self, index, value):#判断位置是否合理if index<0 or index>self.size+1:print("插入失败")returnelse:p=self.headif index == 0: #当插入的是第一个位置  头插self.add_head(value)else:# 找到要插入位置的前一个节点p = self.headi=1while i<index:p=p.nexti+=1#创建一个新的节点node=Node(value)#插入node.next=p.nextp.next=node#插入成功 链表自增self.size+=1#头删def del_head(self):#判空if self.is_empy():print("删除失败，该列表手中为空。")returnelse:#确认被删除元素deleted_value = self.head.valueself.head = self.head.nextself.size -= 1#删除成功 长度自减print(f"删除成功，{deleted_value}已被删除！")#尾删def del_tail(self):#判空if self.is_empy():print("删除失败，该链表为空！")elif self.size == 1: #当链表只有一个节点时#确认被删除元素deleted_value = self.head.valueself.head = Noneself.size -= 1print(f"删除成功，{deleted_value}已被删除！")else:#找到最后一个节点的前一个节点q = self.headwhile q.next.next:q = q.next#确认被删除元素deleted_value = q.next.value#删除q.next = None #或  q.next = q.next.nextself.size -= 1#删除成功 长度自减print(f"删除成功，{deleted_value}已被删除！")#按位置删除def del_at(self, index):#判断位置是否合理if index < 0 or index >= self.size:print("删除失败，位置无效！")elif index == 0:  #当插入的是第一个位置  头删self.del_head()else:# 找到要删除位置的前一个节点p = self.headfor _ in range(index - 1):p = p.next#确认被删除元素deleted_value = p.next.value#删除p.next = None#删除成功 链表自减self.size -= 1print(f"删除成功，{deleted_value}已被删除！")#按位置修改def modify_at(self, index, value):#判断位置是否合理if index < 0 or index >= self.size:print("修改失败，位置无效！")else:# 找到要修改位置的节点p = self.headfor _ in range(index):# 修改p = p.nextp.value = valueprint(f"修改成功，位置{index + 1}的数据修改为{value}。")#按值修改def modify_by_value(self, old_value, new_value):# 找到要修改位置的节点p = self.headfound = Falsewhile p:#寻找旧值if p.value == old_value:#把旧值修改成新值p.value = new_valuefound = Truep = p.nextif found:print(f"修改成功，将值{old_value}修改为{new_value}。")else:print(f"修改失败，值{old_value}未找到。")#按值查找返回位置def find_value(self, value):# 找到要查找位置的节点p = self.headindex = 0while p:#返回值if p.value == value:return index + 1p = p.nextindex += 1return -1#链表的反转def reverse(self):#初始化一个临时变量`node`为None，用于存储反转后的链表头node = None#`p`指向链表的当前头节点，遍历过程中会逐步向后移动p = self.headwhile p:#暂存当前节点的下一个节点，用于后续移动next_node = p.next#反转当前节点的指针方向，使其指向反转后的部分p.next = nodenode = pp = next_node#最终更新链表的头节点为反转后的头节点self.head = nodeprint("链表反转成功！")#遍历def show(self):#判空if self.is_empy():print("该链表为空！")returnelse:q = self.headwhile q:print("%d"%(q.value),end=" ")q = q.next #改变q的指向print()linkList = LinkList()linkList.add_head(10)
linkList.add_head(20)
linkList.add_head(30)
linkList.add_head(40)
linkList.add_head(50)# 主菜单
while True:print("\n菜单：")print("1. 显示所有数据")print("2. 添加数据")print("3. 删除数据")print("4. 修改数据")print("5. 查找数据")print("6. 链表反转")print("7. 退出")choice = get_choice("请选择操作：", 1, 7)if choice == 1: #显示所有数据linkList.show()elif choice == 2: #显示添加菜单while True:print()print("1. 添加到末尾")print("2. 插入到指定位置")print("3. 返回上一级")add_choice = get_choice("请选择操作：", 1, 3)if add_choice == 1: #添加数据到末尾num = get_int("请输入一个整数：")linkList.add_tail(num)print("数字加入成功。")elif add_choice == 2: #添加数据到指定位置index = get_valid_int(f"请输入插入位置（1-{linkList.size + 1}）：", 1, linkList.size + 1) - 1value = get_int("请输入一个整数：")linkList.add_index(index, value)print("数字加入成功。")elif add_choice == 3: #返回主菜单breakelif choice == 3: #显示删除菜单while True:print()print("1. 删除第一个数据")print("2. 删除最后一个数据")print("3. 按位置删除数据")print("4. 返回上一级")del_choice = get_choice("请选择操作：", 1, 4)if del_choice == 1: #删除第一个数据linkList.del_head()elif del_choice == 2: #删除最后一个数据linkList.del_tail()elif del_choice == 3: #按位置删除数据index = get_valid_int(f"请输入要删除的位置（1-{linkList.size}）：", 1, linkList.size) - 1linkList.del_at(index)elif del_choice == 4: #返回主菜单breakelif choice == 4: #显示修改菜单while True:print()print("1. 按位置修改")print("2. 按值修改")print("3. 返回上一级")sub_choice = get_choice("请选择操作：", 1, 3)if sub_choice == 1: #按位置修改index = get_valid_int(f"请输入修改位置（1-{linkList.size}）：", 1, linkList.size) - 1value = get_int("请输入新的值：")linkList.modify_at(index, value)elif sub_choice == 2: #按值修改old_value = get_int("请输入要修改的原值：")new_value = get_int("请输入新的值：")linkList.modify_by_value(old_value, new_value)elif sub_choice == 3: #返回主菜单breakelif choice == 5: #查找数据value = get_int("请输入要查找的值：")index = linkList.find_value(value)if index != -1:print(f"值{value}位于位置{index}。")else:print(f"值{value}未找到。")elif choice == 6: #反转链表linkList.reverse()elif choice == 7: #退出程序print("程序已退出。")break