单向链表实现append、iternodes方法
双向链表实现append、pop、insert、remove、iternodes方法
链表的好处：
查询慢、插入追加删除快
思路：
# 单向链表 1 2 2 3 3 4 4 5 5 6 None 最基本的链表结构
# 链表由 每一个数据块组成 串联在一起就是链表
#先定义数据块 Node
class Node1: ##(item -> next)
def __init__(self,item, next=None):
self.item = item
self.next = next
def __repr__(self):
return '<{}--->{}>'.format(self.item,
self.next.item if self.next else 'None') #？？？怎么理解这句话
#构造单向链表
class Singelinked:
def __init__(self): #设定开头和结尾 这是一个链表最基本的属性 初始链表的开头和结尾为None
self.head = None
self.tail = None
def append(self,item):
Node = Node1(item) ##构造一个要添加的节点 然后写入到链表中
if self.head is None: #
self.head = Node ##如果是空的直接追加
self.tail = Node
else:
self.tail.next = Node #不为空 就在最后一个尾部 追加 然后追加完成后 把前一个的next 变成 node
self.tail = Node
return self
def iterlink(self):
current = self.head #当前的头部
while current: #无限循环 知道 当前为None 等效False
yield current
current = current.next
双向链表的结构： 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
##先定义数据块 Node
class Node2: ##(item -> next)
def __init__(self,item, next= None,prev=None): ##双向链表除了头和尾之外都是双向的
self.prev = prev
self.item = item
self.next = next
def __repr__(self):
return '<{}<--{}-->{}>'.format(self.prev.item if self.prev else 'None',self.item,self.next.item if self.next else 'None')
#构造双向链表
class DubleLineked:
def __init__(self):
self.head = None
self.tail = None
self.size = None
def append(self,item):
Node = Node2(item) ##构造一个要添加的节点 然后写入到链表中
if self.head is None:
self.head = Node ##如果是空的直接追加
#self.tail = Node
else:
Node.prev = self.tail
self.tail.next = Node
self.tail = Node
return self
def insert(self,index,value):
if index < 0 : #只接受正索引
raise IndexError('Negative index err{}'.format(index))
current = None
for i,node in enumerate(self.iterlink()):
if i == index:
current = node
break
else:
self.append(value)
return ########################## if使用后记得用return 终止函数执行
##创建一个待加入节点对象； 如果是空 或者超界的情况 则直接执行append语句 append有包装的语句
node = Node2(value) #包装成模块
prev = current.prev
# next = current.next
## 放在头 考虑修正关系 切记 修改后要修改头部 为不加入不用考虑 因为append 就是尾部和空的加入
if index == 0 : # 除了空和尾部追加 就是 头部 和中部了 分开讨论一下就ok了 i==0 or prev = None
current.prev = node
node.next = current
self.head = node
else:#中部追加
node.prev = prev
node.next = current
current.prev = node
prev.next = node
return
def pop(self): #尾部移除
if self.tail is None: #考虑空链表
raise Exception('{}'.format(None))
else:
node = self.tail #取模块
item = node.item # item 是模块内的data
prev = node.prev #模块的前一项
if prev is None and next is None: #只有一个node
self.head = None
self.tail = None
return item #返回一个数值
else:##两个元素移除尾部 最后剩下一个
self.tail = prev ##node.prev
prev.next = None
return item #返回一个数值
def remove(self,index): #任意位置移除 比较index
if index < 0 :
raise IndexError("Do not support nagative index {}".format(index))
if self.head is None or self.tail is None:
raise Exception('Empty')
for i,node in enumerate(self.iterlink()):
if i == index:
current = node
break
else: ##超出索引范围 移除最后一个
self.pop() #抛出最后一个
return ##记得终止函数执行@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
#raise IndexError('超出索引边界') 两个都可以
###break 说明找到了要索引的值 这时候就要对这个值进行操作了
prev = current.prev
next = current.next
item = current.item
#分4情况
#就一个模块 既是头 有事尾
#在开头
#在结尾
#在中间
if prev is None and next is None: #JUEST ONE
self.head = None
self.tail = None
elif prev is None: ##不是一个元素的链表,头部移除 修正头部
self.head = next ##更改头部
next.prev = None # 头部指针置空
elif next is None: ##不是一个元素的链表，说明尾部移除 修正尾部
self.tail = prev
prev.next = None
else: #不是一个元素 且是中间移除 不用修正头和尾
prev.next = next
next.prev = prev
def iterlink(self,reversed = False): #双向迭代就是翻转的问题 想sorted函数
current = self.head if not reversed else self.tail
while current:
yield current
current = current.next if not reversed else current.prev
#输出结果测试
a = DubleLineked()
a.append(1)
a.append(2)
a.append(3)
a.insert(100,'abd')
a.insert(0,112)
a.insert(3,'liajibin')
a.pop()
print(a.pop())
a.remove(1)
for x in a.iterlink():
print(x)
