上一篇文章為:→3.1.1單向鏈表
單向循環(huán)鏈表
單鏈表的一個變形是單向循環(huán)鏈表市咽，鏈表中最后一個節(jié)點的next域不再為None袖外，而是指向鏈表的頭節(jié)點。
day24_鏈表-01.png
操作
- is_empty() 判斷鏈表是否為空
- length() 返回鏈表的長度
- travel() 遍歷
- add(item) 在頭部添加一個節(jié)點
- append(item) 在尾部添加一個節(jié)點
- insert(pos, item) 在指定位置pos添加節(jié)點
- remove(item) 刪除一個節(jié)點
- search(item) 查找節(jié)點是否存在
實現(xiàn)
class Node(object):
"""節(jié)點"""
def __init__(self, item):
self.item = item
self.next = None
class SinCycLinkedlist(object):
"""單向循環(huán)鏈表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判斷鏈表是否為空"""
return self._head == None
def length(self):
"""返回鏈表的長度"""
# 如果鏈表為空魂务，返回長度0
if self.is_empty():
return 0
count = 1
cur = self._head
while cur.next != self._head:
count += 1
cur = cur.next
return count
def travel(self):
"""遍歷鏈表"""
if self.is_empty():
return
cur = self._head
print cur.item,
while cur.next != self._head:
cur = cur.next
print cur.item,
print ""
def add(self, item):
"""頭部添加節(jié)點"""
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
#添加的節(jié)點指向_head
node.next = self._head
# 移到鏈表尾部曼验，將尾部節(jié)點的next指向node
cur = self._head
while cur.next != self._head:
cur = cur.next
cur.next = node
#_head指向添加node的
self._head = node
def append(self, item):
"""尾部添加節(jié)點"""
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
# 移到鏈表尾部
cur = self._head
while cur.next != self._head:
cur = cur.next
# 將尾節(jié)點指向node
cur.next = node
# 將node指向頭節(jié)點_head
node.next = self._head
def insert(self, pos, item):
"""在指定位置添加節(jié)點"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
cur = self._head
count = 0
# 移動到指定位置的前一個位置
while count < (pos-1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
"""刪除一個節(jié)點"""
# 若鏈表為空，則直接返回
if self.is_empty():
return
# 將cur指向頭節(jié)點
cur = self._head
pre = None
# 若頭節(jié)點的元素就是要查找的元素item
if cur.item == item:
# 如果鏈表不止一個節(jié)點
if cur.next != self._head:
# 先找到尾節(jié)點粘姜，將尾節(jié)點的next指向第二個節(jié)點
while cur.next != self._head:
cur = cur.next
# cur指向了尾節(jié)點
cur.next = self._head.next
self._head = self._head.next
else:
# 鏈表只有一個節(jié)點
self._head = None
else:
pre = self._head
# 第一個節(jié)點不是要刪除的
while cur.next != self._head:
# 找到了要刪除的元素
if cur.item == item:
# 刪除
pre.next = cur.next
return
else:
pre = cur
cur = cur.next
# cur 指向尾節(jié)點
if cur.item == item:
# 尾部刪除
pre.next = cur.next
def search(self, item):
"""查找節(jié)點是否存在"""
if self.is_empty():
return False
cur = self._head
if cur.item == item:
return True
while cur.next != self._head:
cur = cur.next
if cur.item == item:
return True
return False
if __name__ == "__main__":
ll = SinCycLinkedlist()
ll.add(1)
ll.add(2)
ll.append(3)
ll.insert(2, 4)
ll.insert(4, 5)
ll.insert(0, 6)
print "length:",ll.length()
ll.travel()
print ll.search(3)
print ll.search(7)
ll.remove(1)
print "length:",ll.length()
ll.travel()
