Python数据结构（链表）

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,node=None):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,node=Node):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(self，item): #头插法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