Article directory
- 1. Python implements data structure
-
- 1.1 Python implements one-way linked list
- 1.2 Python implements one-way circular linked list
- 1.3 python implements doubly linked list
1. Python implements data structure
1.1 Python implements one-way linked list
singleLinkedList.py
class SingleNode: """the node of single link list""" def __init__(self, item): self.item = item self. next = None def __str__(self): return str(self. item) class SingleLinkList: """sing link list""" def __init__(self): self._head = None def is_empty(self): """Determine whether the linked list is empty""" return self._head is None def length(self): """Get the length of the linked list""" cur = self._head count = 0 while cur is not None: count + = 1 cur = cur. next return count def travel(self): """Traverse the linked list""" cur = self._head while cur is not None: print(cur. item) cur = cur. next print() def add(self, item): """Add element to the head of the linked list""" node = SingleNode(item) node.next = self._head self._head = node def append(self, item): """Add element at the end of the linked list""" node = SingleNode(item) if self. is_empty(): self._head = node else: cur = self._head while cur.next is not None: cur = cur. next """At this point cur points to the last node, next=None""" cur.next = node def insert(self, pos, item): """Add element at specified position""" # If pos is less than 0, perform header insertion if pos <= 0: self. add(item) # If the length of the pos large fish list, perform tail insertion elif pos > self. length() - 1: self. append(item) else: node = SingleNode(item) cur = self._head cur_pos = 0 while cur.next is not None: """Get the previous node at the insertion position""" if pos - 1 == cur_pos: node.next = cur.next cur.next = node break cur = cur. next cur_pos += 1 def remove(self, item): """Delete node""" if self. is_empty(): return cur = self._head if cur.item == item: self._head = cur.next else: while cur.next is not None: if cur.next.item == item: cur.next = cur.next.next break cur = cur. next def search(self, item): """Find node location""" cur = self._head count = 0 while cur is not None: if cur.item == item: return count cur = cur. next count + = 1 return -1 # if __name__ == "__main__": # ll = SingleLinkList() # ll. add(1) # ll. add(2) # ll.append(3) #ll.insert(2,4) # print("length: ", ll. length()) # ll. travel() # print("search(3): ", ll. search(3)) # print("search(5): ", ll. search(5)) # ll. remove(1) # print("length: ", ll. length()) # ll. travel()
1.2 Python realizes one-way circular linked list
sinCycLinkedList.py
class Node: def __init__(self, item): self.item = item self. next = None def __str__(self): return str(self. item) class SinCycLinkedList: """One-way circular linked list""" def __init__(self): self._head = None def is_empty(self): """Determine whether the linked list is empty""" return self._head is None def length(self): """Returns the length of the linked list""" if self. is_empty(): return 0 cur = self._head count = 1 while cur.next != self._head: count + = 1 cur = cur. next return count def travel(self): """Traverse the linked list""" 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): """Add node to the head of the linked list""" node = Node(item) if self. is_empty(): self._head = node node.next = node else: cur = self._head node.next = self._head while cur.next != self._head: cur = cur. next cur.next = node self._head = node def append(self, item): """Add a node at the end of the linked list""" 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 cur.next = node node.next = self._head def insert(self, pos, item): """Insert a node at the specified position in the linked list""" if pos <= 0: self. add(item) elif pos > self. length() - 1: self. append(item) else: cur = self._head cur_pos = 0 node = Node(item) while cur.next != self._head: if cur_pos == pos - 1: node.next = cur.next cur.next = node break cur = cur. next cur_pos += 1 def remove(self, item): """Delete the specified node in the linked list""" if self. is_empty(): return pre = self._head if pre.item == item: cur = pre while cur.next != pre: cur = cur. next cur.next = pre.next self._head = pre.next else: cur = pre while cur.next != pre: if cur.next.item == item: cur.next = cur.next.next #break cur = cur. next def search(self, item): """Find the node and return the subscript """ cur = self._head count = 0 while cur.next != self._head: if cur.item == item: return count count + = 1 cur = cur. next return -1 # if __name__ == "__main__": # ll = SinCycLinkedList() # ll. add(1) # ll. add(2) # ll. travel() # ll.append(3) # ll. insert(2, 4) # ll. insert(4, 5) # ll. insert(0, 6) # print("length", ll. length()) # ll. travel() # print("search(3)", ll. search(3)) # print("search(7)", ll. search(7)) # print("search(6)", ll. search(6)) # print("remove(1)") # ll. remove(1) # print("length: ", ll. length()) # print("remove(6)") #ll. remove(6) # ll. travel()
1.3 python implements doubly linked list
doubleLinkedList.py
class Node: def __init__(self, item): self.item = item self. previous = None self. next = None def __str__(self): return str(self. item) class DLinkedList: """Doubly linked list""" def __init__(self): self._head = None def is_empty(self): """Determine whether the linked list is empty""" return self._head is None def length(self): """Returns the length of the linked list""" if self. is_empty(): return 0 count = 1 cur = self._head while cur.next is not None: count + = 1 cur = cur. next return count def travel(self): """Traverse the linked list""" if self. is_empty(): return cur = self._head print(cur. item) while cur.next is not None: cur = cur. next print(cur. item) print() def add(self, item): """Add node to the head of the linked list""" node = Node(item) if self. is_empty(): self._head = node else: node.next = self._head self._head.previous = node self._head = node def append(self, item): """Add a node at the end of the linked list""" node = Node(item) if self. is_empty(): self._head = node else: cur = self._head while cur.next is not None: cur = cur. next cur.next = node node.previous = cur def insert(self, pos, item): """Insert a node at the specified position in the linked list""" if pos <= 0: self. add(item) elif pos > self. length() - 1: self. append(item) else: cur = self._head node = Node(item) cur_pos = 0 while cur is not None: if cur_pos == pos - 1: node.next = cur.next node.previous = cur cur.next = node cur.next.previous = node break cur = cur. next cur_pos += 1 def remove(self, item): """Delete the specified element from the linked list""" if self. is_empty(): return cur = self._head if cur.item == item: self._head = cur.next self._head.previous = None else: while cur.next is not None: if cur.item == item: cur.previous.next = cur.next cur.next.previous = cur.previous return cur = cur. next if cur.item == item: cur.previous.next = None def search(self, item): """Find the specified element in the linked list and return the element subscript """ cur_pos = 0 cur = self._head while cur is not None: if cur.item == item: return cur_pos cur = cur. next cur_pos += 1 return -1 if __name__ == "__main__": ll = DLinkedList() 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("search(3) ", ll. search(3)) print("search(4)", ll. search(4)) print("search(10) ", ll. search(10)) ll. remove(1) print("length: ", ll. length()) ll. travel() print("Delete the first node remove(6): ") ll. remove(6) ll. travel() print("Delete the tail node remove(5): ") ll. remove(5) ll. travel()