单向循环链表其实就是在单向链表的基础上，让尾节点的下一个节点指向头节点，整个链表形成一个闭环。所以在整体思路上，和单向链表类似，只是在考虑问题时，需要考虑尾部节点指向头部节点的指针。
1.构造单向循环链表
1.1 构造节点
单向循环链表的节点与单向链表相同，因此，这部分的代码没有区别。
class Node(object):
"""节点"""
def __init__(self,item):
self.elem = item
# 创建Node时，还不存在下一个节点,因此默认指定为None
self.next = None
1.2 构造函数
作用：构造头节点
- 思路与单向链表相同
- 传入node时，由于是单向循环链表，因此node的next指针指向自身
class SingleLinklist(object):
"""单链表"""
def __init__(self,node=None):
# 单向循环链表创建头节点后，头节点末尾指向自身
self.__head = None
if node:
node.next = node
1.3 is_empty函数
作用：用于判断链表是否为空
- 思路和代码都与单向链表相同
def is_empty(self):
"""判断是否为空"""
return self.__head == None
1.3 length函数
作用：用于返回链表的长度
- 构建一个cur游标，起使指向头节点的位置，即cur = self.__head
- 创建一个计数器count，用于计算长度
- 单向循环链表的遍历条件为while cur.next != self.__head，由于遍历条件会少算一次【不算尾节点】，因此count需要从1开始计数
- 当cur的next指针所指的不是self.__head时遍历，每遍历一次，count+1，cur移动一个索引位置
def length(self):
"""返回长度"""
if self.is_empty():
return 0
# 建立一个游标，由于对链表进行遍历
# 当count = 0 时，可以解决链表为空的情况
cur = self.__head
# 区别单向链表，此时count需要从1开始
count = 1
while cur.next != self.__head:
count += 1
cur = cur.next
return count
1.4 travel函数
作用：遍历整个链表
- 创建一个cur游标，起使指向头节点的位置，即cur = self.__head
- 当cur的next指针所指的不是self.__head时遍历，打印当前cur所指的元素
-
由于while循环内不会打印尾节点的元素，因此退出循环后，要打印当前cur游标所处的尾节点的元素
【注意】 - 由于单向循环链表的遍历条件，因此都需要考虑链表为空的情况
- 当链表为空时，结束函数
def travel(self):
"""遍历列表"""
# 链表为空时直接结束
if self.is_empty():
return
cur = self.__head
while cur.next != self.__head:
print(cur.elem,end =" ")
cur = cur.next
# 循环退出后cur指向尾节点
# 但尾节点的元素没有打印
print(cur.elem)
1.5 add函数【头插法】
作用：在链表头部添加元素
- 创建cur游标，让其移动到尾节点
- 让node的next针先指向当前的头节点，然后在重新设置node为头节点
- 让cur的next指针指向node
【注意】 - 当链表为空时，将头节点赋值为node，然后让node的下一个节点指向自身
def add(self,item):
"""在头部添加元素 头插法"""
node = Node(item)
# 链表为空的情况
if self.is_empty()
self.__head = node
node.next = node
else:
# 找到尾节点
cur = self.__head
while cur.next !- self.__head:
cur = cur.next
# 循环退出后，cur指向尾节点
node.next = self.__head # 让新节点的下一个元素指向当前头节点的元素
self.__head = node
cur.next = node
1.6 append函数【尾插法】
作用：在链表尾部添加元素
- 大致思路与单向链表相同
【注意】 - 当链表为空时，不存在cur.next，因此需要考虑链表为空的情况
- 当链表为空时，直接将当前的头节点赋值为node，node的next指针指向自身，当前尾节点的next指针指向node
def append(self,item):
"""在尾部添加元素 尾插法"""
# 注意item是传进来的一个数据，不是节点
node = Nonde(item)
# 需要考虑链表为空的情况
if self.is_empty():
self.__head = node
node.next = node
cur = self.__head
# 让cur一直往后走，走到尾节点
while cur.next != self.__head:
cur = cur.next
node.next = self.__head
cur.next = node
1.7 search函数
作用：查找节点是否存在
- 当cur的next指针所指的不是self.__head时遍历。每次对比cur是否和item相等，相等则返回True，结束遍历，不相等则cur移动一个索引位置，继续比较
- 退出循环后，游标处于尾节点，需要对比尾节点的元素是否和item相等，相等则返回True，结束遍历，不相等则返回False
【注意】 - 当链表为空时，不存在cur.next，因此需要考虑链表为空的情况
- 当链表为空时，直接返回False
def search(self,item):
"""查找某个元素是否存在"""
cur = self.__head
# 链表为空时直接返回False
if self.is_empty():
return False
# 当cur没有移动到末尾时
while cur.next != self.__head:
if cur.elem == item:
return True
else:
cur = cur.next
# 游标指向尾节点，需要判断尾节点是否是item
if cur.elem == ietm:
return True
return False
1.8 insert函数
作用：在指定位置插入元素
- insert方法与单向链表完全相同
# insert方法与单链表相同
def insert(self,pos,item):
"""在指定位置添加节点"""
# 特殊情况
if pos <= 0:
# pos小于等于0视为在头部插入元素
self.add(item)
# pos大于链表长度，视为在尾部添加
elif pos > self.length()-1:
self.append(item)
else:
# pos 从0开始
cur = self.__head
count = 0
# cur需要移动到pos所在位置的前面
while count < (pos-1):
# cur后移
cur = cur.next
count += 1
#当循环退出后，cur指向pos-1位置
node = Node(item)
node.next = cur.next
cur.next = node
1.9 remove函数
作用：删除指定位置元素
- 需要创建两个游标，pre和cur，pre始终指向cur的前一个节点
- 遍历链表【while cur.next != __head】,如果当前节点不是要删除的节点，则移动cur 和 pre
- 当cur指向的元素于要删除的元素相等时，直接让pre的next指针指向cur的next位置，即可删除此节点元素
- 如果要删除的节点为头节点，即cur处于head的位置，需要创建rear游标，让其移动到尾节点的位置【需要让尾节点的next指针指向新的头节点】
- 当前cur处于头节点的位置，让新的头节点指向cur.next
-
rear指向的尾节点重新指向新的头节点
修改完后return结束函数【区别单链表的break】
【注意】 - 循环退出后处于尾节点，要处理尾节点的情况
- 如果链表只有一个节点，则直接让self.__head为None即可
如果是遍历到尾节点的部分，则让pre.next = cur.next
def remove(self,item):
"""删除节点"""
if self.is_empty():
return
# 需要cur和pre两个游标
cur = self.__head
pre = None
while cur.next != self.__head:
if cur.elem == item:
# 如果是头节点，则直接指向cur.next
if cur == self.__head:
# 找到尾节点
# 创建一个rear游标，用于查找尾节点
while rear.next != self.__head:
rear = rear.next
# 循环退出后rear处于尾节点
self.__head = cur.next
rear.next = self.__head
else:
# 中间节点
pre.next = cur.next
# 区别单链表，这里必须使用return ,因为循环结束后还有代码
# 如果使用break，否则删除头节点时会报错
return
else:
# 不是需要删除的节点则移动游标
pre = cur
cur = cur.next
# 退出循环时代表处于尾节点
if cur.elem == item:
# 当链表只有1个节点时
if cur == self.__head: # 或者pre == None??
self.head = None
else:
pre.next = cur.next
2 完整代码
class SingleLinklist(object):
"""单链表"""
def __init__(self,node=None):
# 单向循环链表创建头节点后，头节点末尾指向自身
self.__head = None
if node:
node.next = node
def is_empty(self):
"""判断是否为空"""
return self.__head == None
def length(self):
"""返回长度"""
if self.is_empty():
return 0
# 建立一个游标，由于对链表进行遍历
# 当count = 0 时，可以解决链表为空的情况
cur = self.__head
# 区别单向链表，此时count需要从1开始
count = 1
while cur.next != self.__head:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历列表"""
# 链表为空时直接结束
if self.is_empty():
return
cur = self.__head
while cur.next != self.__head:
print(cur.elem,end =" ")
cur = cur.next
# 循环退出后cur指向尾节点
# 但尾节点的元素没有打印
print(cur.elem)
def add(self,item):
"""在头部添加元素 头插法"""
node = Node(item)
# 链表为空的情况
if self.is_empty()
self.__head = node
node.next = node
else:
# 找到尾节点
cur = self.__head
while cur.next !- self.__head:
cur = cur.next
# 循环退出后，cur指向尾节点
node.next = self.__head # 让新节点的下一个元素指向当前头节点的元素
self.__head = node
cur.next = node
def append(self,item):
"""在尾部添加元素 尾插法"""
# 注意item是传进来的一个数据，不是节点
node = Nonde(item)
# 需要考虑链表为空的情况
if self.is_empty():
self.__head = node
node.next = node
cur = self.__head
# 让cur一直往后走，走到尾节点
while cur.next != self.__head:
cur = cur.next
node.next = self.__head
cur.next = node
# insert方法与单链表相同
def insert(self,pos,item):
"""在指定位置添加节点"""
# 特殊情况
if pos <= 0:
# pos小于等于0视为在头部插入元素
self.add(item)
# pos大于链表长度，视为在尾部添加
elif pos > self.length()-1:
self.append(item)
else:
# pos 从0开始
cur = self.__head
count = 0
# cur需要移动到pos所在位置的前面
while count < (pos-1):
# cur后移
cur = cur.next
count += 1
#当循环退出后，cur指向pos-1位置
node = Node(item)
node.next = cur.next
cur.next = node
def remove(self,item):
"""删除节点"""
if self.is_empty():
return
# 需要cur和pre两个游标
cur = self.__head
pre = None
while cur.next != self.__head:
if cur.elem == item:
# 如果是头节点，则直接指向cur.next
if cur == self.__head:
# 找到尾节点
# 创建一个rear游标，用于查找尾节点
while rear.next != self.__head:
rear = rear.next
# 循环退出后rear处于尾节点
self.__head = cur.next
rear.next = self.__head
else:
# 中间节点
pre.next = cur.next
# 区别单链表，这里必须使用return ,因为循环结束后还有代码
# 如果使用break，否则删除头节点时会报错
return
else:
# 不是需要删除的节点则移动游标
pre = cur
cur = cur.next
# 退出循环时代表处于尾节点
if cur.elem == item:
# 当链表只有1个节点时
if cur == self.__head: # 或者pre == None??
self.head = None
else:
pre.next = cur.next
def search(self,item):
"""查找某个元素是否存在"""
cur = self.__head
# 链表为空时直接返回False
if self.is_empty():
return False
# 当cur没有移动到末尾时
while cur.next != self.__head:
if cur.elem == item:
return True
else:
cur = cur.next
# 游标指向尾节点，需要判断尾节点是否是item
if cur.elem == ietm:
return True
return False
网友评论