Data structure and algorithm fundamentals (front-end bias)
December 8, 2023
by Roger Patel
No Comments
Mentioned algorithm, a lot of people who graduated from CS will not unfamiliar, but no matter you are solid theoretical knowledge learned in school how to still have to play in the school experience (ACM), but at work because there is no actual application scenarios, or very little application scenarios, lead to some of knowledge and operating conveniently came to feel that is very rusty.
At the same time, as I am now specialized in the front-end work (originally, I did both the front and back ends), many application scenarios do not involve algorithms. This is also the front end at the top of the tech disdain chain. In fact, the front end is also a lot of top algorithm ideas and implementation. You just use it when someone else does it for you.
So I have always believed in one creed:
Experience is the mother of knowledge
So, for the rest of the document, I’ll put together a review and summary of geek Time’s course on data structures and the beauty of algorithms (most of the content is geek Time, but some of it is also checked by me for comparison and verification).
This course is just a personal learning document and opinion, if there is any mistake and understanding deviation, please feel free to comment.
The complexity of the
Progressive complexity, including time complexity and space complexity, is used to analyze the growth relationship between algorithm execution efficiency and data size. It can be roughly expressed that the higher the algorithm of order complexity, the lower the execution efficiency
From low order to high order: O(1), O(logn), O(n), O(nlogn), O(n2)
An array of
Arrays are probably the most common class of quantitative types that you see in development, and the most common class of linear tables.
Classification of linear tables
Statically typed languages (Java,c++)
A linear table data structure. It uses a contiguous set of memory Spaces to store a set of data of the same type.
Dynamically typed languages (javaScript)
As JavaScript arrays are implemented As hash-maps or dictionaries and not contiguous.
The list
Instead of a contiguous memory space, it uses Pointers to concatenate a set of discrete memory blocks
Memory allocation
Linked lists use Pointers to concatenate a set of discrete chunks of memory. We refer to memory blocks as nodes of linked lists
Singly linked lists
There are two nodes that are special, the first node and the last node. We habitually call the first node the head node and the last node the tail node. The header is used to record the base address of the linked list. And with that, we can go through the whole list. The special thing about endpoints is that instead of pointing to the next node, the pointer points to an empty address, NULL, indicating that this is the last node on the list.
Circular linked list
A pointer to the tail of a circular list points to the head of the list
Two-way linked list
Bidirectionally linked lists require two extra Spaces to store the addresses of successors and precursors. So, if you store the same amount of data, bidirectionally linked lists take up more memory than single-linked lists.
Linked list VS array performance
Random access in an array refers to random access by index
Js implements a linked list (for CRUD)
The general structure is as follows:
Size and head are private attributes of the LinkedList constructor. Size records how many nodes there are in the list, and head points to the head of the list
Unidirectional linked list code implementation
/** * Custom list: Public methods include * append(element) append a node to the end of the list * insert(index, element) Insert node at index position * remove(Element) Remove node * removeAt(index) Remove specified index node * removeAll(element) Remove all matching nodes *setAccording to the index, Change the node value of the corresponding index * get(index) Obtains node information based on the index * indexOf(element) Obtains the index position of a node * clear() Clears all nodes * length() Returns the node length *print() Prints all node information * toString() prints all node informationprint
* */
const LinkedList = function() {let head = null;
letsize = 0; // Count the list elements //Node modelfunctionLinkNode(element, next){ this.element = element; this.next = next; } // Element out of bounds check, out of bounds throws an exceptionfunction outOfBounds(index){
if (index < 0 || index >= size){
throw("Sorry, target location does not exist!"); }} // Get the target object according to the indexfunction node(index){
outOfBounds(index);
let obj = head;
for (let i = 0; i < index; i++){
obj = obj.next;
}
returnobj; } // Add a new elementfunction append(element){
if (size == 0){
head = new LinkNode(element, null);
}
else{
letobj = node(size-1); obj.next = new LinkNode(element, null); } size++; } // Insert an elementfunction insert(index, element){
if (index == 0){
head = new LinkNode(element, head);
}
else{
letobj = node(index-1); obj.next = new LinkNode(element, obj.next); } size++; } // Modify the elementfunctionset(index, element){
letobj = node(index); obj.element = element; } // Remove node elements based on the valuefunction remove(element){
if (size < 1) return null;
if (head.element == element){
head = head.next;
size--;
return element;
}
else{
let temp = head;
while(temp.next){
if (temp.next.element == element){
temp.next = temp.next.next;
size--;
return element;
}
else{ temp = temp.next; }}}returnnull; } // Remove nodes by indexfunction removeAt(index){
outOfBounds(index);
let element = null;
if (index == 0){
element = head.element;
head = head.next;
}
else{
let prev = node(index-1);
element = prev.next.element;
prev.next = prev.next.next;
}
size--;
returnelement; } // Remove all elements in the list that match elementfunction removeAll(element){
letvirHead = new LinkNode(null, head); // Create a virtual head node with head as the secondary nodelet tempNode = virHead, ele = null;
while(tempNode.next){
if (tempNode.next.element == element){
tempNode.next = tempNode.next.next;
size--;
ele = element;
}
else{ tempNode = tempNode.next; }} // reassign head = virhead.next;returnele; } // Get an elementfunction get(index){
returnnode(index).element; } // get the element indexfunction indexOf(element){
let obj = head, index = -1;
for (let i = 0; i < size; i++){
if (obj.element == element){
index = i;
break;
}
obj = obj.next;
}
returnindex; } // Clear all elementsfunctionclear(){ head = null; size = 0; } // Attribute to stringfunction getObjString(obj){
let str = "";
if (obj instanceof Array){
str += "[";
for (let i = 0; i < obj.length; i++){
str += getObjString(obj[i]);
}
str = str.substring(0, str.length - 2);
str += "]."
}
elseif (obj instanceof Object){
str += "{";
for (var key in obj){
let item = obj[key];
str += "\" " + key + "\"," + getObjString(item);
}
str = str.substring(0, str.length-2);
str += "},"
}
elseif (typeof obj == "string"){
str += "\" " + obj + "\" " + ",";
}
else{
str += obj + ",";
}
return str;
}
functiontoString() {let str = "", obj = head;
for (let i = 0; i < size; i++){
str += getObjString(obj.element);
obj = obj.next;
}
if (str.length > 0) str = str.substring(0, str.length -2);
returnstr; } // Print all elementsfunctionprint(){console.log(this.tostring ())}} this.append = append; this.insert = insert; this.remove = remove; this.removeAt = removeAt; this.removeAll = removeAll; this.set =set;
this.get = get;
this.indexOf = indexOf;
this.length = function() {return size;
}
this.clear = clear;
this.print = print; this.toString = toString; } //// test //let obj = new LinkedList();
// let obj1 = { title: "All-star Game.", stores: [{name: "Zhang Fei vs Yue Fei", store: "" "}, { name: "Guan Yu vs Qin Qiong", store: "The center"}}; // // obj.append(99); // obj.append("hello")
// obj.append(true)
// obj.insert(3, obj1);
// obj.insert(0, [12, false."Good", 81]);
// obj.print();
// console.log("obj1.index: ", obj.indexOf(obj1)); // obj.remove(0); // obj.removeAll(obj1); // obj.print(); //// Test 2 console.log("\n\n...... test2.....")
var obj2 = new LinkedList();
obj2.append(8); obj2.insert(1,99); obj2.append('abc'); obj2.append(8); obj2.append(false);
obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8); obj2.print(); obj2.removeAll(8); // delete all 8 obj2.print();Copy the code
A simple algorithm for Linked Lists (reverse one-way Linked Lists)
/ * * * *function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let prev = null;
letcurr = head; / / define"The sentinel"while(curr ! = null) {letnextTemp = curr.next; Curr. Next = prev; // Disconnect from the rest of the list and point to changes prev = curr; // Curr = nextTemp; // move pointer down}return prev;
};
Copy the code
The stack
A good example of a stack is a stack of plates stacked on top of each other. When we usually put plates, are from the bottom up one by one; When we take them, we take them one by one from the top down, not from the middle. Last come out, first come out, this is the typical “stack” structure.
From the operation characteristics of the stack
A stack is an “operation-constrained” linear table that allows data to be inserted and deleted at only one end.
In fact, stacks can be implemented as arrays or linked lists. A stack implemented in arrays is called a sequential stack, and a stack implemented in linked lists is called a chained stack. (This is only for statically typed languages like C,C++,JAVA, etc.)
Function call stack
The operating system allocates each thread a separate block of memory, which is organized into a “stack” structure to store temporary variables for function calls. Each time a function is entered, a temporary variable is pushed onto the stack as a frame. When the called function completes execution and returns, the corresponding frame of the function is pushed off the stack.
functionmain() {
let a = 1;
let ret = 0;
let res = 0;
ret = add(3.5);
res = a + ret;
console.log(The processing result is${res}`);
reuturn 0;
}
functionadd(x, y) {
let sum = 0;
sum = x + y;
return sum;
}
Copy the code
The figure shows the stack of function calls when the add() function is executed.
Application of stack in expression evaluation
In fact, the compiler is implemented through two stacks. One holds the stack of operands, and the other holds the stack of operators. We iterate through the expression from left to right, and when we encounter a number, we push it directly onto the operand stack; When an operator is encountered, it is compared with the top element of the operator stack.
The calculation of the expression 3+5*8-6 is plotted as follows:
Implement browser forward and backward functions
Using two stacks, X and Y, we push the first page into stack X, and when the back button is clicked, we push the page out of stack X and put the data out of stack INTO stack Y. When we click the forward button, we take data from stack Y in turn and put it into stack X. When there is no data in stack X, there are no pages to go back to. When there is no data in stack Y, there are no pages to browse by clicking the forward button.
Into the stack,
For example, if a, B, and C are viewed in sequence and a, B, and C are pushed in sequence, the data of the two stacks will look like this:
2. After you move from page C to page A using the browser’s back button, pop c and B off stack X and onto stack Y. At this point, the data for both stacks looks like this:
Repeat the preceding steps to explain how to roll back and forward the browser.
Stack in memory vs. data structure stack
Stack in memory and data structure Stack is not a concept. It can be said that the stack in memory is a real physical area, and the stack in data structure is an abstract data storage structure.
Memory space
Memory space is logically divided into three parts: code area, static data area, and dynamic data area, the dynamic data area is divided into stack area and heap area.
Code area: The binary code that stores the method body. High-level scheduling (job scheduling), intermediate scheduling (memory scheduling), low-level scheduling (process scheduling) control the code area to execute the switch code.
Static data area: stores global variables, static variables, constants, including final modified constants and String constants. The system automatically allocates and recycles.
Stack area: stores the parameters, local variables, and return values of the run method. It is automatically distributed and recycled by the system.
Heap: New A reference or address to an object stored in the stack refers to the object’s real data stored in the heap.
The queue
A queue, like a stack, is a linear table data structure with limited operation.
Sequential queue and chain queue
Queues, like stacks, are abstract data structures. It has a first-in, first-out feature and supports inserting elements at the end of the queue and deleting elements at the head of the queue.
Queues can be implemented using arrays or linked lists. Arrays are called sequential stacks, and linked lists are called chained stacks. Similarly, arrays are called sequential queues, and lists are called chained queues.
Code to implement a sequential queue
// Queue with arraysconst ArrayQueue=function(){
// Array: items, array size: nlet items =[];
let n = 0;
// head indicates the team header index, and tail indicates the team tail indexlet head = 0;
let tail = 0;
// Apply for an array of capacityfunctioncreateArrayQueue(capacity) {
items = newArray(capacity);
n = capacity;
}
// Add item to the end of the queuefunctionenqueue(item) {
// tail == n Indicates that there is no space at the end of the queueif (tail == n) {
// tail ==n && head==0, indicating that the queue is fullif (head == 0) returnfalse;
// Data movefor (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// Update the head and tail after the move
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
returntrue;
}
/ / out of the teamfunctiondequeue() {
// If head == tail, the queue is emptyif (head == tail) returnnull;
// To make it more explicit for students of other languages, put the -- operation on a separate linelet ret = items[head];
++head;
return ret;
}
this.createArrayQueue = createArrayQueue;
this.enqueue = enqueue;
this.dequeue = dequeue;
}
Copy the code
Circular queue
When tail==n, there will be a data move, which will affect queue performance.
To avoid data movement, use circular queues for processing.
We can see that the size of the queue is 8, with head=4 and tail=7. When a new element, A, joins the team, we place it at subscript 7. But at this point, instead of updating tail to 8, we move it back one bit in the loop to zero. When another element B enters the queue, we put b at zero, and then tail increments by 1 to update to 1. So, after a and B are queued, the elements in the loop queue look like this:
In this way, we successfully avoid data migration operations.
Code to implement a loop queue
const CircularQueue = function{
// Array: items, array size: nlet items;
let n = 0;
// head indicates the team header index, and tail indicates the team tail indexlet head = 0;
let tail = 0;
// Apply for an array of capacityfunctioncreateCircularQueuee(capacity) {
items = newArray(capacity);
n = capacity;
}
/ / teamfunctionenqueue(item) {
// The queue is fullif ((tail + 1) % n == head) returnfalse;
items[tail] = item;
tail = (tail + 1) % n;
returntrue;
}
/ / out of the teamfunctiondequeue() {
// If head == tail, the queue is emptyif (head == tail) returnnull;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
this.createCircularQueuee = createCircularQueuee;
this.enqueue = enqueue;
this.dequeue = dequeue;
}
Copy the code
