This is the 13th day of my participation in the Novembermore Challenge.The final text challenge in 2021

introduce

Arrays are probably the most commonly used data structures when we want to store multiple elements. But array has a downside is that, once to insert or remove a, then the position of the element behind all to change, the cost is very high, then list the data structures will play an advantage, because he USES pointer to connect all of its elements, when a change, so he just has to change to.

In this issue we will take you to explain how to write a linked list structure with ordinary objects, use digimon evolution to explain the case printing.

concept

A linked list stores an ordered collection of elements, but unlike an array, the elements in a linked list are not placed consecutively in memory. Each element consists of a node that stores the element itself and a reference (also known as a pointer or link) to the next element.

The body of the

1. The Node class

export class Node {
    constructor(item) {
        this.item = item;
        this.next = null; }}Copy the code

Before we do the list, we have to write a node class that will hold the current value and the next point to the node.

2. The LinkedList class

export class LinkedList {
    constructor() {
        this.count = 0;
        this.head = null;
        return this;
    }
    size() {
        return this.count;
    }
    toString() {}
    push(item) {}
    indexOf(item) {}
    removeAt(index) {}
    remove(item) {}
    insert(item, index){}}Copy the code

We use the list to record the head and the current list length count. The following methods are as follows:

  • Size: Returns the number of nodes in the current linked list.
  • ToString: A string that returns all the values of the current list.
  • Push: Push a node to the list, and finally return the current list length.
  • IndexOf: Returns whether an element exists in the list, its index, or -1 if not.
  • RemoveAt: Remove the node of an item based on the passed subscript. If true is returned, the deletion succeeds; if false, the deletion fails.
  • Remove: Removes the node of an item based on the passed element and returns true for successful deletion, false for failed deletion.
  • Insert: Inserts a node and returns the current list length.

3. Push&toString method

push(item) {
    let node = new Node(item);
    if (!this.head) this.head = node;
    else {
        let target = this.head;
        while (target.next) {
            target = target.next;
        }
        target.next = node;
    }
    return ++this.count;
}
toString() {
     let target = this.head;
     let str = this.head.item || "";
     while (target.next) {
         const { next } = target;
         target = next;
         str += "," + (typeof next.item == "object" ? JSON.stringify(next.item) : next.item);
     }
     return str;
}   
Copy the code

The push method is similar to the push method in the array, which injects the node at the end of the list, but we need to look up the last item and point to the new node. ToString also iterates to the last item, but only to concatenate strings.

We can see that a digimon evolution has been completed and the results printed out in toString.

4. IndexOf method

indexOf(item) {
    let target = this.head
    for (let i = 0, len = this.count; i < len; ++i) {
        if (target.item == item) return i
        else target = target.next;
    }
    return -1;
}
Copy the code

IndexOf is similar to our indexOf strings and arrays in that it iterates through the list, returning the position immediately if a match is found, and -1 if not.

And we can see that this evolutionary path, the subarchaic and the second term, but not the Garulus.

3. RemoveAt&remove method

removeAt(index) {
    if (index < 0 || index >= this.count) return false;
    if (index == 0) {
        this.head = this.head.next;
    }else{
        let target = this.head;
        for (let i = 1; i < index; i++) {
            target =  target.next; 
        }
        target.next = target.next.next;
    }
    this.count--;
    return true;
}
remove(item) {
    let index = this.indexOf(item);
    if(index ! = = -1) return this.removeAt(index);
    return false;
}
Copy the code

We’ll start with removeAt, which will do a boundary check, and return false if it’s beyond the length or less than zero. And then we also have to determine if it’s the 0th term, we just replace the head, because we have a generic list, head doesn’t point to anything. The others traverse to find where they want to interrupt, and then direct their next point to their next node, which is equivalent to skipping them. The remove method directly borrows the index from indeOf and transfers it to removeAt.

After testing, we found that removing garulus is not possible because there is no such type in the evolutionary path, and we succeeded in removing Tyrannosaurus. Of course, we also succeeded in removing the third item with Linkedlist.removeat (3), and the evolutionary chain can only reach the Subarchinus.

4. Insert method

insert(item, index) {
    if (index < 0 || index >= this.count) return false;
    let node = new Node(item);
    let target = this.head;
    for (let i = 1; i < index; i++) {
        target =  target.next; 
    }
    node.next = target.next;
    target.next = node;
    return ++this.count
}
Copy the code

Insert means to insert an item at a location. Just like removeAt, you need to do boundary determination, traverse to find the location where you want to insert, change the node pointing to the current node, and the node pointing to the previous node pointing to the previous node.

Insert (” Lost Tyrannosaurs “,4) add lost Tyrannosaurs to the fourth item, so its evolutionary path is complete.

conclusion

This time we learn to implement the linked list structure. This period is also a basic course, itself is also focused on understanding the idea rather than the implementation of the case itself, do not be too tangled, the case is the evolution of digital baby, but in fact, he is not an ordinary list, he is a two-way list or a multi-branch tree, after all, there is degradation? Think of a train or subway car, one after the other. The linked list itself has many variants, in some cases will greatly compensate for the lack of arrays, we also choose to use it.