概念
將單鏈表的終端節(jié)點(diǎn)的指針由原來(lái)的空指針改為指向頭節(jié)點(diǎn), 就是整個(gè)單鏈表形成一個(gè)環(huán), 這種首尾相接的單鏈表稱為單循環(huán)鏈表.
實(shí)現(xiàn)
class Node:
"""
節(jié)點(diǎn)
"""
def __init__(self, value):
self.data = value
self.next = None
class CircularLinkedList:
def __init__(self):
self.rear = None # 尾節(jié)點(diǎn)
def is_empty(self):
return self.rear is None
# def append(self, elem):
# """
# 尾插法
# """
# temp = Node(elem)
# if self.rear is None:
# temp.next = temp
# self.rear = temp
# else:
# temp.next = self.rear.next
# self.rear.next = temp
# self.rear = temp
def prepend(self, elem):
"""
頭插法
"""
temp = Node(elem)
if self.rear is None:
temp.next = temp
self.rear = temp
else:
temp.next = self.rear.next
self.rear.next = temp
def append(self, elem):
"""
尾插法
先將節(jié)點(diǎn)插入頭部,然后尾指針后移
"""
self.prepend(elem)
self.rear = self.rear.next
def print_all(self):
if self.is_empty():
return
p = self.rear.next # 取得頭部節(jié)點(diǎn)
print('Head', end='')
while True:
print('-->', p.data, end='')
if p is self.rear: # 到達(dá)尾部停止
break
p = p.next
print('-->Finish')
def pop(self, index=0):
"""
彈出指定索引的節(jié)點(diǎn), 默認(rèn)頭部節(jié)點(diǎn)
"""
if self.rear is None:
raise IndexError('pop from empty circular linked list.')
p = self.rear
for _ in range(index):
p = p.next
target = p.next
if target is self.rear:
self.rear = None
p.next = target.next
target.next = None
return target.data
def __iter__(self):
if self.rear is None:
return
p = self.rear.next
while p is not self.rear:
yield p.data
p = p.next
yield p.data
