Single linked list

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

Illustration:

Noun:

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