In the previous article, I introduced the meanings of several common linked lists. Today, I will introduce how to write the correct linked list code.

How do I represent linked lists

The linked list we typically design has two classes. The Node class is used to represent nodes, and the LinkedList class provides helper methods such as adding, deleting, and viewing nodes and displaying list elements. Let’s look at how to represent a linked list in JS code.

Code demo:

{
  var Node = function(data) {
    this.data = data;
    this.next = null;
  };
  var node1 = new Node(1);
  var node2 = new Node(2);
  var node3 = new Node(3);

  node1.next = node2;
  node2.next = node3;
  console.log(node1.data);
  console.log(node1.next.data);
  console.log(node1.next.next.data);
}
Copy the code

The Node class contains two properties: Data, which holds the data on the Node, and next, which holds the link to the next Node.

{
    var LList = function() {
        this.head = new Node('head');
        this.find = find;
        this.insert = insert;
        this.remove = remove;
        this.display = display; }}Copy the code

The LList class provides methods for manipulating linked lists. This class uses a Node class to hold the headers in the list. When a new element is inserted, next points to the new element.

How about that? Easy, right? You already know lists

But, this is just basic linked list notation, and the water is still deep.

Matters needing attention

Bring the single linked list diagram from the previous article for easy reference

Point 1: Understand the meaning of Pointers or references

A pointer or a reference here, they all mean the same thing, they’re the memory address of the object to which they’re referring.

Assigning a variable to a pointer is essentially assigning the address of a variable to the pointer, or conversely, the pointer contains the memory address of the variable, points to the variable, and the pointer finds the variable.

See what this pseudo-code means:

p -> next = q;
Copy the code

This line of code says that the next pointer in p stores the memory address of q.

Now look at what the following code represents:

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

This line of code shows that the next pointer to p stores the memory address of the next node of P.

You should now get a sense of what Pointers or references are.

Point two: beware of pointer loss and memory leaks

When we’re writing linked list code, our Pointers, in particular, are constantly changing, pointing around. So make sure you don’t lose the pointer when you write.

Insert a single linked list as shown below

We want to insert node D between node B and neighboring node C. Suppose the current pointer P points to node B. If you implement your code like this, pointer loss and memory leaks will occur.

/ / pseudo code
p -> next = d; // set p's next pointer to D;
d -> next = p -> next // Next pointer on D to C? Node.
Copy the code

After the first step, the p -> next pointer no longer points to node C, but to the newly added node D. The second line of code assigns D to D ->next, pointing to itself. Therefore, the whole list is truncated.

Therefore, when we add nodes, we must pay attention to the operation sequence. We should first point the next pointer of node D to node C, and then point the pointer of node B to node D, so as not to lose the pointer. You know the correct way to modify that code.

Key three: pay attention to the processing of boundary conditions

Let’s review the insertion of a single linked list. If you add a new node after p, you only need to focus on the following two steps.

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

However, special treatment is required when we insert the first node into an empty linked list. If the head of the linked list is empty, then it can be assigned as follows:

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

Take a look at the complete code for adding nodes:

// add a new node
  append(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
      this.tail = this.head;
    } else {
      this.tail.next = node;
      this.tail = node; }}Copy the code

The head is equal to the tail if it does not exist. Use the tail to extend the list if the header exists, and don’t forget to move tail to become the tail.

Let’s look at deleting a single linked list node. If a node is deleted after p, only one step is required:

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

However, if only one node in the list is head, special processing is also required, as follows:

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

To remove the code logic, see Github – linked list -remove

The methods I provided are quite complicated. When I read “JavaScript Description of Data Structure and Algorithm”, I found the methods written in the book are particularly concise. Share it here.

Here is the code for deleting nodes in this book:

{
/* Check whether the data to be deleted is stored in the next node of each node based on the element to be deleted. If found, the node, the previous node, is returned. * /
  function findPvevious(item) {
    var currNode = this.head;
    while(! (currNode.next ==null) && (currNode.next.element ! = item)) { currNode = currNode.next; }return currNode;
  }
 // Then, after finding the previous node, delete the node using the singly linked list deletion operation mentioned above.
  function remove(item) {
    var prevNode = this.findPvevious(item);
    if(! (prevNode.next ==null)) { prevNode.next = prevNode.next.next; }}}Copy the code

So when writing linked list code, always pay attention to whether boundary conditions are taken into account:

  • Does the code work if the list is empty?
  • Does the code work if the list has only one node?
  • Does the code work when dealing with heads and tails?

Key four: learn to draw pictures to assist thinking

For example, some single – linked list of additions, deletions, changes, and so on, the pointer is always changing. At this time if the brain can not think, you can simply draw a schematic diagram to assist. For example, when adding nodes to a single list, you can draw the list changes before and after adding nodes.

Code demo

Head over to Github to see a common approach to linked lists

Reference books

JavaScript Description of Data Structures and Algorithms

You are perfect

Linked list this kind of data structure, is really easy to understand, but want to write a good related operation code, it is not easy, pointer or reference is also my weak link, I can not remember how to point to point! The joints of animals are very important for animals. The pointer feels like the joints of a linked list. The linked list is like a train.

portal

  1. A stack of JavaScript data structures
  2. Queues for JavaScript data structures
  3. JavaScript data structures stack against stack
  4. Linked lists of JavaScript data structures — Introduction
  5. Complexity analysis of JavaScript algorithms
  6. Best and worst time complexity analysis of JavaScript algorithms