Mentioned data structure and algorithm are feeling this should be the backend to master knowledge, as long as write a page for the front-end, bind an event, it is good to send data to the background, use less than the data structure and algorithm, maybe to find a simple for loop for some data can be done, maybe just raised a few milliseconds, negligible, False into node to do background development, a request to save a few milliseconds, tens of millions of requests to save is not millisecond time, data structure is as a senior program engineers will be knowledge

Welcome to visit happy Garbage collector, a front-end knowledge summary sharing platform, and we grow together and progress together! 🙏 🙏 🙏

Let’s start with the JS data types

  • Basic types (stack) : Number, String, Boolean, Null and Undefined, Symbol(es6 new); Basic data types are allocated from high to low by value access, stack memory is up to 8MB, (out of stack overflow), String: is special stack memory (allocated to high variable size), programmer allocation
  • Reference types (heap) :Object, Array, Function, Data; Reference type data stored in stack memory is actually the object in the heap memory reference address (pointer), allocated to high, the system automatically allocated
A, stack space allocation difference:
  • Stack (operating system) : automatically allocated and released by the operating system, storing function parameter values, local variable values, etc. It operates like a stack in a data structure;
  • Heap (operating system) : The heap is allocated and released by the programmer. If the programmer does not release the heap, the program may be recycled by the OS at the end of the program. Allocation is similar to a linked list.
Two, stack cache method difference:
  • Stacks use a level 1 cache, which is usually stored in storage when called and released immediately after the call.
  • The heap is stored in a level 2 cache, and its lifetime is determined by the virtual machine’s garbage collection algorithm (objects are not recycled once orphaned). So the speed of calling these objects is relatively low.
Iii. Differences between heap and stack data structures:
  • Heap (data structure) : A heap can be thought of as a tree, e.g. Heap sort;
  • Stack (data structure) : A first-in, last-out data structure.

The data structure

Data structure refers to the set of data elements which have one or more relations with each other and the composition of the relationship between the data elements in the set. The most important rule for setting up basic operations on data structures is to achieve application and storage structure independence (data structure = storage of data + algorithm)

Data structure classification

  • Logical structure: reflects the logical relationship between data;

  • 1. The representation of data structures in a computer;

Logical structure:
Collection: Data elements in a structure have no relationship other than that they belong to the same type. (No logical relationship) Linear structure: One-to-one relationship between data elements (linear table) Tree structure: One-to-many relationship between data elements (nonlinear) Graph structure or network structure: Many-to-many relationship between data elements in a structure (nonlinear)Copy the code
Storage structure:
Sequential storage data structure Chain storage data structure Index storage data structure Hash storage data structureCopy the code

Linear structure:

  • Queue: Also a linear table with limited operations. It only allows insertion at one end of the table and deletion at the other. The end that allows deletion is called front, and the end that allows insertion is called rear. First in, first out.
  • Stack: a linear table in which insertion and deletion operations are limited to one end of the table. This end is usually called the Top and the other end is the Bottom of the stack. First in, last out. If top= -1, the stack is empty. If top=0, there is only one element in the stack, and the top should increment when the element is pushed onto the stack. Last in, first out
  • String: A finite sequence of zero or more characters. A String of length zero is called an Empty String and contains no characters. A String that consists of only one or more Spaces is usually called a Blank String. Note the difference between a Blank String and a Blank String. For example, “” and” “represent a Blank String of length 1 and a Blank String of length 0 respectively.

Nonlinear structure

  • Tree: A nonlinear structure. Tree is a recursive structure, and the concept of tree is used in the definition of tree
  • Order number: There is an order relationship between the children
  • Unordered tree: There is no sequential relationship between the children
  • Binary tree: a nonlinear structure. Tree is a recursive structure, and the concept of tree is used in the definition of tree
Binary tree traversal

So that every node is accessed once and only once. Non-recursive traversal implementations make use of stacks.

  • Traversal DLR first: root -> left -> right subtree (breadth traversal)Copy the code
  • Middle-order traversal LDR: left subtree -> root node -> right subtree. Middle order traversal is required to get the correct order of a binary tree (breadth traversal)Copy the code
  • Subsequent traversal of LRD: left subtree -> right subtree -> root node. Stack support is required. (Breadth traversal)Copy the code
  • Hierarchical traversal: When storing a binary tree with a one-dimensional array, the nodes are always stored in hierarchical traversal order. Hierarchical traversal should use queues. (Depth traversal)Copy the code

Memory: a long one-dimensional array;

algorithm

Algorithm features:

There is poverty, certainty, feasibility, input, output

Algorithm design measures:

Accuracy, readability, robustness, time complexity, space complexity

Classification algorithm

Basic algorithms (required)

Bubble sort

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // Compare adjacent elements in pairs
                var temp = arr[j+1];        // Element swap
                arr[j+1] = arr[j]; arr[j] = temp; }}}return arr;
}
Copy the code

Quick sort

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

function partition(items, left, right) {
    var pivot = items[Math.floor((right + left) / 2)],
        i = left,
        j = right;
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if(i <= j) { swap(items, i, j); i++; j--; }}return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right);
        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }
        if(index < right) { quickSort(items, index, right); }}return items;
}

var items = [3.8.7.2.9.4.10]
var result = quickSort(items, 0, items.length - 1);
Copy the code

Insertion sort

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}
Copy the code

Selection sort

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // Find the smallest number
                minIndex = j;                 // Save the smallest index
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
Copy the code

Time space complexity

  • In bubble sort, insert sort, select sort, quicksort, in the worst case, the quicksort time complexity is O(n2), insert sort O(n2), select sort O(n2), bubble sort O(n2)

Welcome to visit happy scavenger for more front-end knowledge!