用面向对象实现LinkedList链表

单向链表实现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)