preface

This paper mainly summarizes the writing skills of linked list in data structure, including understanding the meaning of pointer, memory leak, sentry thought, boundary processing and so on. And some thoughts and experience of the summary.

Tips for writing list code

Understand the meaning of Pointers or references

meaning

Assigning a variable (object) to a pointer (reference) is actually assigning the address of the variable (object) to the pointer (reference).

The sample

P ->next=q indicates that the successor pointer of the p node stores the memory address of the q node.

P ->next=p->next->next indicates that the successor pointer to the p node stores the memory address of the next node after the p node.

Beware of pointer loss and memory leaks

Insert the node

How do Pointers get lost? Let me give you an example of inserting a single linked list.

Insert node x between node A and adjacent node B, assuming that the current pointer p points to node A. Pointer loss and memory leaks can occur if we change the code implementation to look like this.

p->next = x; // Set the next pointer of p to x; x->next = p->next; // Set the next pointer of x to b;Copy the code

The p->next pointer no longer points to node B, but to node X after the first operation. The second line of code is equivalent to assigning x to x->next, pointing to itself. Therefore, the list is broken in half, and all nodes from node B are inaccessible.

Therefore, when inserting nodes, we must pay attention to the order of operation. We must first point the next pointer of node X to node B, and then point the next pointer of node A to node X, so as not to lose the pointer and cause memory leak.

The correct way to write is the exchange order of two sentences of code, namely:

X - > next = p - > next; P - > next = x;Copy the code

Remove nodes

Node B is deleted between node A and node B. node B is next to node A. the p pointer points to node A. So the example looks like this:

P - > next = p - > next - > next;Copy the code

Use sentry to simplify implementation

What is a sentry?

The “sentinel” nodes in the list solve boundary problems and do not participate in business logic.

If we introduce the sentinel node, the head pointer will point to the sentinel node regardless of whether the list is empty. We call such a list with sentinel nodes led, while a list without sentinel nodes is called unled.

No sentinels introduced

If you insert a node after the p node, it takes only two lines of code:

New_node - > next = p - > next; P - > next = new_node;Copy the code

However, to insert a node into the empty list, the code is as follows:

if(head == null){
    head = new_node;
}
Copy the code

If we want to delete the successor of node p, we need only one line of code:

P - > next = p - > next - > next;Copy the code

However, if you delete the last node in the list (the only node left in the list), the code is as follows:

If (head -- >next == null){head = null; }Copy the code

As can be seen from the above situation, for the insertion and deletion of the linked list, special processing is needed for the case of inserting the first node and deleting the last node. This makes the code seem tedious, so “Sentinel” nodes are introduced to solve this problem.

Introduce the sentry situation

The Sentinel node does not store data. The head pointer points to the sentinel node regardless of whether the list is empty. The sentinel node always exists as the head of the list.

As you can see from the linked list below, the Sentinel node does not store data. Because sentinel is always there, inserting the first node and inserting the other nodes, deleting the last node and deleting the other nodes can be implemented in the same code logic.

“Sentry” understanding

Sentry can be understood as a way to reduce the judgment of special cases, such as:

  • Sentenced to empty;
  • Sentenced to cross;
  • Reduce the judgment of empty linked list in the insertion and deletion of linked list;

Empty and out of bounds can be considered small probability cases, so the code will go through the judgment of each operation, in most cases will be redundant.

The sentry’s trick is to get rid of this in advance. You give a sentinel, you assign a key to the last element of the array, and you can walk through the array and stop for equality without judging that it’s out of bounds.

The guiding principle of using sentry: Kill the judgment that small probability requires in advance.

For example, give it a value in advance so that it is not null, or give it a preset value in advance, or give it an empty implementation in the case of polymorphism, and then do not have to judge it in every operation to increase efficiency.

Application scenarios of Sentry

The techniques of using Sentry to simplify programming are useful in many code implementations, such as insertion sort, merge sort, dynamic programming, and so on.

Focus on boundary condition treatment

4 boundary conditions often used to check whether the list is correct:

  1. Does the code work if the list is empty?
  2. Does the code work if the list contains only one node?
  3. Does the code work if the list contains only two nodes?
  4. Does the code logic work when dealing with the head and tail nodes?

For different scenarios, there may be certain boundary conditions, so you have to think about that, but the pattern is the same.

Draw pictures with examples to help thinking

Core idea: Release some of your brain capacity and allow more logical thinking, so you’ll feel much clearer.

Use e examples and drawings. For example, to insert data into a single linked list, take each case as an example, and plot the list changes before and after insertion, as shown in the figure below:

Write more and practice more. There is no shortcut

Five common linked list operations

  1. Single linked list inversion
  2. Linked list of central detection
  3. Merge two ordered lists
  4. Example Delete the NTH node from the list
  5. Find the middle node of the list

Exercise question LeetCode corresponding number: 206,141,21,19,876. You can go and practice

Thinking and experience

  1. When you need to move the list in a function, it is best to create a new pointer to move it, so as not to change the original pointer position.

  2. The single linked list has the lead node and not the lead node of the list, generally do the default head node is a value.

  3. The memory of a linked list is discontinuous. Each node occupies a block of memory, and each block of memory has a place (next) to store the address of the next node (this is a single linked list example).

  4. Link list to find the idea of the ring: create two Pointers a fast pointer a walk two steps a slow pointer a step, if encounter there is a ring, if the first point to null, no ring.

  5. The idea of finding the KTH node from the bottom of the list is to create two Pointers. The first one takes k-1 steps and then the two go together. The first one goes to the end and the second pointer points to the k from the bottom.

  6. The idea of reverse list: the pointer of each node is reversed from the front to the back, that is, the address in.next is changed to the address of the previous node, but in order to prevent the loss of the later list, before each change, we need to create a pointer to the next node.

  7. The idea of merging two ordered lists: recursion is used here. First determine whether there is an empty list of the list, if yes, return two lists, lest the pointer to the unknown region caused the program crash. The next pointer points to this function (the recursion starts, and the argument is the list where the smaller value is located. Next and another list).

reference

  • The beauty of data structures and algorithms