“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”
A brief introduction to linked lists
- A list of multiple elements
- The element stores are discontinuous and are linked together using the next pointer
Now, if you look at this, you might wonder, well, if it’s a list, how is it different from an array? We don’t want to forget that when we want to add or remove elements that are not at the beginning or end of an array, we need to change the index of the array, which can be very cumbersome and complicated. But when we add or delete non-beginning or end elements to the list, we just need to change the direction of next.
In the front end, or in JS, there is no linked list data structure, but we can simulate linked lists with Object.
The following code
- Now let’s try walking through the linked list
We declare a pointer and we get the value of each node by moving the pointer around, until the node points to null, indicating the last one
- Add a node, we add an e between BC’s
– Delete node E
Leetcode 237- Delete nodes in the linked list
If you think this is the first time you do this, a lot of people think it’s easy, you just point the previous node to the next node, and if you think this, you don’t really know what a linked list is, because you can’t get the last node directly. So that’s not going to work.
But we can do this, we can get the value of our next node. We can give the value of the next node to the node to be deleted, and then delete the next node, as shown in the figure
The following code
The above code is O(1) in time and space.
Leetcode 206- Reverse linked list
We can start with two nodes, if we only have two nodes, we can just point the second node to the first node, and along the way, we can use two Pointers to do the transposition.
The following code
This problem is mainly the application of double Pointers, many problems, we can according to this idea to solve.
Leetcode 2- Add two numbers
After traversing the two lists, add the corresponding positions into the new list. When the length of the two lists is not equal, the default value is 0 when there are no nodes. Over 10, ten digits are added to the calculation of the next node
Then move the node
If c was greater than 0 the last time we added it to the new list, this would be an error because we forgot to process C
The modified code is as follows:
It’s order N, it’s order N in space.
Leecode 83- Removes duplicate elements from sorted lists
If the current element is equal to the next element, delete the next element. If the next element is equal, move the pointer and continue the comparison.
Leetcode 141- Circular linked list
This problem is to judge whether there is a ring or not. We can compare the example in life, for example, we often watch F1 race recently. On the circular track, some good techniques can always fall a slow lap. The two drivers are bound to meet again at some point in the lap down. And we can apply this idea to this problem, we can declare two Pointers, one fast and one slow, and if it’s a circle, they’ll always meet. The specific code is as follows:
Prototype chain in JS
A lot of people might be wondering, if we’re talking about linked lists, why are we talking about prototype chains?
In fact, JS prototype chain is essentially a linked list, which is linked by _proto_.
So what is the length of the prototype chain? We can look at it by object, function, array.
As we can see from the above results, arrays and functions refer first to their prototype and then to their prototype. This is also true for strings and numbers
7.1 Knowledge points about prototype chain
A instanceof B is true if A can find b. prototype along the prototype chain
This is actually the example in the picture above.
If no y attribute is found on A, the y attribute is searched along the prototype chain until null is found or found
7.2 instanceof principle
You must have encountered such an interview question, please briefly explain the principle of Instanceof and implement instanceof
In fact, the principle of instanceof is: if A can find B.prototype along the prototype chain, then an instanceof B is true
The code is as follows:
Use the linked list to obtain the value of the Json node
This is actually a linked list in the front end of the application scenario, when we do some complex systems, we may need to do similar operations, here we use a small example to write a piece of code
