Tip 1: Understand the meaning of Pointers or references

Pointers or references store the memory address of an object. Assigning a variable to a pointer is essentially assigning the address of the variable to the pointer.

P ->next=q indicates that the next pointer in p stores the memory address of q. Just read it from left to right, and the next node of p is q.

Tip 2: Beware of pointer loss and memory leaks

Take the insertion of a single linked list. Insert x between node A and adjacent node B, assuming that the current pointer P points to node A.

p->next = x; // set p's next pointer to x; x-next = p -> next; // next pointer on node x to node b;Copy the code

Obviously, there is something wrong with the above code execution. Node X ends up pointing to itself, and the linked list breaks, causing a memory leak. So we should reverse the order.

When inserting nodes, pay attention to the order of operations so that Pointers are not lost. When deleting nodes, be sure to manually release the memory to avoid memory leaks.

Tip 3: Use sentries to simplify the implementation

In order to insert and delete linked lists, special treatment is needed for inserting the first node and deleting the last node. For example, check whether it is null.

The head pointer will always point to the sentinel node, whether the list is empty or not. The linked list with sentinel nodes is called a lead linked list. On the contrary. A list without sentries is called an unheaded list.

The sentinel node does not store data. Because the sentinel node is always there, inserting the first node and inserting the other nodes, deleting the last node and deleting the other nodes, can use the same code to implement the logic.

Tip 4: pay attention to boundary condition processing

Boundary conditions commonly used to check whether linked list code is correct:

  • Does the code work if the list is empty?
  • Does the code work if the linked list contains only one node?
  • Does the code work if the linked list contains only two nodes?
  • Does the code logic work when dealing with heads and tails?

In fact, when writing any code, not just linked list code, don’t just implement business-as-usual functions. Think about what boundary cases or exceptions your code might encounter as it runs. Write code that is robust when confronted with what to do about it!

Skill five: draw pictures with examples to help you think

You can take a concrete example, draw it on a piece of paper, free up some brain space and leave more for logical thinking, and you will feel much clearer.

Tip 6: Write and practice more, there is no shortcut

Five common linked list operations are selected as exercises.

  • Single-linked list inversion
  • Linked list central detection
  • Merge two ordered linked lists
  • Delete the NTH node from the penultimate list
  • Find the intermediate node of the linked list