用面向对象实现Linkedlist链表
单向链表实现append、iternodes
双向链表实现append、pop、insert、remove、iternodes
单向链表与双向链表
单向链表：
就好比小朋友在操场上，手拉着手。
分为数据域和指针域，指针域指向下一个数据，代码中分别用val 和next 表示。
整个链表用一个容器来存储，因为单向链表的数据虽然真正在内存中是散落的，但是某种关系可以把这些数据有序的组织起来，所以最合适的数据结构应该是列表。列表存储还支持追加和索引，容器在代码中用self.nodes=[] 表示。
如图：内存中的数据散落存储，5表示头head，9表示tail尾。
在链表为空时，需要定义头和尾，来表示前一个数据和下一个数据，头和尾在代码中用head 和tail 分别表示，前一个数据和下一个数据用prev 和next 分别表示。
0）链表数据为空时，顺序是：head --> tail，头和尾都可以用None表示；
1）链表中有一个数据时，顺序就变成了： head--> 数据1 -->tail；
2）链表有两个数据时，顺序变成了：head -->数据1 -->数据2 -->tail；
3）链表有三个数据时，顺序变成了：head -->数据1 -->数据2 -->数据3 -->tail
以此类推。。。
代码：
class SingleNode:
"""代表一个节点"""
def __init__(self, val, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
def __repr__(self):
return str(self.val)
def __str__(self):
return str(self.val)
class LinkedList:
"""容器类,某种方式存储一个个节点"""
def __init__(self):
self.nodes = []
# 不需要插入的列表来说，检索方便，但是insert、remove不合适
self.head = None
self.tail = None
def __len__(self):
return len(self.nodes)
def __getitem__(self, item):
return self.nodes[item]
def append(self, val):
node = SingleNode(val) # 实例化的一个新节点
prev = self.tail
if prev is None:
self.head = node
else:
prev.next = node
self.nodes.append(val)
self.tail = node
def iternodes(self, reverse=False):
current = self.head
while current:
yield current
current = current.next
ll = LinkedList()
ll.append(5)
ll.append(7)
for node in ll.iternodes():
print(node)
print(ll[0])
print(ll[1])
双向链表：
0) append 尾部追加
1) pop 尾部弹出
2) insert 头部插入、中间插入、尾部插入
3) remove 头部删除、中间删除、尾部删除
class SingleNode:
def __init__(self,val,next=None,prev=None):
self.val = val
self.next = next
self.prev = prev
def __repr__(self):
return str(self.val)
def __str__(self):
return str(self.val)
class LinkedList:
def __init__(self):
# self.nodes = []
self.head = None
self.tail = None
def append(self,val):
node = SingleNode(val)
# prev = self.tail
# if prev is None:
if self.head is None: #only one
self.head = node
else: # >1
self.tail.next = node
node.prev = self.tail
# self.nodes.append(node)
self.tail = node
def iternodes(self,reverse=False):
current = self.tail if reverse else self.head
while current:
yield current
current = current.prev if reverse else current.next
def pop(self):
if self.tail is None: #0个数据
raise Exception('Empty')
tail = self.tail
prev = tail.prev
# next = tail.next #尾的下一个恒定为None
if prev is None: # =0, =1
self.head = None
self.tail = None
else: # >1
self.tail = prev
prev.next = None
return tail.val
def getitem(self,index): #index不考虑传入str类型，全当做int类型
if index < 0:
return None
current = None
for i,node in enumerate(self.iternodes()):
if i == index:
current = node
break
if current is not None:
return current
def insert(self,index,val):
if index < 0: #不考虑负索引
raise Exception('Error')
current = None
for i, node in enumerate(self.iternodes()):
if i == index:
current = node
break
if current is None: #考虑元素为空、为一个
self.append(val)
return
#尾部、头部、中间追加
prev = current.prev
next = current.next
node = SingleNode(val)
if prev is None: #头部插入
self.head = node
# node.next = current
# current.prev = node
else:
node.prev = prev
# node.next = current #和前面条件共同部分抽出来放后面
# current.prev = node
prev.next = node
node.next = current
current.prev = node
def remove(self,index):
if self.tail is None:
raise Exception('Empty')
if index < 0:
raise ValueError('Wrong Index {}'.format(index))
current = None
for i,node in enumerate(self.iternodes()):
if i == index:
current = node
break
if current is None: #Not found
raise ValueError('Wrong Index {}. Out of boundary'.format(index))
prev = current.prev
next = current.next
if prev is None and next is None: #only one node
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
del current
# def __getitem__(self, item):
# return self.nodes[item]
ll = LinkedList()
ll.append('abc')
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
ll.append('def')
ll.insert(6,6) #边界
ll.insert(7,7) #尾部
ll.insert(8,8) #尾部
ll.insert(0,123) #头部
ll.insert(100,100) #超界
# ll.remove(100)
# ll.pop()
# ll.pop()
for node in ll.iternodes(False): #False
print(node)
print('~'*30)
# print(ll[0])
# print(ll[1])
ll.remove(5)
ll.remove(6)
ll.remove(0)
ll.remove(1)
for node in ll.iternodes(False): #False
print(node)