What is a linked list?

  • Linked lists vs. Arrays: In most languages, arrays are fixed in size, and adding or removing elements from the beginning or middle of an array is expensive because of the need to move elements.
  • Each element in a linked list is not placed consecutively in memory and has no relation to its left and right elements.
  • Each element consists of a node that stores the element itself and a reference to the next element.
  • The advantage of linked lists, as opposed to arrays, is that you don’t need to move other elements when you add or remove them.
  • We can directly access any element anywhere in the array, but to access any element in the list, we need to iterate through the list from the starting point (the list header) until we find the desired element.

For example, a train is made up of a series of cars. Each car or car is connected to each other, and you can easily separate a car, change its position, add or remove it. Each carriage corresponds to the element of the linked list, and the docking buckle between carriages is the reference of the element.

Create a linked list class

const defaultCompare = function (a, b) { // a comparison function
  if (a === b) return 0;
  return a < b ? - 1 : 1;
}

class Node { // A helper class that represents the element we want to add to the list
  constructor(element, next) {
    this.element = element; // The element value
    this.next = next; // A pointer to the next element in the list}}class LinkedList { / / list
    constructor(equalsFn = defaultEquals) {
    this.equalsFn = equalsFn; // Compare elements in the linked list to be equal, default a===b
    this.count = 0; // The number of elements in the list
    this.head = undefined; / / headers}}Copy the code

Methods to create several linked lists

  1. Add an element to the end of the list
push(element) {
    const node = new Node(element); // Create the node item
    let current; // Declare a pointer to a temporary item in the list
    if (this.head == undefined) { // If the header is empty, the list is empty
      this.head = node; // Set the header equal to the current element. The next item is not passed, so undefined
    } else {
      current = this.head; // Make current equal to the first element
      while(current.next ! =null) { // As long as the next element of the current element is not false, the loop continues
        current = current.next;
      }
      current.next = node; // After finding the last element, make its next element equal to the element passed in
    }
    this.count++;// Add the total length
  }
Copy the code
  • First initialize the Node class, passing element as a value.
  • There are two cases of adding elements to the end of the list. One is when the list is empty, and the other is when the list has a value. In the latter case, since the list only has references to the header, when adding elements to the end of the list, we need to loop through the list until we find the last element.
  • If no value is added to the list, the first element is added to the list. The reference to the next item is not passed, so undefined
  • Then there is the second case, which first sets current equal to the head of the list, then loops through the list until the last element is found, and then makes the reference to the next item of the last element point to the node you want to add to the list.
  • And then I’ll just increment the total length
  1. Removes an element from a specific position
removeAt(index) {
    if (index >= 0 && index < this.count) { // Check the out-of-bounds value
      let current = this.head;
      if (index === 0) { // if it is a header
        this.head = current.next; // make the header equal to the next reference
      } else {
        letPrevious;for (let i = 0; i < index； i++) { // Well, start iterating ~~~
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
        // The next of the previous is the next of the present,,, (now inner OS: Who am I, where am I??) The current node is discarded in computer memory, waiting to be removed by the garbage collector
      }
      this.count--;// The length is reduced
      return current.element; // Returns the removed element
    }

    return undefined;
  }
Copy the code
  • Since this method needs to get the index of the removed element, we need to verify that the index is between 0 and the length of the list. If not, return undefined.
  • If you remove the first element in the list, make head point to the second element in the list. We use the current variable to create a reference to the first element in the list. The current variable is then a reference to the first element in the list. If you assign head to current. Next, the first element will be removed. We could also assign head directly to head.next without using current.
  • If we want to remove the last element of the list or one of the middle elements. You need to iterate through the list until you reach your destination.
  • After reaching the target location, the current variable becomes the node we want to remove from the linked list. Therefore, to remove the current element from the linked list, all you need to do is link previous.next to current. Next. The current node is then discarded in computer memory, waiting to be scavenged by the garbage collector.
  1. Loop through the list until you reach the destination
getElementAt(index) {
    if (index >= 0 && index <= this.count) return undefined; // Check the out-of-bounds value
    let node = this.head; // Default is equal to the table header
    for (let i = 0; i < index && node ! =null; i++) { // Well, start iterating ~~~
      node = node.next;
    }
    return node;
  }
Copy the code
  • In the remove method, we need to iterate through the list until we reach our target index index. The code snippet that loops to the target index is often used in linked list methods. Therefore, we can separate this part of logic into a separate approach so that we can reuse it in different places.
  • We can then refactor the Remove method using the getElementAt method we just created
if(index===0) {// The logic of the first position
} else {
    const previous = this.getElementAt(index - 1);
    current = previous.next;
    previous.next = current.next;
}
this.count--;
Copy the code
  1. Insert elements at any location
insert(element, index) {
    if (index >= 0 && index <= this.count) { // boundary processing
      const node = new Node(element); // instantiate the current element
      if (index === 0) { // If it is inserted in the header
        const current = this.head;// Declare a variable equal to the original header
        node.next = current;// The next reference to the passed element is equal to current
        this.head = node; // The current header is equal to the element passed in
      } else {
        const previous = this.getElementAt(index - 1);// Find the last value of the index passed in
        previous.next = node;// The previous reference is equal to the value passed in
        node.next = previous.next;// The next reference to the passed value is equal to the next reference to the previous value
        
      }
      this.count++;// The total length increases
      return true; // Finally returns true
    }
  return false; // Return false if the location is not found
}
Copy the code
  • So let’s do the usual boundary processing.
  • First, if it is inserted in the header, we declare a variable equal to the original header, make the first reference to the inserted element equal to the original variable, and make the current header equal to the element passed in.
  • If it’s in the middle or at the end of the list we need to use the getElementAt method to find the last element at the target location and make the last reference equal to the value passed in. The next reference to the passed value is equal to the next reference to the previous value. Be sure to add one to the total length to return true
  1. Returns the position of an element
indexOf(element) {
    let current = this.head; // is equal to the header of the table
    for (let i = 0; i < this.size() && current ! =null; i++) { // Loop over all elements
      if (this.equalsFn(element, current.element)) { // Find the first element equal to the current element
        return i;// return index
      }
      current = current.next;// If not, proceed to the next iteration
    }
    return - 1; // If none is found, return -1
  }
Copy the code
  • The indexOf method takes the value of an element and returns its position if it is found in the linked list, otherwise -1.
  • As always, we need a variable to help us loop through the list. The variable is current, whose initial value is head
  • The elements are then iterated over, starting at the head of the list and continuing to the length of the list. To ensure that runtime errors do not occur, we can verify that the current variable is null or undefined.
  • Loop through all elements until the first element equal to the current element is found, returning its position
  • If not, return -1
  1. Removes the element passed in
remove(element) { 
    const index = this.indexOf(element); // Find the first index of this element
    return this.removeAt(index); // Remove the element at the specified position by deleting it
  }
Copy the code
  • We already have a method for removing elements at a given location, and we have an indexOf method. Find its position using the indexOf method, and remove it using the method of deleting the specified position element.
  1. Check for empty, length, and get the list header
isEmpty() {
    return this.size() === 0;
  }
  size() {
    return this.count;
  }
  getHead() {
    return this.head;
  }
Copy the code
  • It’s relatively simple.
  1. Convert all elements to strings
toString() {
    if (this.head == null) { // If the list is empty, an empty string is returned
      return ' ';
    }
    let objString = `The ${this.head.element}`; // Create a variable equal to the element in the header
    let current = this.head.next; // is equal to the next reference in the header
    for (let i = 1; i < this.size() && current ! =null; i++) { // Loop over all elements
      objString = `${objString}.${current.element}`; // Make this string equal to the original string plus the current element
      current = current.next; // The current element equals the current next reference
    }
    return objString; // Finally return the string
  }
Copy the code
  • First, if the list is empty, we return an empty string.
  • If there is a value we initialize the string returned by the method with the value of the first element in the list.
  • We then iterate over all the other elements in the list, adding element values to the string.
  • Finally, return the string.

The last

  • That’s all for today’s notes, and I’ll write another article about various enhancements to linked lists when I have time. In conclusion, after reading this chapter, I think linked lists are more suitable for adding and deleting operations than arrays, while arrays are more suitable for storing some relatively fixed ordered collections.