First of all, this is a serious technical article. After reading this article, you can learn:

  1. What is a linked list
  2. How is an array converted to a linked list
  3. How does a linked list turn into an array
  4. Common operations on linked lists
  5. Use scenarios of linked lists in the front end

What is a linked list

Linked lists can be divided into one-way linked lists and two-way linked lists. This is a one-way linked list, where each node is only responsible for linking its next node. Two-way linked list is on the basis of one-way linked list, add a link on a node function, can do back and forth.

The data structure of a one-way linked list looks something like this:

const linkedList = {
    val: 1.next: {
        val: 2.next: {
            val: 3.next: {
                val: 4.next: null}}}}Copy the code

How to convert an array into a linked list

Array-to-list can be broken down into two steps. The first step converts the current value to a linked ListNode, requiring a constructor ListNode, and then just running through the for loop, doing two actions:

  1. Each node is converted to a linked list node using a constructor;
  2. Sets the next number to be the successor of the current node.
function ListNode(val) {
    this.val = val;
    this.next = null;
}

function generateList(array) {
    // Non-null judgment
    if(! array || ! array.length) {return null;
    }

    let node = new ListNode(array[0]);
    let current = node;

    for (let index = 1; index < array.length; index++) {
        current.next = new ListNode(array[index]);
        current = current.next;
    }

    return node;
}
Copy the code

How to convert a list to an array

It’s even easier to convert lists to arrays. Because of the list, you can get the next node each time by next of the current node, and you just need a while loop to go through the list.

function generateArray(list) {
    let res = [];

    while (list) {
        res.push(list.val);
        list = list.next;
    }

    return res;
}
Copy the code

Common operations of linked lists

I will illustrate this part by combining the real problems in Leetcode

1. Flip the list

Sword refers to Offer II 024. Reverse linked list

function reverseList(head) {
    let prev = null;
    let cur = head;

    while (cur) {
        const next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next
    }

    return prev;
};
Copy the code

Code parsing: Essentially, starting from the beginning node, we keep recording the result of the previous round, and then each time, the next node of the current node points to the result of the previous round. It’s the same as if we shift over and over in the array, take the first value, and then unshift it and insert it into the result array. It’s just a next pointing problem in the linked list.

  1. 25. Merge two sorted lists

function mergeTwoLists(l1, l2) {

    if(! l1)return l2;

    if(! l2)return l1;

\


    if (l1.val < l2.val) {

        l1.next = mergeTwoLists(l1.next, l2);

        return l1;

    } else {

        l2.next = mergeTwoLists(l1, l2.next);

        returnl2; }};Copy the code

To merge two ordered lists, we only need to consider the current value of the largest and the first, and then compare the size of the next number of the largest list and the current number of the other list again, recursing until one is completely sorted. Just put the rest of the other party’s data behind it.

3. To give you the head of a linked list, rotate the list and move each node to the right by k **. 61. Rotate linked lists

function rotateRight(head, k) {

    if (k === 0| |! head || ! head.next) {return head;

    }


    let count = 1;


    let cur = head;

    while (cur.next) {

        count++;

        cur = cur.next;

    }


    let index = count - k % count;


    if (index === count) {

        return head;

    }


    cur.next = head;

    while (index > 0) {

        index--;

        cur = cur.next;

    }


    const ret = cur.next;

    cur.next = null;

    return ret;

};
Copy the code

When you first look at a rotated list, you might think it’s the same thing as a flipped list. If you flip it, you flip it backwards. If you rotate it, you might move the last few elements to the front.

I broke this problem down into four steps

  1. Find the total length of the linked list;
  2. We calculate the difference between the total length of the list, minus k, but given that k might be larger than the total length, we do a remainder operation, and that’s where we’re going to cut the list later;
  3. Link the end of the list to form a closed loop, so that you don’t have to cut the end of the list, but go to the front and join the end of the list.
  4. The rotation of the linked list is achieved by cutting from the position just calculated in Step 2.

5. Use scenarios of linked lists in the front end

1. The prototype chain

The front-end prototype chain is essentially a linked list, which can be passed from one class to another. When we insert a middle class called Connect into the Parent and Child classes, we use a similar link insertion function. We set the Connect prototype to Parent. And set the prototype of Child to Connect.

2. Chain programming

A lot of times when you’re maintaining some ancestral code, you don’t have to change the original code, because you can fix a bug with a small change and you can create more bugs, but what if the original data structure changes? At this time we can add a format conversion method, write a new method, the current data structure into the original data structure for use. This is also the chain programming popular around the world a bright spot.

Code word is not easy, like small partners can point to support ~!