网站如何加入流量统计,域客士营销型单页网站程,网站建设学什么语言编辑好,php mysql网站开发书Python数据结构#xff08;链表#xff09;
单向链表
单向链表也叫单链表#xff0c;是链表中最简单的一种形式#xff0c;它的每个节点包含两个域#xff0c;一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点#xff0c;而最后一个节点的链接域则指向…Python数据结构链表
单向链表
单向链表也叫单链表是链表中最简单的一种形式它的每个节点包含两个域一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点而最后一个节点的链接域则指向一个空值。 表元素域elem用来存放具体的数据 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置从p出发能找到表中的任意节点
节点实现
class node(object):def __init__(self,item):# __item存放的是数据元素self.item item# __next是下一个节点的表示self.next None单链表的操作
class node(object):def __init__(self,item):# __item存放的是数据元素self.item item# __next是下一个节点的表示self.next Noneclass SingleLinkList(object):def __init__(self,nodeNone):self.head node # 定义头节点默认值为Nodedef is_empty(): #链表是否为空return self.head None:def length(): #链表长度cur self.head #cur游标表当前的节点用来移动遍历节点count 0while cur ! None:count 1cur cur.nextreturn countdef travel(): #遍历整个链表cur self.headwhile cur ! None:print(cur.item, end )cur cur.nextprint()def get_all(self):#查找整个链表数据cur self.headres []while True:#遍历整个链表,并转成列表形式if cur.next None:if cur.item:res.append(cur.item)breakelse:if cur.item:res.append(cur.item)cur cur.nextreturn resdef reverse_printing(self):res self.get_all()#获取列表形式所有链表数据ret res[::-1]#反转列表return retdef reverse(self):#反转链表res self.reverse_printing()#获取逆序的列表形式链表sign1 self.head#创建游标while True:#遍历整个链表,断开各连接,没有指向的数据会被垃圾回收if sign1.next None:breaksign2 sign1.nextsign1.next Nonesign1 sign2sign self.headfor ele in res:#根据逆序列表形式链表,重新构建链表body Item(ele)sign.next bodysign sign.nextdef ReverseList(self): #反转链表 cur self.head pre None while cur: nextNode cur.next cur.next pre pre cur cur nextNode return pre def add(item): #链表头部添加元素,头插法node Node(item)node.next self.headself.head nodedef append(item): #链表尾部添加元素尾插法node Node(item)if self.is_empty():self.head nodeelse:cur self.headwhile cur.next ! None:cur cur.nextcur.next nodedef insert(pos,item): #指定位置添加元素if pos 0:self.add(item)elif pos (self.length()-1):self.append(item)else:pre self.headcount 0while count (pos-1):count 1pre pre.next# 当循环退出后pre指向pos-1的位置node Node(item)node.next pre.nextpre.next nodedef remove(item): #删除节点# 双指针cur self.headpre Nonewhile cur ! None:if cur.item item:# 先判断此节点是否为头结点if cur self.head:self.head cur.nextelse:pre.next cur.nextbreakelse:pre curcur cur.next# 单指针pre self.headwhile pre ! None:if pre.next.item item:if pre self.head:self.head pre.nextelse:pre.next pre.next.nextbreakelse:pre pre.nexdef search(item): #查找节点是否存在cur self.headwhile cur ! None:if cur.item item:return Trueelse:cur cur.nextreturn False链表与顺序表的对比
链表失去了顺序表随机读取的优点同时链表由于增加了结点的指针域空间开销比较大但对存储空间的使用要相对灵活。 链表与顺序表的各种操作复杂度如下所示:
操作链表顺序表访问元素O(n)O(1)在头部插入/删除O(1)O(n)在尾部插入/删除O(n)O(1)在中间插入/删除O(n)O(n)
注意虽然表面看起来复杂度都是 O(n)但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找删除和插入操作本身的复杂度是O(1)。顺序表查找很快主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作只能通过拷贝和覆盖的方法进行。
单向循环链表
单链表的一个变形是单向循环链表链表中最后一个节点的next域不再为None而是指向链表的头节点 操作
class Node(object):def __init__(self,item):self.item itemself.next Node
class SingleCycleLinkList(object): #单向循环链表def __init__(self,nodeNode):self.head node# 定义头节点if node:node.next nodedef is_empty(self): #判空return self.head Nonedef length(self): #链表长度if self.is_empty():return 0cur self.headcount 1while cur.next ! self.head:count 1cur cur.nextreturn countdef travel(self): #遍历链表if self.is_empty():returncur self.headwhile cur.next ! self.next:print(cur.item, end - )cur cur.nextprint(cur.item) #尾节点不能进入循环所以要出循环后打印出来def add(selfitem): #头插法node Node(item)if self.is_empty():self.head nodenode.next nodeelse:cur self.headwhile cur.next ! self.head:cur cur.next#退出循环后cur指向尾节点node.next self.headself.head nodecur.next self.head #cur.next nodedef append(self,item): #尾插法node Node(item)if self.is_empty():self.head nodenode.next nodeelse:cur self.headwhile cur.next ! self.head:cur cur.nextnode.next self.headcur.next nodedef insert(self,pos,item): #在指定位置插入元素if pos 0:self.add(item)elif pos (self.length()-1):self.append(item)else:pre self.headcount 0while count (pos-1):count 1pre pre.nextnode Node(item)node.next pre.nextpre.next nodedef remove(self,item): #删除节点cur self.headpre Nonewhile cur.next ! self.head:if cur.item item#判断此节点是否为头结点if cur sef.head:#删除是头结点的情况先找到尾节点rear self.headwhile rear.next ! self.head:rear rear.nextself.head cur.nextrear.next self.headelse:#中间节点pre.next cur.nextreturnelse:pre curcur cur.next#退出循环cur指向尾节点 if cur.item item:if cur self.head:#链表只有一个节点的情况self.head Noneelse:pre.next cur.nextdef search(self,item): #查找节点if self.is_empty():return Falsecur self.headwhile cur.next self.head:if cur.item item:return Trueelse:cur cur.next#退出循环cur指向尾节点if cur.item item:return Truereturn False
双向链表
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点当此节点为第一个节点时指向空值而另一个指向下一个节点当此节点为最后一个节点时指向空值。 操作
class Node(object): #应为前几个方法与单链表都一样用面向对象的思想可以把单链表中的类继承过来双链表的节点def __init__(self, item):self.item itemself.next Noneself.prev Nonedef is_empty(): #链表是否为空return self.head None:def length(): #链表长度cur self.head #cur游标表当前的节点用来移动遍历节点count 0while cur ! None:count 1cur cur.nextreturn countdef travel(): #遍历整个链表cur self.headwhile cur ! None:print(cur.item, end )cur cur.nextprint()def add(item): #链表头部添加元素,头插法node Node(item)node.next self.headself.head.prev nodeself.head nodedef append(item): #链表尾部添加元素尾插法node Node(item)if self.is_empty():self.head nodeelse:cur self.headwhile cur.next ! None:cur cur.nextcur.next nodenode.prev curdef insert(pos,item): #指定位置添加元素if pos 0:self.add(item)elif pos (self.length()-1):self.append(item)else:cur self.headcount 0while count pos:count 1cur cur.next# 当循环退出后cur指向pos的位置node Node(item)node.next curnode.prev cur.prevcur.prev.next nodecur.prev nodedef remove(item): #删除节点cur self.headwhile cur ! None:if cur.item item:if cur self.head:self.head cur.nextif cur.next: #判断链表是否只有一个节点cur.next.prev Noneelse:cur.prev.next cur.nextif cur.next:cur.next.prev cur.prevbreakelse:cur cur.nexdef search(item): #查找节点是否存在cur self.headwhile cur ! None:if cur.item item:return Trueelse:cur cur.nextreturn False
