Linked list is a common basic data structure. It is a kind of linear table, but it does not store data continuously like the sequential table, but stores the location information (i.e. address) of the next node in each node (data storage unit).
A one-way linked list is also called a single linked list. Each node contains two domains, an information domain (element domain) and a link domain. The link points to the next node in the list, and the link field of the last node points to a null value.
Table element field elem is used to store specific data.
The location where the next link domain is used to store the next node (the identity in python)
The variable p points to the location of the head node (the head node) of the linked list. Starting from P, any node in the list can be found.
The following package a single chain table, so that it has the most basic functions.
The specific implementation code and effect are as follows:
""" Date: 2019--06 16:11 User: yz Email: email@example.com Desc: """ class Node(object): def __init__(self, element): self.element = element self.next = None class SingleLink(object): def __init__(self): self.head = None def is_empty(self): return self.head == None def __len__(self): if self.is_empty(): return 0 else: cur = self.head length = 0 while cur != None: length += 1 cur = cur.next return length def trvel(self): if not self.is_empty(): cur = self.head while cur.next != None: print(cur.element, end=' ') cur = cur.next print(cur.element) else: print("Empty linked list") def append(self, item): node = Node(item) if self.is_empty(): self.head = node else: cur = self.head while cur.next != None: cur = cur.next cur.next = node def add(self, item): node = Node(item) node.next = self.head self.head = node def insert(self, index, item): if index <= 0: self.add(item) elif index >= len(self): self.append(item) else: node = Node(item) count = 0 cur = self.head while count < index - 1: count += 1 cur = cur.next node.next = cur.next cur.next = node def remove(self, item): cur = self.head pre = None while cur != None: # Specified element found if cur.element == item: # If the first one is the deleted node if not pre: # Point the head pointer to the next node of the head node self.head = cur.next else: # Point the next of the previous node of the delete location to the next node of the delete location pre.next = cur.next break else: pre = cur cur = cur.next def search(self, item): """Whether the link list lookup node exists and returns True perhaps False""" cur = self.head while cur != None: if cur.element == item: return True cur = cur.next return False if __name__ == '__main__': link = SingleLink() print("Chain length:", len(link)) link.trvel() print("Is the list empty?", link.is_empty()) print("Add element:") link.append(8) link.append(4) #Link list header add link.add(6) #Link list specified location add link.insert(1, 'good') print("Chain length:", len(link)) # Calendar list link.trvel() #Delete 4 link.remove(4) #Find whether the element 6 exists in the linked list print(link.search(6)) link.trvel()
In this way, our single chain table is packaged. It also has the basic function of single chain table.