## Single linked list

Features: the node contains only one pointer field, and the beginning and end are not connected

Illustration:

Noun:

noun | concept |
---|---|

Head pointer | Pointer to the first node in the linked list (either the head node or the first element node) |

Head node | A node attached before the first node of the linked list; Only information such as table length is put in the data field, which is not included in the table length. Its function is to unify the forms of empty list, and non empty linked list |

Initial node (start node) | Refers to the node where the first data element a1 of the linear table is stored in the linked list |

Tail node (end node) | Refers to the last node in the linked list, and the tail pointer points to NULL |

You should understand that what problems do linked lists solve in our development?

When inserting and deleting an array, you need to find the current element and move all subsequent elements forward or backward. After finding the linked list, you only need to point to the new node with the pointer of the previous node or delete the next node of the element.

You can use your brain to think about how convenient it is to associate disordered and non adjacent elements through a linked list and add and delete them quickly!

## Implementation of single linked list in Python

#Create node object class class Node(object): #Create a node and initialize two variables. The default is None. Create a new node and pass the value value. The next node object is saved def __init__(self, value=None, next=None): self.value, self.next = value, next class SingleLink(object): #Initialize three variables, # final_node: record the last node # root: record header node # Length: the length of the linked list def __init__(self): self.final_node = None self.root = Node() self.length = 0 # Add at the end # Insert a node at the end of the linked list, that is, final_node points to a new node and updates final_node and length increase by 1 def append(self, value): node = Node(value) if self.final_node is None: self.root.next = node else: self.final_node.next = node self.final_node = node self.length += 1 # Head increase # Insert a node in the head, that is, the root head node points to the new node, temporarily record the next node before pointing to the new node, point the root node to the new node, and point the new node to the next node. The length increases by 1 def appendleft(self, value): node = Node(value) if self.root.next is None: self.root.next = node else: cur_node = self.root.next self.root.next = node node.next = cur_node self.length += 1 # Sequential node # Loop through the linked list, first judge whether the linked list is None, which is an empty linked list # Starting from the root node, while loops through the next node and outputs the node. When the node = final_node, that is, traverse to the last node, directly exit the loop and output the last node def iter(self): if self.root is None: raise Exception("Link is Null") else: cur_node = self.root.next while cur_node != self.final_node: yield cur_node cur_node = cur_node.next yield cur_node # Return linked list length def len(self): return self.length # Return linked list data as array # Use the list generation formula to generate an array containing all value s of the linked list def iterlink(self): return [node.value for node in self.iter()] # Delete linked list data # Store the previous node, which is initially the root node # Cycle through the node and call the iter() method. When the traversed node value is equal to the incoming value, point the previous node to the next node of the current node, that is, delete (or manually del the occupation of this node in memory). If the node is the last node, remember to update final_node is the previous node of the current node, and the length decreases by 1 def delete(self, value): prev_node = self.root for node in self.iter(): if node.value == value: if node is self.final_node: self.final_node = prev_node else: prev_node.next = node.next self.length -= 1 else: prev_node = node # Query linked list data # Call iter method. When the value of node traversed is the same as the input value, return node def find(self, value): for node in self.iter(): if node.value == value: return node return -1 # Update linked list data # Call the iter method. When the value of the traversal node is the same as the incoming value, assign the new value to the traversal node. This assignment only changes the value, and the object is still the same node object, so no other operation is required def update(self, old_value, new_value): node = self.find(old_value) if node != -1: node.value = new_value return 1 else: return -1

When writing a single linked list in python, we need to think about:

1. Final node_ Use of node variable

2. When deleting, prev for the previous node_ Use of node variable

There is also a tail. I believe those who understand it can see that the above methods do not support the search, deletion and update of duplicate data. At present, they only operate on the first node found. After reading the article, you can try it yourself to expand the deletion, modification and query of duplicate data. You can really remember and understand it only by yourself, Don't just stop at understanding this level. Oh, come on

Note: you are welcome to communicate and learn, including but not limited to Web, data structure, operating system, database, middleware and other knowledge