This article introduces you to the necessary front-end data structures – linked lists

This is the first day of my participation in Gwen Challenge

Dudu dudu, let’s ride with the blogger! 😊 attached at the end of the article related topics

Not only the graphic explanation, the notes are also very clear oh! :thumbsup:

[TOC]

What is a linked list

A linked list is a collection of nodes, each of which has a pointer to its next node. For example, like the little train pictured above, each carriage is connected by a rope. Each carriage is a node, and the connection between the carriages is the pointer :heart:

So once you know what a linked list is, a lot of people think, well, what’s the difference between this and an array? Isn’t array manipulation more convenient?

Arrays are fixed in size, and inserting or removing items from the beginning or middle of an array is expensive because it requires moving elements (the same is true behind the scenes, despite all the API we’ve learned).

1.1 Advantages of linked lists

One advantage of linked lists over traditional arrays is that adding or removing elements does not require moving other elements ==. In this way, the time complexity of add and remove operations == is O(1). The following figure is a schematic diagram of inserting nodes into a one-way linked list. We only need to change the next pointer of the previous node and change the next pointer of the new node to join the list

1.2 Disadvantages of linked lists

In contrast to an array, when accessing an element, an array can be accessed directly through the index, while in a linked list, accessing an element requires iterating through the list from the starting point until the desired element is found. So the time complexity of access falls between O(1) and O(n)

1.3 Time complexity comparison of each operation between unidirectional linked list and array

List operation	Maximum time complexity	An array of operating	Maximum time complexity
Search (access)	O(n)	Search (access)	O(1)
Insert	O(1)	Insert	O(n)
Remove (remove)	O(1)	Remove (remove)	O(n)
Append (add)	O(1)	Append (add)	O(1)

1.4 Classification of linked lists

There are three types: unidirectional, bidirectional and circular lists

1.4.1 Unidirectional linked lists

1.4.2 Bidirectional linked lists

1.4.3 Circular linked lists

2. Use JS to implement linked lists

Now that we know what a linked list is, we can use JS to implement related operations on a linked list

2.1 Unidirectional linked lists

2.1.1 Creating a one-way linked list

Here is the basic skeleton of a LinkedList

class LinkedList {
    constructor() {
        // List length size
        this.size = 0;
        this.head = null;
    }
    // Add the list entry
    append(element){}// Insert the linked list entry
    appendAt(position, element){}// Deletes the specified list item
    remove(element){}// Delete the list entry at the specified location
    removeAt(position){}// Find the specified element index
    indexOf(element){}// Flip the linked list
    reserve(){}// Get the node
    getNode(index){}}/ / test
let l1 = new LinkedList();
Copy the code

Linked list data structures also require a Node helper class. The Node class represents the items to be added to the list. It contains an Element attribute, which is the value to add to the list, and a next attribute, which is a pointer to the next node item in the list.

/ / the node class
class Node {
    constructor(element) {
        this.element = element;
        // Add a pointer
        this.next = null}}Copy the code

Another important point is that we also need to store a reference to the first node. To do this, we can store the reference in a variable called head, and we’ll implement the method for filling in the LinkedList class.

• append(element): Adds a new item to the end of the list
• appendAt(position, element): Inserts a new item to a specific location in the list
• remove(element): Removes an item from the list
• removeAt(position): Removes an item from a specific position in the list
• getNode(index): Gets a node at a location
• reserve(): reverses the linked list

2.1.2 Obtaining nodes in the Linked List

I wrote this first because there are many methods that use this function later! In fact, you can also not separate encapsulation into a function, save personal habits

Pass in the position of the node that you want to find, through the for loop, keep pointing current to the next bit until index is reached, break out of the for loop, and return the current node :orange:

getNode(index) {
    // bounds determine whether the parameter passed is within the length range of the list
    if (index < 0 || index >= this.size) {
        throw new Error('out')}let current = this.head;
    // Continuously move current to the next digit until index-1 is reached
    // This is a loop loop
    for (let i = 0; i < index; i++) {
        current = current.next;
    }
    // Finally return to the node
    return current
}
Copy the code

2.1.3 Append elements to the end of the list

There are two scenarios:

1. The list is empty and the first element is added
2. The list is not empty. Append elements to it

Get the last node of the list by using the getNode method in the previous part. Let the next pointer of the last node point to the newly created node node, so that the list is connected in series. Finally, let the length of the list add itself.

append(element) {
    // Add attributes via instantiation
    let node = new Node(element);
    // Add operations
    if (this.head === null) {
        this.head = node;
    } else {
        let current = this.getNode(this.size - 1);
        // Next of the last node points to the newly created node
        current.next = node
    }
    // Add the linked entry, the size increases
    this.size++;
}
Copy the code

Note that node creation is done by using the new operator. Node is constructed as an object with its own value, Element, and a pointer to next. The next pointer to the newly created node defaults to null

2.1.4 Insert an element anywhere in the list

Because you insert elements by location, you first determine whether the location is out of bounds. If the boundaries are crossed, you can simply throw an error. Again, there are two scenarios:

In the first scenario, we need to add an element at the beginning of the list, which is the first position, make the newly created node next pointer to the head node, which is this.head, and set the newly created node as the head node :tada:

The second scenario: non-starting insertion. First, we need to find the previous node pre, and make the newly created node point to the next node pre. Next, and make the next pointer of the Pre node point to the newly created node :apple:

// Insert the linked list entry
appendAt(position, element) {
    // boundary judgment
    if (position < 0 || position > this.size) {
        throw new Error('position out range')}// instantiate create node
    let node = new Node(element);
    // Start insert
    if (position === 0) {
        node.next = this.head;
        this.head = node;
    } else {
        // Find the previous node where you want to insert
        let pre = this.getNode(position - 1);
        // Make the newly created node point to the next node from the current previous node
        node.next = pre.next;
        // Make the previous node point to the newly created nodepre.next = node; }}Copy the code

2.1.5 Removing an element from a linked list (by specific location)

There are also two scenarios for removing elements: removing the first element, and removing any element other than the first. Again, we need to do the boundary judgment first, throwing errors outside the length of the list. :banana:

The first scenario is very simple, since the first node is removed, you just need to have the head point to the second element in the list

Now, suppose we want to remove the last item in the list or one of the middle items. First we need to get the previous node of the deleted node and make the next pointer of this node point to the next node of the deleted node. The discarded elements are then discarded in computer memory, waiting to be scavenged by the garbage collector. :pear:

// Delete the list entry at the specified location
removeAt(position) {
    // If the length of the list is exceeded, an error is thrown
    if (position < 0 || position >= this.size) {
        throw new Error('position out range')}let current = this.head
    if (position === 0) {
        // If the first node is deleted, make head point to the next node
        this.head = current.next;
    } else {
        // Get the previous node of the deleted location
        let pre = this.getNode(position - 1); 
        // current indicates the deleted node
        current = pre.next;
        // Make the previous node point to the next node after the deleted node
        pre.next = current.next;
    }
    // The length is reduced
    this.size--;
}
Copy the code

2.1.6 Finding the position of an element in the linked list

We need a variable to help us loop through the list, current in the code, whose initial value is head. The for loop iterates through the list to determine whether the value of the current position is equal to the search value, and if so, returns its position; If not, keep going. If the end of the for loop does not pop up, the end of the list is reached, that is, the element does not exist in the list, and -1 is returned. :heart_decoration:

// Find the specified element index
indexOf(element) {
    // The current list head node
    let current = this.head; 
    // Iterate through the list
    for (let i = 0; i < this.size; i++) {
        if (current.element === element) {
            return i
        }
        // Move down in sequence
        current = current.next; 
    }
    return -1;
}
Copy the code

2.1.7 Removing an element based on its value

Now that we have indexOf, we can pass in the element’s value, find its location, and then call removeAt and pass in the location to remove the element :deciduous_tree:

remove(element) {
    // Get the position of the element to be deleted in the list
    let index = this.indexOf(element)
    if(index! = -1 ) {
        // Remove the node at the specified location using the following removeAt method
        this.removeAt(index)
    }else {
        // Delete elements that do not exist, throw an error
        throw new Error('element no found')}}Copy the code

2.1.8 Reverse the linked list

Reverse lists are common in LeetCode and can be found in various interview questions. So, in passing, I’ll write the following

First, we define two Pointers: prev and current, with current before prev after. Set the next pointer of current to prev each time to achieve a local inversion. After the partial inversion is completed, prev and Current move forward one position at the same time, and cycle the process until current reaches the end of the list. The animation is as follows

reserve() {
    let prev = null;
    let current = this.head;
    while (current) {
        // Save the current next bit
        let next = current.next;
        // Make the current node point to the previous node prev
        current.next = prev;
        // After the swap, let the prev move to the next bit, which is current
        prev = current;
        current = next;
    }
    // Return the flipped list
    this.head = prev
}
Copy the code

2.2 Bidirectional linked lists

The difference between a bidirectional list and a unidirectional list is that a node in a unidirectional list has only a pointer to the next node in the chain, while in a bidirectional list, there are two Pointers, one pointing to the previous element and one to the next element, as shown below:

2.2.1 Creating a bidirectional linked list

There is an extra pointer to the previous element as opposed to a one-way list, so there are some changes to be made in the code

// a list node
class Node {
    constructor(element) {
        this.element = element
        this.next = null
        this.prev = null/ / new}}// Two-way linked list
class doubleLinkedList {
    constructor () {
        this.size = 0
        this.head = null
        this.tail = null/ / new
    }
    // Here is how to write next
}
Copy the code

Advantages of bidirectional lists: Access to the next or == before == element of a particular node. In a one-way list, if you iterate over the list and miss the element you’re looking for, you need to go back to the beginning of the list and start over:

Note: There is a tail attribute in the doubleLinedList class that holds a reference to the last item in the list.

2.2.2 Obtaining nodes in the Linked List

The method of obtaining linked list by position is the same as that in one-way linked list. Remember to jump back and have a look! :heart:

// Get a node at a location, same as a one-way list
getNode(index) {
    if (index < 0 || index >= this.size) {
        throw new Error('out')}let current = this.head
    for(let i = 0; i < index; i++) { current = current.next }return current
}
Copy the code

2.2.3 Append nodes to the end of the list

Believe that you see here, should know what to do first! There are two cases

Case one: The linked list is empty

Second case: Linked lists are not empty

In the first case, we simply point head and tail to the newly created node

In the second case, which is a bit different from the one-way list, we need to set the precursor pointer.

Make the next pointer of the last node point to the new node, and make the prev pointer of the new node point to the previous node (i.e. the last node before joining). Finally, remember to move tail to the last node and increment the size! Here’s the schematic, clear and clear :thumbsup:

append(element) {
    // Create a node
    let node = new Node(element)
    // Save the current pointer to the last element
    let tail = this.tail
    // If the list is empty, the new node will be the first
    if(this.head === null) {
        // Head and tail are nodes
        this.head = node
        this.tail = node
    }else {
        // Make the next pointer to the last element point to node
        tail.next = node
        // Make node's precursor pointer to tail the last node
        node.prev = tail
        // Finally update tail to point to the last element node
        this.tail = node
    }
    this.size++
}
Copy the code

2.2.4 Inserting a node into a Linked list

Inserting a new node into a two-way list is very similar to a one-way list. The difference is that one-way lists only need to control one NEXT pointer, whereas bidirectional lists control both next and prev Pointers

Let’s start with the first scenario: insert a new node at the first position in the list. If the list is empty, all you need to do is point head and tail to the new node. If not null, the current variable will hold a reference to the first element in the list, so simply make the next pointer to current, the prev pointer to current, and the head pointer to the first node. ==

Next comes the second scenario: tail insertion, which is somewhat similar to the previous one, but will not be repeated here

The final scenario is also a little more complicated: insert in the middle of the list

Using the getNode method we wrote earlier, we get the previous node, preNode, and the next node, current. We insert new elements between the current and preNode elements. First, the next pointer to node points to current, then the prev pointer to node points to preNode, and then the remaining two Pointers to node respectively.

// Insert the node
insert(position, element) {
    // The input position needs to be within the range
    if (position < 0 || position > this.size) {
        throw new Error('position out range')}// Create a node
    let node = new Node(element)
    // Save the first node as a variable
    let current = this.head
    // In the first case, insert in the most header
    if (position === 0) {
        // The list is empty
        if (!this.head) {
            this.head = node
            this.tail = node
        } else {
            // The linked list is not empty
            // Make node's next pointer point to the first node
            node.next = current
            // The first node has a precursor pointer to node
            current.prev = node
            // head points to the new first node
            this.head = node
        }
        this.size++
    } else if (position === this.size) {
        // Insert at the end
        // the current variable holds the last node
        current = this.tail
        // The next pointer to the last node points to the new node
        current.next = node
        // The new node has a precursor pointer to the previous node
        node.prev = current
        // tail moves to node
        this.tail = node
        this.size++
    } else {
        // Insert in the middle
        // Get the previous node of the insertion position
        let preNode = this.getNode(position - 1)
        // The current variable holds the next node of the preNode
        current = preNode.next
        // 1. Make the next pointer to node current
        node.next = current
        // 2. Set the prev pointer of node to the previous preNode
        node.prev = preNode
        // 3. Make the next pointer to preNode point to the new node
        preNode.next = node
        // 4. Set the current prev pointer to the new node
        current.prev = node
        this.size++
    }
}
Copy the code

Note: In our encapsulated getNode method, which is iterated from scratch anyway, we can actually optimize the process by iterating from the end when the position we are looking for is greater than half size, which improves performance.

2.2.5 Remove an element from a specific position in a linked list

In fact, the operation of bidirectional linked lists is similar to that of unidirectional linked lists, but there is only one more precursor pointer to operate one more pointer. For this method of deleting elements in specific positions, the most important thing we need to know is to remove the deleted node from the linked list, and then connect the linked list intact

Again, we need to break it down into 3 cases

Case 1: Delete the first node

The current variable holds a reference to the first node in the list that we want to remove. The first thing to change is the head reference, changing it from current to current-.next. We also need to update the current. Next pointer to the last element, so we need to determine whether the length of the list is 1. If it is 1, the list will be empty after the first node is deleted, so we need to set tail to NULL. The demo diagram is as follows:

The second case: delete the last node

Since we have the tail reference to the last node, we don’t need to get the last node via getNode, so we can also assign the tail reference to the current variable. Next, we need to update the reference to tail to the next-to-last element in the list and point the next pointer to null, as shown below:

Third case: delete intermediate nodes

First, we need to find the node to be deleted through the getNode method, save it in the current variable, and use preNode to indicate the previous node to be deleted. To remove it, we can skip it in the linked list by updating the references to prev.next and current.next-prev, so that the next pointer to prev points to current.next and the prev pointer to current.next points to prev, as shown below:

removeAt(position) {
    // The input position needs to be within the range
    if (position < 0 || position > this.size) {
        throw new Error('position out range')}let current = this.head
    // Delete the first node
    if (position === 0) {
        // make head point to the next digit
        this.head = current.next
        // If the length of the list is 1, the end of the list should be null
        if(this.size === 1) {
            this.tail = null
        }else {
            // The first node (current.next) after the node is deleted is null
            this.head.prev = null
        }
        this.size--
    }else if (position === this.size -1) {
        // Delete the last node
        // Let current save the node we want to delete
        current = this.tail
        // move tail to the first digit of the deleted node
        this.tail = current.prev
        // Set tail's next pointer to null so that the last node is discarded
        this.tail.next = null
        this.size--
    }else {
        // The deleted node
        let current = this.getNode(position)
        // Delete the previous node of the node
        let preNode = current.prev
        // Delete the previous node next points to its next node
        preNode.next = current.next
        // The prev of the latter node points to the preNode
        current.next.prev = preNode
        this.size--
    }
}
Copy the code

2.2.6 Find the position of an element in the linked list

This is done in the same way as a one-way list, with no changes :hamburger:

indexOf(element) {
    // The current list head node
    let current = this.head; 
    // Iterate through the list
    for (let i = 0; i < this.size; i++) {
        if (current.element === element) {
            return i
        }
        // Move down in sequence
        current = current.next; 
    }
    return -1;
}
Copy the code

2.2.7 Remove nodes based on element values

RemoveAt removeAt removeAt removeAt removeAt removeAt removeAt removeAt removeAt removeAt removeAt

// Delete elements based on their value
remove(element) {
    let index = this.indexOf(element)
    if(index ! = -1) {
        // Remove the node at the specified location using the following removeAt method
        this.removeAt(index)
    } else {
        // Delete elements that do not exist, throw an error
        throw new Error('element no found')}}Copy the code

2.2.8 Printing bidirectional linked lists

By walking through the list, concatenating the values of each node, it looks much clearer

Example: NULL<->1<->2<->3<->NULL

print() {
    let str = 'NULL<->';
    let current = this.head
    while(current ! = =null) {
        str += current.element + '< - >';
        current = current.next;
    }
    return str += 'NULL';
}
Copy the code

2.3 Unidirectional circular linked lists

A circular list is similar to a one-way list in that the node type is the same. The only difference is that when creating a circular list, the next pointer of the last node points to the first node

// Assume lastItem is the last node
lastItem.next = this.head
Copy the code

2.3.1 Creating a one-way circular linked list

The general structure is the same as that of a one-way list

class Node {
    constructor(element) {
        this.element = element
        this.next = null}}class CircleLinkedList {
    constructor() {
        this.size = 0
        this.head = null
    }
    // Add nodes at the end
    append(element) {}
    // Insert node at any position
    insert(position,element) {}
    // Delete nodes by location
    removeAt(position){}
    // Find the corresponding index of the element, the same as the one-way list
    indexOf(element) {}
    // Remove nodes based on element values, as in a one-way list
    remove(element) {}
    // Get node, same as unidirectional list
    getNode(index){}}Copy the code

2.3.2 Append nodes to the end of the list

If the list is empty, use head to point to a new node

In the second case, the list is not empty. Use getNode to get the last node of the list and make the next pointer point to the new node node

Note: the next pointer of the last node points to the head of the first node after executing the if judgment

append(element) {
    // Create a node
    let node = new Node(element)
    // The linked list is empty
    if (this.head === null) {
        this.head = node
    } else {
        // Get the last node
        let current = this.getNode(this.size - 1)
        current.next = node
    }
    In either case, keep it end to end
    node.next = this.head
    this.size++
}
Copy the code

2.3.3 Inserting a Node into a Linked List

Similarly, there are two scenarios ==

• When the insertion position is the first, unlike the operation of a one-way list, extra will be required to link the last node of the listnextThe pointer points to the new nodenode
• When you insert somewhere else, you can use the ternary operator to determine what the new node isnextStudent: Pointing rightnullIf it isnullNew nodeInsert it at the last node, the node’snextPointer to the first node, otherwise insert normally

insert(position, element) {
    // boundary judgment
    if (position < 0 || position > this.size) {
        throw new Error('position out range')}// instantiate create node
    let node = new Node(element);
    if (position === 0) {
        // node points to the previous first node
        node.next = this.head;
        // The head node is changed to the new node node
        this.head = node;
        let current = this.getNode(this.size - 1)
        current.next = this.head
        this.size++
    } else {
        // Find the previous node where you want to insert
        let prev = this.getNode(position - 1);
        // If prev.next is null point to head otherwise point to next
        node.next = prev.next == null ? this.head : prev.next
        // Make the previous node point to the newly created node
        prev.next = node;
        this.size++
    }
}
Copy the code

2.3.4 Deleting a node at a specific location from the linked list

Different from one-way linked lists, == when deleting the first node ==, the next pointing of the last node needs to be changed to point to the new first node. When deleting other nodes, it needs to determine whether the next pointing of the previous node of the following deleted node is null to proceed with the next operation

// Delete nodes by location
removeAt(position) {
    // If the length of the list is exceeded, an error is thrown
    if (position < 0 || position >= this.size) {
        throw new Error('position out range')}let current = this.head
    if (position === 0) {
        // If the first node is deleted, make head point to the next node
        let last = this.getNode(this.size - 1); 
        this.head = current.next;
        last.next = this.head
    } else {
        // Get the previous node of the deleted location
        let pre = this.getNode(position - 1); 
        // current indicates the deleted node
        current = pre.next;
        // Make the previous node point to the next node after the deleted node
        pre.next = current.next == null ? this.head : current.next;
    }
    // The length is reduced
    this.size--;
}
Copy the code

2.4 Bidirectional circular linked lists

Bidirectional lists differ from unidirectional lists in that they have an additional prev pointer from the first node to the last node

Bidirectional circular list and the front of the difference is not very big, this article will not expand to write, I believe that see the front of the detailed solution, must be able to complete their own

3. Related topics

A few topics on linked lists in Leetcode, with ac code attached

3.1 Reverse a linked list(Direct link oh!)

var reverseList = function(head) {
    let prev = null;
    let current = head;
    while (current) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev
};
Copy the code

3.2 Merge K ascending linked lists

var mergeKLists = function (lists) {
    if(! lists || ! lists.length)return null;
    let end = lists[0]
    let i = 1;
    while(i ! = lists.length) { end = mergeTwoLists(lists[i++], end) }return end
};

function mergeTwoLists(l1, l2) {
    // If one of them is empty, the other list is returned
    if(! l1)return l2
    if(! l2)return l1
    // Compare the list values in turn
    if (l1.val > l2.val) {
        // If the value of l2 is large, the next of L2 is recursively determined again
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    } else {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    }
};
Copy the code

3.3 Delete the penultimate node of the linked list

var removeNthFromEnd = function (head, n) {
    let node = head;
    let count = 0 ;
    // Calculate the list length
    while(node) {
        node = node.next;
        count++;
    }
    count = count - n - 1
    if(count == -1) {
        return head.next
    }else {
        node = head;
        while(count > 0) {
        node = node.next;
        count--;
    }
    }
    node.next = node.next.next
    return head
};
Copy the code

4. Summary

That’s all for this JavaScript implementation list, and I hope you learned a lot from it.

And that’s the end of today’s sharing!

References: javascript data structures and algorithms