preface

The front end rarely has the opportunity to contact the algorithm, most of them are interactive operations, so many front end engineers will hold such an idea: I am doing the front end, why should I learn data structure and algorithm? Without data structures and algorithms, I get the job done just fine. In fact, algorithm is a broad concept, any code we usually write can be an algorithm, it is an accurate and complete description of the solution to a problem, is a clear instruction to solve a series of problems, it represents a systematic method to describe the strategy mechanism to solve the problem. Now with the rapid development of Internet, the front-end engineer is not operated with a few selector add link to add events will be able to cope with, more and more complex products and basic library, need solid data structure and algorithm to manage, so I think that the front-end engineer is also should attach importance to algorithms and data structures, which are of great help for their career development is. Of course, algorithm learning is not overnight, it is a process, have to explore, to practice, to sum up, I only here some common algorithms and data structure with JavaScript to achieve, play a role of a brick to draw inspiration.

List (List)

List is a common data structure in computer. Shopping lists and to-do items in daily life can be lists. It is a group of ordered data, and the data items in each list are called elements. In javascript, the elements in a list can be any data type. There is no limit to how many elements a list can hold (it is limited by program memory in practice). There are some common attributes or methods in the list, such as the number of elements in the list, the current position of the list, adding an element to the end of the list, removing an element from the list, clearing the list, and so on. Next, we abstract out the data type definition of a list and implement it with an array in JS.





Data type definitions for lists

The list of classes

Function List () {this.listSize = 0; This. pos = 0; // The initialization position is 0 this.dataStore = []; // Initialize the empty array to hold the list element this.clear = clear; this.find = find; This.tostring = toString; // Display elements in the list this.insert = insert; this.append = append; this.remove = remove; this.front = front; this.end = end; this.prev = prev; this.next = next; this.length = length; This. currPos = currPos; this.moveTo = moveTo; this.getElement = getElement; this.contains = contains; // Check whether the given value is in the list}Copy the code

And then we implement these methods.

You need to be able to add elements first, so let’s write the append method first

Append: Adds an element to the list

Function append (element) {this.datastore [this.listsize+ +] = element; }Copy the code

Now that we’re ready to add elements to the list, let’s look for the find method

Find: Finds an element in a list

Function find(element){for(var I = 0; function find(element){var I = 0; i < this.dataStore.length ; i ++ ){ if( this.dataStore[i] == element ){ return i; } } return -1; }Copy the code

We can insert elements, so we can always delete, so we remove an element using remove

Remove: Removes an element from the list

// This method intercepts the dataStore array by using the find() method to return the location of the element. If the deletion succeeds, it returns true and decreases the listSize value by 1 to update the list length. Function remove (element) {var foundAt = this.find(element); if( foundAt > -1 ){ this.dataStore.splice( foundAt , 1 ); --this.listSize; return true; } return false; }Copy the code

When I want to know how many more elements I have in my list, I have to build the length method,

Length: Returns the total number of elements in the list

Function length(){return this.listsize; }Copy the code

It would be nice if I could show my list element, I could have this, so let’s look at the toString method,

ToString: Displays the elements of the list

Function toString(){return this.datastore; }Copy the code

Now that our list has some basic features, let’s give it a try

Var fruits = new List(); // Add three elements fruits. Append ('Apple'); fruits.append('Grape'); fruits.append('Banana'); // Print list console.log(fruits.tostring ()) // ["Apple", "Grape", Log (fruits.length()) // 3 // Find the position of Banana console.log(fruits.find('Banana')) // 2 // Delete Grape fruits.remove('Grape'); console.log( fruits.toString() ) // ["Apple", "Banana"]Copy the code

If we remove the Grape element and we want to put it back in its original position, we need to call insert

Insert: Adds an element somewhere in the list

// This method takes two arguments: the first argument represents the element to be inserted, and the second argument represents the element before the element to be inserted, which determines the position of the element to be inserted, and calls the splice method to change the list array, updating the listSize on success and returning true, otherwise returning false; function insert( element , after ){ var insertPos = this.find( after ); if( insertPos > -1 ){ this.dataStore.splice( insertPos + 1 , 0 , element ); this.listSize ++; return true; } return false; }Copy the code

Now, let’s put Grape back in its place;

fruits.insert( 'Grape' , 'Apple' );
console.log( fruits.toString() )        // ["Apple", "Grape", "Banana"]
Copy the code

Ok, it’s now possible to insert Grape into its original position.

If I’ve eaten all the fruit, and I want to clear the list now, we need a clear method;

Clear: Clears the list

// This method uses the delete operator to delete the dataStore array, then creates a new array and initializes its listSize and pos to 1. function clear(){ delete this.dataStore; this.dataStore = []; this.listSize = this.pos = 0; }Copy the code

We may as well give it a try.

fruits.clear(); console.log( fruits.toString() ); / / []Copy the code

Success!

We have seen that there is a POS property in the list that represents the current position of the list, so we are going to do something around it so that the user can manipulate the list freely

Front: Moves the position of the list to the first position

Function front(){this.pos = 0; }Copy the code

End: Moves the position of the list to the last position

Function end(){this.pos = this.listsie-1; }Copy the code

Prev: Moves the current position forward one bit

Function prev(){if(this.pos > 0){this.pos --; function prev(){this.pos --; }else{console.log(' you are currently in the first place '); }}Copy the code

Next: Move the current position back one bit

Function next(){if(this.pos < this.listsie-1){++this.pos; function next(){if(this.pos < this.listsie-1){++this.pos; }else{console.log(' you are currently at the end '); }}Copy the code

MoveTo: Moves the current position to the specified position

// Change the value of pos. Pay attention to the legitimacy of the input function moveTo (position) {if (position < 0 | | position > (enclosing listSize - 1)) {the console. The log (' please enter the correct position); }else{ this.pos = position; }}Copy the code

Since I can change the position of my list at will, I always know where MY current position is, so I need the currPos and getElement methods to return the current position and element, respectively.

CurrPos: Returns the current position of the list

Function currPos(){return this.pos; }Copy the code

GetElement: Returns the element in the current position

Function getElement(){return this.datastore [this.pos]; }Copy the code

Next, we test it by first returning the list to its original form, and then adding a few more elements.

// Add a few more fruits. Append ('Pear'); fruits.append('Orange'); fruits.append('Strawberry'); console.log( fruits.toString() ); // ["Apple", "Grape", "Banana", "Orange", "Strawberry"] console.log(fruits.currpos); // 0 console.log( fruits.getElement() ); // Apple // We try to change fruits.moveto (2); fruits.next(); console.log( fruits.currPos() ); // 3 console.log( fruits.getElement() ); // Pear fruits.end(); fruits.prev(); console.log( fruits.currPos() ); // 4 console.log( fruits.getElement() ); // OrangeCopy the code

So now that we’re pretty much done with lists, we’re left with one last one, which is to determine if a given element is in a list, and we use the contains method here

Contains: Determines whether the given value is in the list

//ES5 function contains(element){if(this.datastore.indexof () {//ES5 function contains(element){if(this.datastore.indexof (); element ) > -1 ) return true; else return false; } //ES6 function contains( element ){ return this.dataStore.includes( element ); }Copy the code

(Ps: If you are not familiar with ES6, you can also refer to my other series of ES6 blogs.)

Write the quiz,

console.log(fruits.contains('Banana'));         // true
console.log(fruits.contains('Watermelon'));     // false
Copy the code

And you’re done! We have implemented a list by ourselves with javascript. As for how to expand it later (such as making a circular list), we can divergent our thinking and practice more.