Introduction of the list

What is a linked list? A linked list is a dynamic data structure, which means that we can add and delete as many elements as we want, and it expands as needed. Why use linked lists? Here are some uses for linked lists:

• Because array storage is flawed: adding or deleting elements often requires moving them around. The list is not placed continuously in memory. The element points to the next element through the next attribute, so the list adds and deletes elements without moving them, just changing the pointing of next.
• In daily life, the most vivid chain list is the train. The head is the locomotive, and each car has a next to connect the next car. If you want to add or delete cars, you only need to change the next.
• When we use split chaining to resolve hash table conflicts, we also use linked lists to store elements with conflicting positions.
• There are two very important chains in JavaScript: the scope chain and the prototype chain. Learning about linked lists is also very helpful in understanding these two features of JavaScript.

Write linked list classes in JavaScript

To write a linked list class, we still use the constructor function method.

function LinkedList() {... }module.exports = LinkedList;
Copy the code

Unlike stacks and queues, the private variable of a linked list class is not an array, but a pointer head. This pointer is just a normal variable pointing to an object. In addition, we define the private variable Length to record the length of the list and a private constructor function Node to build the list element containing the next attribute

function LinkedLst() {
  const Node = function(element) {
    this.element = element;
    this.next = null;
  };
  
  let length = 0;
  let head = null;
}
Copy the code

So what does a linked list element look like in code? If a linked list has 4,7 elements successively, the list would look like this:

{
  element: 4.next: {
    element : 7.next: null}}Copy the code

The private variable head refers to the object with element 4, length is 2, and the constructor function Node is used only to create list elements.

Implement append and toString methods

Now that we know about private variables, let’s implement various class methods. We expect the linked list class to have append and toString methods, which append elements and convert to strings, to pass the following tests:

var linkedList = new LinkedList();
/ / add 4
linkedList.append(4);
/ / add 7
linkedList.append(7);
// To a string
expect(linkedList.toString()).toBe('4, 7');
Copy the code

If only to run the above test, it is very simple, just use an array, but note that we are implementing the list class, the data structure used must be a list, so when append(4), head should be:

{
  element: 4.next: null
}
Copy the code

When append(7), head should be:

{
  element: 4.next: {
    element : 7.next: null}}Copy the code

So, we wrote the following code:

this.append = function(element) {
  let node = new Node(element);
  let current;
  
  // If the list is empty, head points directly to the new element
  if (head === null) {
    head = node;
  } else {
    // If the list is not empty, move current to the last element
    current = head;
    while (current.next) {
      current = current.next;
    }
    // Then point the next attribute of the last element to the new elementcurrent.next = node; } length++; }...this.toString = function() {
  let current = head;
  let string = ' ';
  
  while (current) {
    string += current.element + (current.next ? ', ' : ' ');
    current = current.next;
  }
  return string;
}
Copy the code

Both methods iterate over the list:

while (current) {
  // Write the logic in the loop here. current = current.next; }Copy the code

If you’re not familiar with JavaScript, you might ask: What is current = cuuren.next? Let me explain it slowly. In JavaScript, variables are divided into primitive types and reference types. Object types are reference types, which means that when you create an object, you create a space in memory, and no matter how many other variables you pass, they all refer to the same block of memory:

var a = { name: 'Joe' };
b = a;
b.name = 'bill';
console.log(a); // {name: 'li si'}
Copy the code

So in linked lists, we can use head, current and other variables to point to a variable that exists in memory:

{
  element: 4.// head points to an object with element 4
  next: {
    element : 7.// current is a temporary variable whose pointer can be changed to traverse the list
    next: null}}Copy the code

So current = current. Next is equivalent to current pointing to an object with Element 4 and then pointing to an object with Element 7, because the latter hangs on the next property of the former, as in the code above. Now you understand! More detailed knowledge of reference types can be found on Google.

var linkedList = new LinkedList();
linkedList.append(4);
linkedList.append(7);
// Return null when removing elements in position less than 0
expect(linkedList.removeAt(-1)).toBe(null); To assert a / /
// Delete an element whose position is greater than the length of the list
expect(linkedList.removeAt(3)).toBe(null); / / assertions
// Remove the element at position 1 and return
expect(linkedList.removeAt(1)).toBe(7); / / allegation
// Remove the element at position 0 and return
expect(linkedList.removeAt(0)).toBe(4); / / 4
// There are no elements in the chain
expect(linkedList.toString()).toBe(' ');
Copy the code

Assertions 1 and 2 are exceptions and should be checked with conditional statements and skipped, while assertions 3 and 4 are normal and elements should be removed and returned.

The implementation code is as follows:

this.removeAt = function(position) {
  // Used to skip exceptions
  if (position > -1 && position < length) {
    let current = head;
    let previous = null;
    let index = 0;
    // Delete the header element
    if (position === 0) {
      head = current.next;
    } else {
      // Find the element at the specified location and have its preceding element join its next element
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      previous.next = current.next;
    }
    length--;
    return current.element;
  }
  return null;
}
Copy the code

The trick of this method is to find the element in the specified position, but the essence of this method is to iterate through the list, with the termination conditions being different:

while (index < position) {
  // Code logic. current = current.next; index++; }Copy the code

Implement insert method

Implement the insert method, which inserts the specified element at the specified location, and run the following tests:

var linkedList = new LinkedList();
expect(linkedList.insert(0.4)); To assert a / /
expect(linkedList.insert(1.7)); / / assertions
expect(linkedList.insert(0.14)); / / allegation
expect(linkedList.insert(-1.8)); / / 4
expect(linkedList.insert(4.8)); / / assert that five
expect(linkedList.toString()).toBe('14,4,7');
Copy the code

Assertions 1 and 3 are head insertions, assertions 2 are non-head insertions, and assertions 4 and 5 are abnormal illegal inputs. The implementation code is as follows:

this.inset = function(position, element) {
  // Used to skip illegal input, corresponding to the fourth and fifth assertions
  if (position > -1 && position <= length) {
    let node = new Node(element);
    let current = head;
    let previous = null;
    let index = 0;
    // Insert into the header, corresponding to the first and third assertions
    if (position === 0) {
      node.next = current;
      head = node;
    } else {
      // Insert into the non-header, corresponding to the second assertion
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      node.next = current;
      previous.next = node;
    }
    length++;
    return true
  }
  return false
}
Copy the code

The trick with this method is to look up the specified element in the linked list, and the rest is boring boundary judgment.

Implement indexOf methods

Implement the indexOf method, which returns an element at a specified location, to run the following tests.

const linkedList = new LinkedList();
linkedList.append(4);
linkedList.append(7);
expect(linkedList.indexOf(7)).toBe(1); To assert a / /
expect(linkedList.indexOf(8)).toBe(-1); / / assertions
Copy the code

Other methods are relatively simple and will not be repeated.

conclusion

To play with linked lists, there are the following skills:

• Determine the private variable and element structure, mainly a head pointer, and a constructor function Node, used to generate an object containing the next attribute.
• Learn how to traverse a linked list using a while loop through current = curren.next.
• Learn to use previous to record the previous node of the current node while traversing a linked list.
• Consider various boundary cases: empty linked lists, outside the search scope, and so on.

In addition to mastering the above techniques, it’s also important to get your hands dirty writing code! Let’s call it a day.