链表的基础操作1. 数组与字符串的局限性先前的字符串和数组列表两种结构它们的元素按照一定的顺序排列可以通过索引来访问数组中的元素和字符串中的字符。缺点固定大小超出预设大小就需要整体复制到新的内存空间内存连续导致内存碎片化造成空间浪费数据类型固定只能存储相同类型的数据2. 链表的概念链表链表的元素存储可以是不连续的每个数据元素除了存储本身的信息还存储下一个元素的地址指针。第一个节点的存储位置被称为头节点head通过next指针找到下一个节点直到找到最后一个节点最后一个节点的next指针指向NonePython 中表示空指针面向对象编程基础1. 面向对象概念如何在计算机世界表示人首先抽象成一个类Person包括姓名、性别、年龄属性和吃饭的方法如果想表示具体的某一个人需要创建类的实例对象2. 类的定义Class 类类的命名要使用大驼峰形式如MyName在类的代码块中可以定义变量和函数类中定义的变量会成为所有实例的属性所有实例都可以访问这些变量类中定义的函数被称为方法类的所有实例也可以访问这些方法classPerson:# 类中定义一个变量 name会成为所有实例的公共属性nameTom# 类中定义函数称之为方法方法也可以通过该类的实例来访问defsay_hello(self):print(Hello)# 创建 Person 的实例person1Person()person2Person()# 实例可以调用属性person1.nameJerryperson2.nameMike# 实例可以调用方法person1.say_hello()person2.say_hello()3. 类的特殊方法类中的方法被调用时Python 会自动传递一个参数通常命名为self__init__方法用于初始化实例属性避免属性值被固定Python 类的基本结构class类名:# 公共属性# __init__ 方法def__init__(self,其他参数):# 初始化代码# 其他方法defmethod_1(self,其他参数):# 方法实现链表的实现1. 定义链表节点# 1. 定义链表节点类classNode:# __init__ 方法初始化属性def__init__(self,data):self.datadata# 存储节点的数据self.nextNone# next 指针初始化为 None2. 定义链表类# 2. 定义链表类用于容纳链表节点classLinkList:def__init__(self):# 链表头节点初始化为 Noneself.head_nodeNone# 链表长度初始化为 0self.length0链表的插入操作1. 尾部插入append / addLast目的把一个新的数据节点按顺序挂到整个链表的最后面。步骤维护长度链表长度 1创建新节点初始化值为 data判断是否为第一个节点情况 A如果链表是空的头节点为空把新节点设为头节点情况 B如果链表不为空找到当前的尾节点将尾节点的next指向新节点新节点成为新的尾节点classLinkList:def__init__(self):self.head_nodeNoneself.length0# 尾部插入方法definsert(self,data):self.length1# 链表长度加 1new_nodeNode(data)# 创建新节点ifself.head_nodeisNone:# 如果链表为空self.head_nodenew_node# 新节点成为头节点returnself.head_node# 如果链表不为空找到尾节点current_nodeself.head_nodewhilecurrent_node.nextisnotNone:current_nodecurrent_node.next# 将新节点连接到链表尾部current_node.nextnew_nodereturnnew_node# 返回插入的节点完整的链表程序# 链表节点类classNode:定义链表节点类用于创建具体的节点对象def__init__(self,data):# 初始化方法创建节点时调用如 Node(5)self.datadata self.nextNoneclassLinkList:单向链表实现def__init__(self):# 刚创建的链表是空的里面一个节点都没有self.head_nodeNoneself.length0# 初始化链表长度为 0definsert(self,data):在链表尾部插入新节点self.length1new_nodeNode(data)ifself.head_nodeisNone:# 空链表self.head_nodenew_nodereturnself.head_node# 非空链表找到尾节点current_nodeself.head_nodewhilecurrent_node.nextisnotNone:current_nodecurrent_node.nextcurrent_node.nextnew_nodereturnnew_nodedefprint_link_list(self):打印链表内容current_nodeself.head_node# 从头节点开始遍历whilecurrent_nodeisnotNone:ifcurrent_node.nextisnotNone:print(current_node.data,end → )else:print(current_node.data)# 最后一个节点current_nodecurrent_node.next# 主程序if__name____main__:whileTrue:try:nint(input(请输入节点个数: ))elementslist(map(int,input(请输入节点数据空格分隔: ).split()))except:breaklink_listLinkList()fordatainelements:link_list.insert(data)print(链表内容: ,end)link_list.print_link_list()总结链表 vs 数组链表解决了数组的固定大小和连续内存问题面向对象通过类和对象来组织代码提高代码复用性和可维护性链表实现包含节点类和链表类支持基本的插入和遍历操作核心操作尾部插入是链表最基本的操作之一需要正确处理空链表和非空链表的情况