Unidirectional circular linked list definition
A Single Cycle Linked List is a variation of a Single Linked List that makes the next field of the last node in the List no longer None, but points to the head node of the List.
Node diagram
One-way circular chains indicate intent
The basic operation of a one-way circular linked list
is_empty()Check whether the linked list is emptylengthChain length of the tabletravel()Iterate through the list, printing elementsadd(item)Add an element to the head of the listappend(item)Add an element to the end of the listinsert(pos, item)Inserts an element at the specified positionremove(item)Remove elementsclear()To empty the listis_contain(item)Determines whether the element exists
Python code implementation
# Code implementation of nodes
class Node(object):
"" "node "" "
def __init__(self, item):
self.item = item
self.next = None
Copy the code# unidirectional cyclic linked list code implementation
class SingleCycleLinkList(object):
"" one-way cyclic linked list ""
def __init__(self):
self._head = None
def is_empty(self):
"" determine if the linked list is empty ""
return self._head is None
@property
def length(self):
""" Returns the length of the list ""
# If the list is empty, return length 0
if self.is_empty():
return 0
count = 1
cur = self._head
whilecur.next ! = self._head:
count += 1
cur = cur.next
return count
def travel(self):
""" Walk through the linked list ""
if self.is_empty():
return
cur = self._head
print(cur.item)
whilecur.next ! = self._head:
cur = cur.next
print(cur.item)
print("")
def add(self, item):
""" Add node to header ""
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
The node added points to _head
node.next = self._head
Move to the end of the list and point next to node
cur = self._head
whilecur.next ! = self._head:
cur = cur.next
cur.next = node
#_head points to the added node
self._head = node
def append(self, item):
""" End node added ""
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
Move to the end of the list
cur = self._head
whilecur.next ! = self._head:
cur = cur.next
Point the tail node to node
cur.next = node
# point node to the head node _head
node.next = self._head
def insert(self, pos, item):
""" Adds node at specified location """
if pos <= 0:
self.add(item)
elif pos > (self.length- 1) :
self.append(item)
else:
node = Node(item)
cur = self._head
count = 0
Move to the position preceding the specified position
while count < (pos- 1) :
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
""" Delete a node """
If the list is empty, return it directly
if self.is_empty():
return
# point cur to the head node
cur = self._head
pre = None
# if the first element is the element to be searched
if cur.item == item:
# If the list has more than one node
ifcur.next ! = self._head:
Find the tail node first and point next of the tail node to the second node
whilecur.next ! = self._head:
cur = cur.next
# cur points to the tail node
cur.next = self._head.next
self._head = self._head.next
else:
The list has only one node
self._head = None
else:
pre = self._head
The first node is not to be deleted
whilecur.next ! = self._head:
The element to delete was found
if cur.item == item:
# remove
pre.next = cur.next
return
else:
pre = cur
cur = cur.next
# cur points to the tail node
if cur.item == item:
# end delete
pre.next = cur.next
def clear(self):
""" Clear the linked list """
self._head = None
def is_contain(self, item):
""" Find if the node exists """
if self.is_empty():
return False
cur = self._head
if cur.item == item:
return True
whilecur.next ! = self._head:
cur = cur.next
if cur.item == item:
return True
return False
def __len__(self):
You can use len() to get the list length.
return self.length
def __iter__(self):
You can loop through the elements in the list.
if self.is_empty():
return
cur = self._head
yield cur.item
whilecur.next ! = self._head:
cur = cur.next
yield cur.item
def __contains__(self, item):
You can use in to determine if you are in the list.
if self.is_empty():
return False
cur = self._head
if cur.item == item:
return True
whilecur.next ! = self._head:
cur = cur.next
if cur.item == item:
return True
return False
Copy the code# Test data
if __name__ == "__main__":
print("-------- create linked list -------")
scl_list = SingleCycleLinkList()
scl_list.add(1)
scl_list.add(2)
scl_list.append(3)
scl_list.insert(2.4)
scl_list.insert(4.5)
scl_list.insert(0.6)
print("length:",len(scl_list))
scl_list.travel()
print(scl_list.is_contain(3))
print(scl_list.is_contain(7))
print(3 in scl_list)
print(7 in scl_list)
scl_list.remove(1)
print("length:",len(scl_list))
scl_list.travel()
print("-------- loop through -------")
for i in scl_list:
print(i)
Copy the code# output result
-------- Create a linked list -------
length: 6
6
2
1
4
3
5
True
False
True
False
length: 5
6
2
4
3
5
-------- Loop traversal -------
6
2
4
3
5
Copy the codeAlgorithm analysis
| operation | The complexity of the |
|---|---|
| Access to the elements |  |
| Insert/delete in the header | |
| Insert/delete at the end | |
| Insert/delete in the middle | |
Contact us
Personal blog: www.bling2.cn/
Github address: github.com/lb971216008…
Zhihu column: zhuanlan.zhihu.com/Use-Python-…
Small column: xiaozhuanlan.com/Use-Python-…
Blog Park: www.cnblogs.com/Use-Python-…
