This article serves as a reading guru

The book notes for the << Front-end Algorithms and Data Structure Interview >> refer to awe-coding-js

An array of

A collection of sequentially stored elements that can be accessed randomly

The characteristics of

  • When inserting and deleting, move subsequent elements, that is, add and delete slowly, and consider capacity expansion
  • The query is fast

Stack Stack

Adding and deleting 'arrays' using pop and push

/ * * * stack can only add data in from the tail, can only take data from the tail (pop, push) * / const stack = [] / / into the stack. The stack process push (' northeast big board) stack. Push (' cute ') stack. Push (' qiao le ' ') While (stack.length) {const top = stack[stack.length - 1] Console. log(' now out ', top) stack.pop()}Copy the code

Two characteristics of a stack

  • Only elements can be added from the tail
  • Only elements are allowed to be removed from the tail

Queue Queue

Add and remove 'arrays' with push and Shift (FIFO)

Two characteristics of queues

  • Only elements can be added from the tail
  • Only elements are allowed to be removed from the header
/** * Queue can only add data from the tail, can only fetch data from the head (push, Shif) * */ const queue = [] queue.push(' tokata ') queue.push(' Tokata ') queue.push(' Tokata ') queue.push(' Ice Factory ') queue.push(' Light milk ') While (queue.length) {const top = queue[0] console.log(' now queue is out ', top) queue.shift()}Copy the code

Hash table: think of the front end as an object

The list

The data unit of the linked list is called “node “, and each node contains two parts: data field and pointer field characteristics

  • You need to traverse to find the elements, the query is slow
  • Insert elements need to be disconnected and reassigned, adding and deleting quickly

Linked lists are similar to arrays in that they are linear structures (with one and only one precursor and one and only one successor). The difference is that in linked lists, data units are called nodes, and the memory distribution of nodes and nodes can be discretized.

The structure of each node in the linked list consists of two parts:

  • Data field: stores the value of the current node
  • Pointer field (Next): A reference to the next node in the pointer field

Js lists are nested objects:

const a = { val: 'head', next: { val: 1, next: { val: 2, next: { val: 3, next: '... '/ /... }}}},Copy the code

Simple linked list implementation:

class ListNode {
    constructor(val) {
        this.val = val
        this.next = null
    }
}
const head = new ListNode('head')
const node1 = new ListNode(1)
const node2 = new ListNode(2)
Copy the code

Addition of linked list elements: Change the precursor and target Pointers

/** * list element increment: * old: 1 -> 2 * new:1 -> 3 -> 2 * add elements, just change the next pointer of the precursor node and target node * 1 2 * \ / * 3 */ const node3 = new ListNode(3) node3.next = node1.next node1.next = node3Copy the code

Element deletion: Next skips the target node

Old 1 ->3->2 * new 1 ->2 * new 1 ->2 node1.next = node3.nextCopy the code

Binary tree

Tree is used to simulate the data set with tree structure, according to his characteristics can be divided into a variety of, we only need to understand the binary tree, almost enough

Binary tree is a typical tree structure. As the name implies, each node of a binary tree has at most two subtree structures, namely, the left subtree and the right subtree

Some calculation rules for trees

  • Tree hierarchy: the root node is in the first layer, its children are in the second layer, and so on
  • Degree: How many subtrees a node opens out, called the degree of this node
  • Leaf node: the node with degree 0 is leaf node
  • The height of node and tree: the height of leaf node is 1, and the height of each layer is increased by 1, which is accumulated to the target node layer by layer to obtain the height of the node. The maximum height of tree node is called the height of tree

Binary tree in js

The binary tree in JS is defined by objects and its structure can be divided into three parts:

  • Data fields
  • A reference to the left child
  • A reference to the child on the right

The structure is as follows:

Build a simple binary tree

Traversal posture of binary trees

The first sequence traversal

Input the above tree, corresponding to the output recursive implementation

function preOrder(root, array = []) { if (root) { array.push(root.val) preOrder(root.left, array) preOrder(root.right, Array)} return array} let res = preOrder(tree)Copy the code

In the sequence traversal

function preOrder(root, array = []) { if (root) { preOrder(root.left, array) array.push(root.val) preOrder(root.right, Array)} return array} let res = preOrder (tree) / / output [' D ', 'B', 'E', 'A', 'C', 'F']Copy the code

After the sequence traversal

In a back-order traversal, we first visit the left tree, then the right tree, and finally the root 

function preOrder(root, array = []) { if (root) { preOrder(root.left, array) preOrder(root.right, ['D', 'E', 'B', 'F', 'C', 'A']Copy the code

Big O– Algorithmic measurement

Time complexity

In the algorithm, the number of repeated basic operations is the time complexity of the algorithmCommon time complexity

Spatial complexity

A measure of the size of storage space temporarily displayed during the operation of an algorithm is called space complexity. Common space complexity is O(1), O(n), and O(n^2).