Learning tips. Usually when we’re learning something new, we start out motivated and ambitious. Because each new field is relatively easy to get started on, it is often comfortable to start learning something new. But then, as we got deeper, we hit a plateau, and one by one the difficulties surfaced, and we began to wonder if it was worth the time.

Overview of linked lists

Why are linked lists introduced

  • A large amount of data is often moved when nodes are inserted or deleted in a sequential table structure

Definition of linked list

  • Sequential data structures
  • A node usually has two parts, containing data and a pointer to the next node
  • The linked list structure is made up of many of these nodes. The first step is to define a “header reference” variable that points to the first node of the list structure.

Linked lists and arrays

  • Linked list storage is more flexible and does not require contiguous storage space as arrays do.

Type of linked list

  • Single linked list: As in the chain structure above, each node contains only one reference
  • Bidirectional linked lists: If each node contains two references, one to the next node and one to the previous node
  • Circular linked lists:

Linked lists support basic operations

  • Insert: Inserts a new element anywhere in the list
  • Delete: To remove an element from a linked list
  • Find: Find a specific element
  • Update: Updates elements on a particular node
  • Add: Adds a node

Code implementation

To realize the Node class

First we create a Node class that defines the data property to hold the data and the next property to point to the next Node.

class Node:
    def __init__(self, data=None) :
        self.data = data
        self.next = None
        
Copy the code

Realize the LinkedList class

LinkedList is used to link nodes together to form a data structure. Initialize the head node in the __init__ initialization method, creating a node with no data as head. This node is usually inaccessible to the user. The head node is used as a placeholder to accept nodes, so the head node is automatically created when LinkedList is initialized instead of being added by the user.

class LinkedList:
    def __init__(self) :
        self.head = Node()

Copy the code

Append method implementation

To add a node to the list, we first point the current pointer to the head node, and then traverse to the end of the list by determining whether the next attribute of the current node is null. When the next attribute is null, the cur pointer moves to the end of the list.

def append(self,data): new_node = Node(data) cur = self.head while cur.next ! = None: cur = cur.next cur.next = new_nodeCopy the code

Length method implementation

If you understand the way the append implementation iterates through the linked list, the length implementation here is not hard to understand.

    def length(self) :
        cur = self.head
        total = 0
        while cur.next! =None:
            total += 1
            cur = cur.next
        return total
Copy the code

Display method implementation

This is a linked list visualization method, nothing special in the code.

    def display(self) :
        elems = []
        cur_node = self.head
        while cur_node.next! =None:
            cur_node=cur_node.next
            elems.append(cur_node.data)
        print(elems)
Copy the code

The implementation of the GET method

The get method receives an index, which returns the corresponding node based on the index. The head node does not have an index. If it exceeds the length of the list, an exception warning is raised :’GET’ Index out of range! And return None. First, the cur_node node points to the head node, and then in the while loop, the current node points to the node next to the current node, And then I’m going to check if cur_idx is index so when index is 0 the current node is already the first node to be added instead of the head node, so you can figure that out for yourself

    def get(self,index) :
        if index>=self.length():
            print("ERROR:'GET' Index out of range!")
            return None
        cur_idx=0
        cur_node = self.head
        while True:
            cur_node=cur_node.next
            if cur_idx==index:return cur_node.data
            cur_idx+=1
Copy the code

The implementation of the delete method

    def delete(self,index) :
        if index>=self.length():
            print("ERROR:'Delete' Index out of range!")
            return
        cur_idx=0
        cur_node = self.head
        while True:
            last_node=cur_node
            cur_node = cur_node.next
            if cur_idx==index:
                last_node.next = cur_node.next
                return
            cur_idx+=1
            
Copy the code

Delete We need to delete the node corresponding to the current index from the previous node next to the current node.

if __name__ == "__main__":
    my_list = LinkedList()
    my_list.append(1)
    my_list.append(2)
    my_list.append(3)
    my_list.append(4)
    my_list.append(5)
    print(my_list.get(0))
    my_list.delete(3)
    my_list.display() # [1, 2, 3, 5]
Copy the code

The update method

This method is basically the same as the GET method in that it updates the node when it finds the corresponding index.

    def update(self,index,data) :
        if index>=self.length():
            print("ERROR:'Update' Index out of range!")
            return
        cur_idx = 0
        cur_node = self.head
        while True:
            cur_node=cur_node.next
            if cur_idx==index:
                cur_node.data = data
                return
            cur_idx+=1
Copy the code