1 js implementation of single linked list

What is a list? What is the difference between an array and a list? I won’t expand on that. Native JS does not have linked lists, so encapsulate a simple version. The code looks like this, and it’s not hard at all.

Function LinkedList() {// wrap a Node class, Function Node(element) {this.element = element this.next = null} // This. Length = 0 this.head = null / / on the list additional element method LinkedList. Prototype. Append = function (element) {/ / 1. Var newNode = newNode (element) // 2. If (this.head === null) {// the list is null this.head = newNode} else {// The list is not empty // 2.1. Var current = this.head while (current.next) {current = current.next} // 2.2. Find the last item and assign it next as node current.next = newNode} // 3. Length_length_length}} this. Length_length_lengthCopy the code

So what does this method implement?

    var list = new LinkedList()
    list.append(1)
    list.append(2)
    list.append(3)
    list.append(4)
    console.log(list)
Copy the code

The print result is as follows

If you go a little bit further

Continue to spread

2. Realize the meaning of single linked list

Arrays are perfectly adequate for a front-end er, and there are so many other useful methods, so why encapsulate one of these yourself?

Answer: above of do not understand, cannot do interview question. The interviewer asks you do you know the algorithm? You said to know some, and then ask you the question of the list, the most basic, list and array have what difference, have to know it, then list has what characteristics, this also have to know ah, or let you reverse a single list how to reverse ah?

3 How do I reverse a single linked list

Take the list as an example, how to achieve 4-3-2-1-NULL? Implement the results shown below

Function myReverse (linkedList) {var head = linkedList. Head // 2 . = = = null | | head next = = = null) return linkedList, three pointer var / / 3, the current head var pre = null var next = = null while(current ! = null) { next = current.next current.next = pre pre = current current = next } linkedList.head = pre }Copy the code

In fact, it is really not difficult, mainly is a thinking transformation. Here is a record of their own understanding, but also for me to see. The myRevese function accepts a list of parameters, and first takes out the head of the list. And then make the boundary judgment. Then the important thing is how to do the next pointer substitution. First, there is no array for map for traversal of a linked list. The list of traversal can only be human flesh node by node to find down. So this code is necessary

var current = head var next = null while(current ! = null) { next = current.next current = next }Copy the code

Only in this way can the list traversal be completed.

  • Back in myRevese itself, current = head, pre, and next are null during initialization.
  • On the first loop, next will save the next of current. Otherwise, the current. Next point will be changed to refer to its previous node
  • Current. Next = pre invert, current node next must be changed to point to its predecessor node
  • Current is about to become current. Next, so the previous node of current is current itself. So pre = current
  • Current = next, the previously saved variable is used
  • Until the last loop, when current is the last node, current becomes current. Next, which means current is null, so we need to redefine the head of the list to point to pre instead of current.

4 summary

This is interesting for a front-end ER that has been writing vue for a long time, and the algorithm masters just ignore it.