Hi, I’m Front-end Tutu. Now I will update an article every week, and share what I have learned with you. Or rather, a rematch. Without further ado, in this article we will talk about linked lists.

The list

Linked list data structures

First, arrays are the most commonly used data structures in our daily development. Elements are accessible through [], but arrays have obvious drawbacks. The size is fixed, and the cost of inserting or removing an element from the head or middle of an array is very high. Why do you say that? Because we’re moving elements.

A linked list is a collection of elements that store ordered items. Each element in the list consists of a node that stores the element itself (also known as a node) and a pointer to the next element.

A linked list is like a train. Each train is the node of the list, and the link between the train is a pointer.

A nice thing about linked lists is that you don’t have to move other elements around to add or remove them. But linked lists require Pointers, so you need to be aware of this when implementing lists.

Singly linked list

As usual, a data structure is represented by a class.

function equalFn(a, b) {
  return a === b;
}

class LinkedList {
  constructor() {
    this.count = 0; // The total number of nodes in the linked list
    this.head = undefined; // Reference to the first element
    this.equalFn = equalFn; // Compare functions}}Copy the code

In the code above, count is used to represent the number of nodes in the storage list. The head attribute holds a reference to the first node. The equalFn property is a function that compares nodes in a linked list for equality.

Next we will create the Node class, which is the Node in the linked list.

class Node {
  constructor(ele) {
    this.element = ele; // The value of the list node
    this.next = undefined; // Pointer to the next element}}Copy the code

The Node class has two attributes: Element and next.

Let’s take a look at the methods that one-way lists have.

• push(ele): Adds a node to the end of the list.
• insert(ele, position): Inserts a node to a specific location in the list.
• getElementAt(index): Gets the node at a location in the list, or returns it if it does not existundefined.
• remove(ele): Removes a node from a linked list.
• indexOf(ele): Checks the location of the node and returns if no node is found- 1.
• removeAt(position): Removes a node at a specific location in the linked list.
• isEmpty: Checks whether the linked list is empty and returns if it istrueAnd isn’t emptyfalse.
• size(): Returns the number of nodes in the linked list.
• toString(): returns the concatenated string of all linked list nodes.

Push method

When adding nodes to the end of the LinkedList object, there are two scenarios:

• If the linked list is empty, the first node is added.
• If the list is not empty, append nodes to the end of the list;

push(ele) {
    const node = new Node(ele);
    // The current node
    let current = "";
    if (this.head == undefined) {
      this.head = node;
    } else {
      current = this.head;
      while(current.next ! =undefined) {
        // Set current to iterate over the next element
        current = current.next;
      }

      // current. Next is undefined to indicate the end of the list, and the pointer property of the last node is set to the next element
      current.next = node;
    }
    this.count++;
  }
Copy the code

1. When adding a node to a linked list, ifheadforundefinedAdd the first element to the list.

Note that the next pointer to the last element of a one-way list always points to undefined or null.

2. When adding a node to a non-empty linked list, the last node is first found. You can only iterate through the list by referring to the first node until you find the last node.

To find the last element, loop through the list, so you need a variable current that points to the current node in the list. During cyclic access, if the pointer to the current element is undefined, the end of the list is reached. You then use the pointer to the last element to point to the node you want to add to the list.

const linked = new LinkedList();
linked.push(10);
linked.push(15);
linked.push(11);
console.log(linked.head);
// You can view it from the browser console
// Node {
// element: 10,
// next: Node {
// element: 15,
// next: Node {
// element: 11,
// next: undefined
/ /}
/ /}
// }
Copy the code

RemoveAt method

There are two ways to remove a node from a linked list:

1. Removes a node from a specific location.
2. Remove elements based on their value (more on that later).

There are two scenarios for removing a node from a linked list:

1. Remove the first element.
2. Remove other elements.

Here is the removeAt method.

removeAt(index) {
    // Verify that index is valid.
    if (index >= 0 && index < this.count) {
      // Get the first node
      current = this.head;

      // Delete the first element
      if (index === 0) {
        // Delete the first node by setting the second node to the first node
        this.head = current.next;
      } else {
        // A reference to the previous node of the current node
        let prev = "";
        for (let i = 0; i < index; i++) {
          prev = current;
          current = current.next;
        }
        // Delete the current node by skipping the current node by connecting the previous node to the next node of the current node
        prev.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
}
Copy the code

First verify that index is valid and return undefined if it is not. When you remove the first element, you point the head to the second node in the list and use the current variable to hold the first node in the list. Assigning the value of head to the value of current-next removes the first node.

To remove the last or middle node in the list. You iterate through the list until you find the destination. Note that current references nodes in the linked list all the time. There is also a variable prev, which represents the previous node of the current node. After the iteration finds the target location, the current variable is the node you want to remove. Remove a node by connecting the previous node of the current node to the next node of the current node. It’s easy to understand if you look at the picture below.

If it is the last element, the current variable is the last node in the list when it breaks out of the loop. The value of current. Next is undefined. Since the reference to the prev node is also retained, prev.next points to current. To remove current, change the value of prev.next to the value of current-next.

console.log(linked.removeAt(2)); / / 11
Copy the code

If you understand the example of removing a node from a linked list, the following operations are easy to understand.

GetElementAt method

Here is the getElementAt method.

getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      // Initialize the node variable, iterating from the first node in the list
      let node = this.head;
      for (let i = 0; i < index && node ! =undefined; i++) {
        node = node.next;
      }
      return node;
    }
    return undefined;
}
console.log(linked.getElementAt(1));
// Node {element: 15, next: undefined}
Copy the code

In the code above, we use a node variable to iterate through the list from the first node. Until the target index. At the end of the loop, the node variable is the node reference at the index position.

As you can see, some of the logic of the getElementAt method is similar to the removeAt method, so we can rewrite the removeAt method.

removeAt(index) {
    // Verify that index is valid.
    if (index >= 0 && index < this.count) {
      // Get the first node
      let current = this.head;

      // Delete the first element
      if (index === 0) {
        // Delete the first node by setting the second node to the first node
        this.head = current.next;
      } else {
        // Get the previous node
        let prev = this.getElementAt(index - 1);
        current = prev.next;
        prev.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
}
Copy the code

The insert method

Let’s implement the INSERT method, which can insert a node anywhere.

insert(ele, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(ele);
      if (index === 0) {
        // Reference to the first node
        const current = this.head;
        node.next = current;
        this.head = node;
      } else {
        const prev = this.getElementAt(index - 1);
        const current = prev.next;
        node.next = current;
        prev.next = node;
      }
      this.count++;
      return true;
    }
    return false;
}
Copy the code

First check if index is valid, similar to removeAt. If the location is valid, deal with different scenarios.

1. Scenario 1: Add a node at the first position in the list,currentIs the reference to the first node in the listnode.nextThe value of the setcurrent. Finally, theheadWas quoted asnode.

2. Scenario 2: Add a node to the middle or bottom of the list. First, iterate through the list to find the target location. At this point, it’s going to cycle toindex - 1Is the location before the new node is added. When the loop is over,prevIs the node before the node where you want to insert the node, andcurrentIs the node behind where you want to insert the node. inprevandcurrentInsert a new element between, first link the new node to the current node, then need to changeprevandcurrentLinks between. Also need toprev.nextPoint to thenodewithnodereplacecurrent.

Add a node to the last position, prev is the last node in the list, current is undefined. In this case, nodex.next points to current, and prev.next points to Node.

The procedure for adding an element to the middle of the list is as follows.In this case, insert the new elementprevandcurrentBetween elements. The first thing we need to do isnode.nextThe value of the pointcurrentAnd then theprev.nextIs set tonode.

linked.insert(20.2);
console.log(linked.head);
console.log(linked.getElementAt(2));
// Node {element: 20, next: undefined}
Copy the code

Method indexOf

The indexOf method takes the value of a node and returns its position if it is found in the linked list, otherwise -1.

indexOf(ele) {
    let current = this.head;
    for (let i = 0; i < this.count && current.next ! =undefined; i++) {
      if (this.equalFn(ele, current.element)) {
        return i;
      }
      current = current.next;
    }
    return -1;
}
Copy the code

The same. First, we need a variable current, whose value is head, to loop through the list. The elements are then iterated over, starting at head and ending at the end of the list. Then use equalFn to determine the equality function. It is important to note that the equalFn function only applies to primitive data types. If the node’s value is a reference type, you need to write your own judgment function. If the node in the current position is the node we are looking for, we return its position. If it was not found, -1 is returned to indicate that it was not found.

The remove method

The remove method is simpler to implement, using a combination of the reomoveAt and indexOf methods.

remove(ele) {
    const index = this.indexOf(ele);
    return this.removeAt(index);
}
Copy the code

IsEmpty, size, getHead methods

isEmpty() {
    return this.size() === 0;
}

size() {
    return this.count;
}

getHead() {
    return this.head;
}
Copy the code

The isEmpty and SIZE methods are implemented like queues. The getHead method simply returns the header element.

Clear method

The clear method simply sets the count and head values to the initialization values.

clear() {
    this.count = 0;
    this.head = undefined;
}
Copy the code

The toString method

The toString method simply takes the LinkedList object

toString() {
    if (this.head == undefined) {
      return "";
    }

    let objString = `The ${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current ! =undefined; i++) {
      objString = `${objString} -> ${current.element}`;
      current = current.next;
    }
    return objString;
}
Copy the code

The toString method is pretty much the same as the toString method for data structures, so I’m not going to go into too much detail here.

The overall code

function equalFn(a, b) {
  return a === b;
}

class Node {
  constructor(ele) {
    this.element = ele; // The value of the list node
    this.next = undefined; // Pointer to the next element}}class LinkedList {
  constructor() {
    this.count = 0; // The total number of elements in the list
    this.head = undefined; // Reference to the first element
    this.equalFn = equalFn;
  }

  push(ele) {
    const node = new Node(ele);
    let current = "";
    if (this.head == undefined) {
      this.head = node;
    } else {
      current = this.head;
      while(current.next ! =undefined) {
        // Set current to iterate over the next element
        current = current.next;
      }

      // current. Next is undefined to indicate the end of the list, and the pointer property of the last node is set to the next element
      current.next = node;
    }
    this.count++;
  }

  removeAt(index) {
    // Verify that index is valid.
    if (index >= 0 && index < this.count) {
      // Get the first node
      let current = this.head;

      // Delete the first element
      if (index === 0) {
        // Delete the first node by setting the second node to the first node
        this.head = current.next;
      } else {
        // Get the previous node
        let prev = this.getElementAt(index - 1);
        current = prev.next;
        prev.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

  getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      // Initialize the node variable, iterating from the first node in the list
      let node = this.head;
      for (let i = 0; i < index && node ! =undefined; i++) {
        node = node.next;
      }
      return node;
    }
    return undefined;
  }

  insert(ele, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(ele);
      if (index === 0) {
        // Reference to the first node
        const current = this.head;
        node.next = current;
        this.head = node;
      } else {
        const prev = this.getElementAt(index - 1);
        const current = prev.next;
        node.next = current;
        prev.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  indexOf(ele) {
    let current = this.head;
    for (let i = 0; i < this.count && current ! =undefined; i++) {
      if (this.equalFn(ele, current.element)) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }

  remove(ele) {
    const index = this.indexOf(ele);
    return this.removeAt(index);
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return this.count;
  }

  getHead() {
    return this.head;
  }
  
  clear() {
    this.count = 0;
    this.head = undefined;
  }

  toString() {
    if (this.head == undefined) {
      return "";
    }

    let objString = `The ${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current ! =undefined; i++) {
      objString = `${objString} -> ${current.element}`;
      current = current.next;
    }
    returnobjString; }}const linked = new LinkedList();
console.log(linked.size()); / / 0
linked.push(10);
linked.push(15);
linked.push(11);
console.log(linked.removeAt(2)); / / 11

console.log(linked.getElementAt(1)); / / 15

linked.insert(20.2);
console.log(linked.getElementAt(2)); / / 20

console.log(linked.getHead());
// Node {element: 10, next: Node}

linked.insert(9.0);
console.log(linked.getElementAt(0)); / / 9

console.log(linked.indexOf(9)); / / 0
console.log(linked.indexOf(20)); / / 3

console.log(linked.toString());
// 9 -> 10 -> 15 -> 20

console.log(linked.size()); / / 4

console.log(linked.remove(9)); / / 9

console.log(linked.toString());
// 10 -> 15 -> 20

linked.clear();
console.log(linked.isEmpty());
// true
Copy the code

Two-way linked list

The difference between a bidirectional and a unidirectional list is that each node also has a pointer to the previous node. That is, the first node points to the second node, which in turn points to the first node. Look at the picture below.

As you can see, each node of the bidirectional list has an extra pointer to the previous node (prev).

Let’s create a bidirectional linked list class.

class DoublyLinkedList extends LinkedList {
  constructor(equalFn) {
    super(equalFn);
    this.tail = undefined; // Reference to the last node}}Copy the code

Bidirectional linked list is a special kind of linked list, which has the properties of unidirectional linked list. We can use extends to inherit properties from the LinkedList class and add a tail property that holds a reference to the last node on the list.

class DoublyNode extends Node {
  constructor(ele, next) {
    super(ele, next);
    this.prev = undefined; // The pointer to the previous element}}Copy the code

DoublyNode is a special Node that not only inherits the properties of Node, but also needs to add a pointer to the prev property of the previous Node.

Now we’re going to rewrite a couple of methods.

The insert method

Inserting a node into a two-way list is similar to a one-way list. Unidirectional lists only need to control the next pointer, whereas bidirectional lists need to control the prev and next Pointers. Now we’ll override the INSERT method.

insert(ele, index) {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(ele);
      let current = this.head;

      // Scenario 1: Insert the first node or insert a node from the head
      if (index === 0) {
        if (this.head == undefined) {
          this.head = node;
          this.tail = node;
        } else {
          node.next = this.head;
          current.prev = node;
          this.head = node; }}else if (index === this.count) {
        // Scenario 2: Add a node from the end
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        // Scenario 3: Insert a node from the middle of a bidirectional list
        const prev = this.getElementAt(index - 1);
        current = prev.next;
        node.next = current;
        prev.next = node;
        current.prev = node;
        node.prev = prev;
      }
      this.count++;
      return true;
    }
    return false;
 }
Copy the code

In the code above, three scenarios are considered.

• Scenario 1: Insert a node to the first position in a two-way list, similar to the operation in a one-way list. The main difference is that we need to set a value for the pointer to the previous node,current.prevPointer toundefinedTo point to the new element,node.prevThe pointer is alreadyundefined, so there is no need to do any operations.

• Scenario 2: Adding a node to the end of a bidirectional list requires control over the pointer to the last node.currentReference the last node, and then establish the connection.current.nextPointer tonode(nodeIt’s already pointed atundefined),node.prevPoint to thecurrent. The last updatetail. It used to point tocurrentNow it’s pointing tonode.

• Scenario 3: Insert a node in the middle of a bidirectional list, just like a single list. withLinkedListinheritedgetElementAtMethod, iterating through the bidirectional linked list until the desired location. inprevandcurrentInsert nodes between. The firstnode.nextPoint to thecurrentAnd theprev.nextPoint to thenode. And then you have to link them all together,current.prevPoint to thenode.node.prevPoint to theprev.

RemoveAt method

Removing a node from a bidirectional list is similar to a unidirectional list. The difference is that you need to set the pointer to the previous position.

removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;

      // Scenario 1: Delete the first node
      if (index === 0) {
        this.head = current.next;
        if (this.count === 1) {
          this.tail = undefined;
        } else {
          this.head.prev = undefined; }}else if (index === this.count - 1) {
        // Scenario 2: Delete the node at the last position
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = undefined;
      } else {
        // Scenario 3: Delete the middle node
        current = this.getElementAt(index);
        const prev = current.prev;
        prev.next = current.next;
        current.prev.next = prev;
      }
      this.count--;
      return current.element;
    }
    return undefined;
}
Copy the code

Again, we’re dealing with three different scenarios.

• Scenario 1: Remove the first node.currentIs the first node in a bidirectional linked list, and it is also the node to be deleted. What needs to happen is changeheadA reference to it fromcurrentChange to the next node. To updatecurrent.nextA pointer to the previous node (of the first nodeprevA pointer isundefined). Therefore, thehead.prevWas quoted asundefined(because theheadAlso points to the new first node in the bidirectional list. You need controltailCan check whether there is only one node in the bidirectional list, if there is only one nodetailSet toundefined.

• Scenario 2: Remove the node from the last location. We have the last nodetail, there is no need to iterate through the list to find the last node. directtailThe value is assigned tocurrent. Then,tailUpdate to the penultimate element of the bidirectional list. Then put thenextPointer updated toundefined.

• Scenario 3: Delete a node from the middle of the bidirectional list. The first step is to iterate through the bidirectional list to find the location of the node.currentThe variable is the node to be deleted. throughprev.nextPoint to thecurrent.next“, just skip it. In the end,current.prev.nextPoint to theprev.

The overall code

class DoublyNode extends Node {
  constructor(ele, next) {
    super(ele, next);
    this.prev = undefined; }}class DoublyLinkedList extends LinkedList {
  constructor(equalFn) {
    super(equalFn);
    this.tail = undefined;
  }

  push(ele) {
    const node = new DoublyNode(ele);
    if (this.head == undefined) {
      this.head = node;
      this.tail = node; / / new
    } else {
      / / new
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.count++;
  }

  insert(ele, index) {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(ele);
      let current = this.head;

      // Scenario 1: Insert the first node or insert a node from the head
      if (index === 0) {
        if (this.head == undefined) {
          this.head = node;
          this.tail = node;
        } else {
          node.next = this.head;
          current.prev = node;
          this.head = node; }}else if (index === this.count) {
        // Scenario 2: Add a node from the end
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        // Scenario 3: Insert a node from the middle of a bidirectional list
        const prev = this.getElementAt(index - 1);
        current = prev.next;
        node.next = current;
        prev.next = node;
        current.prev = node;
        node.prev = prev;
      }
      this.count++;
      return true;
    }
    return false;
  }

  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      // Scenario 1: Delete the first node
      if (index === 0) {
        this.head = current.next;
        if (this.count === 1) {
          this.tail = undefined;
        } else {
          this.head.prev = undefined; }}else if (index === this.count - 1) {
        // Scenario 2: Delete the node at the last position
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = undefined;
      } else {
        // Scenario 3: Delete the middle node
        current = this.getElementAt(index);
        const prev = current.prev;
        prev.next = current.next;
        current.next.prev = prev;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

  indexOf(ele) {
    let current = this.head;
    let index = 0;
    while(current ! =undefined) {
      if (this.equalFn(ele, current.element)) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  }

  getHead() {
    return this.head;
  }

  getTail() {
    return this.tail;
  }

  clear() {
    super.clear();
    this.tail = undefined;
  }

  toString() {
    if (this.head == undefined) {
      return "";
    }
    let objString = `The ${this.head.element}`;
    let current = this.head.next;
    while(current ! =undefined) {
      objString = `${objString} -> ${current.element}`;
      current = current.next;
    }
    return objString;
  }

  inverseToString() {
    if (this.tail == undefined) {
      return "";
    }

    let objString = `The ${this.tail.element}`;
    let prev = this.tail.prev;
    while(prev ! =undefined) {
      objString = `${objString} -> ${prev.element}`;
      prev = prev.prev;
    }
    returnobjString; }}const list = new DoublyLinkedList();

console.log(list.isEmpty()); // true
list.push(10);
list.push(11);
list.push(12);
console.log(list.size()); / / 3

console.log(list.toString());
// 10 -> 11 -> 12

console.log(list.removeAt(list.size() - 1));
console.log(list.inverseToString());
/ / 11 - > 10

console.log(list.size());/ / 2

console.log(list.toString());
/ / 10 - > 11
Copy the code

The advantage of a bidirectional list is that starting from any node in the list, it is easy to access both the preceding and the following nodes. You can also iterate from the head or tail.

Disadvantages: Increased the difficulty of deleting, need to allocate a pointer storage space.

Circular linked list

A circular list is a combination of single and double lists. The reference can be one-way or two-way. The difference with a bidirectional list is that the pointer (tail.next) to the next node is not undefined, but to the first node head.

Tail. next points to head, and head.prev points to tail.

class CircularLinkedList extends LinkedList {
  constructor(equalFn) {
    super(equalFn); }}Copy the code

CircularLinkedList does not have any additional attributes. It simply inherits the LinkedList class and overrides the methods to be overwritten.

The insert method

The logic of inserting a node into a circular list is the same as that of inserting an element into a single list, except that the next pointer to the end of the circular list points to the head node.

insert(ele, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(ele);
      let current = this.head;

      if (index === 0) {
        if (this.head == undefined) {
          this.head = node;
          node.next = this.head;
        } else {
          node.next = current;
          current = this.getElementAt(this.size());
          this.head = node;
          current.next = this.head; }}else {
        // Same as unidirectional lists
        const prev = this.getElementAt(index - 1);
        node.next = prev.next;
        prev.next = node;
      }
      this.count++;
      return true;
    }
    return false;
}
Copy the code

Let’s look at the different scenarios.

• Scenario 1: Insert a node at the first position in the circular list. If the circular list is emptyheadThe value of the assigned tonodeAnd put the last node withheadLink it up. And this node right here is thetanodeAnd at the same timehead.

• Scenario 2: Insert a node at the first position of a non-empty circular linked list. First of all, we need to putnode.nextPoint to thehead(The current variable). And then usegetElementAtMethod and pass in the length of the circular list as an argument to update the header node tonodeNode, and then the last nodecurrentPoint to the new head node.

If a node is inserted in the middle of a circular list, the code is exactly the same as in the LinkedList, because no changes are made to the first and last nodes in the circular list.

RemoveAt method

removeAt(index) {
    if (index >= 0 && index <= this.count) {
      let current = this.head;
      if (index === 0) {
        if (this.size() === 1) {
          this.head = undefined;
        } else {
          / / new
          const removed = this.head;
          current = this.getElementAt(this.size());
          this.head = this.head.next;
          current.next = this.head;
          // Change the current reference, since this value will be used in subsequent returns to indicate the removal of the element's valuecurrent = removed; }}else {
        / / the same
        const prev = this.getElementAt(index - 1);
        current = prev.next;
        prev.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
}
Copy the code

To remove a node from a circular list, only the second scenario needs to be considered, which is to modify the head node of the circular list.

• Scenario 1: Delete an element from a circular list with only one nodeheadThe value of the changeundefined.
• Scenario 2: Remove the first element from a non-empty list, save the current one firstheadThe node reference will be removed from the circular linked list. Next, get the last node in the circular list, which is stored incurrentVariable. The next thing to do is to start linking the point of the new node. First, theheadPoint to the second node, and then point to the last nodehead. The last updatecurrentVariable, since the value of the deleted node is also returned to indicate that the node has been removed.

The overall code

class CircularLinkedList extends LinkedList {
  constructor(equalFn) {
    super(equalFn);
  }

  push(ele) {
    const node = new Node(ele);
    let current;
    if (this.head == undefined) {
      this.head = node;
    } else {
      current = this.getElementAt(this.size() - 1);
      current.next = node;
    }

    node.next = this.head;
    this.count++;
  }

  insert(ele, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(ele);
      let current = this.head;

      if (index === 0) {
        if (this.head == undefined) {
          this.head = node;
          node.next = this.head;
        } else {
          node.next = current;
          current = this.getElementAt(this.size());
          this.head = node;
          current.next = this.head; }}else {
        const prev = this.getElementAt(index - 1);
        node.next = prev.next;
        prev.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  removeAt(index) {
    if (index >= 0 && index <= this.count) {
      let current = this.head;
      if (index === 0) {
        if (this.size() === 1) {
          this.head = undefined;
        } else {
          const removed = this.head;
          current = this.getElementAt(this.size());
          this.head = this.head.next;
          current.next = this.head;
          // Change the current reference to return and remove the nodecurrent = removed; }}else {
        / / the same
        const prev = this.getElementAt(index - 1);
        current = prev.next;
        prev.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined; }}Copy the code

Order list

An ordered list is a list structure that keeps the nodes ordered.

const Compare = {
  LESS_THAN: -1.BIGGER_THAN: 1};function defaultCompare(a, b) {
  if (a === b) {
    return 0;
  }

  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

class SortedLinkedList extends LinkedList {
  constructor(equalFn) {
    super(equalFn);
    this.compareFn = defaultCompare; }}Copy the code

The SortedLinkedList class inherits all properties and methods from the LinkedList class. But this class is special and requires a function compareFn to compare nodes. Returns 0 if the nodes have the same. Returns -1 if the first element is less than the second, 1 otherwise.

The insert method

insert(ele) {
    if (this.isEmpty()) {
      return super.insert(ele, 0);
    }

    const pos = this.getIndexNextSortedEle(ele);
    return super.insert(ele, pos);
}

getIndexNextSortedEle(ele) {
    let current = this.head;
    let i = 0;
    for (; i < this.size() && current; i++) {
      const comp = this.compareFn(ele, current.element);
      if (comp === Compare.LESS_THAN) {
        return i;
      }

      current = current.next;
    }
    return i;
}
Copy the code

In this insert method, there is no index parameter. The position of the insert node is controlled internally because it is an ordered linked list. If the ordered list is empty, call the insert method on the parent LinkedList directly and pass 0 as index. If it is not empty, it knows the correct location to insert the element and calls the Insert method on the LinkedList class, passing in that location to preserve the order of the list.

To get the correct location of the node to insert, a getIndexNextSortedEle method is created. In this method, you iterate through the entire ordered list until you find where to insert the node or iterate through all the nodes. In the latter scenario, the index returned is the length of the ordered list (with the node inserted at the end). CompareFn is then used to compare the nodes passed into the constructor. When the node to be inserted is smaller than the node of current, the position of the insertion node is found.

Other methods simply call methods in the LinkedList class.

The overall code

const Compare = {
  LESS_THAN: -1.BIGGER_THAN: 1};function defaultCompare(a, b) {
  if (a === b) {
    return 0;
  }

  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

class SortedLinkedList extends LinkedList {
  constructor(equalFn) {
    super(equalFn);
    this.compareFn = defaultCompare;
  }

  push(ele) {
    if (this.isEmpty()) {
      super.push(ele);
    } else {
      const index = this.getIndexNextSortedEle(ele);
      super.insert(ele, index); }}insert(ele) {
    if (this.isEmpty()) {
      return super.insert(ele, 0);
    }

    const pos = this.getIndexNextSortedEle(ele);
    return super.insert(ele, pos);
  }

  getIndexNextSortedEle(ele) {
    let current = this.head;
    let i = 0;
    for (; i < this.size() && current; i++) {
      const comp = this.compareFn(ele, current.element);
      if (comp === Compare.LESS_THAN) {
        return i;
      }

      current = current.next;
    }
    returni; }}const list = new SortedLinkedList();
list.push(10);
list.push(9);
list.insert(8);

console.log(list.toString());
// 8 -> 9 -> 10
Copy the code

Coordinate with other data structures

Linked lists can also be used as internal data structures to create other data structures. Examples are stacks, queues, and double-endian queues.

class StackLinkedList {
  constructor() {
    this.items = new DoublyLinkedList();
  }

  push(ele) {
    this.items.push(ele);
  }

  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items.removeAt(this.size() - 1);
    returnresult; }}Copy the code

The StackLinkedList class uses a two-way linked list to store data. The reason is, for the stack. You can add or remove elements from the tail. A bidirectional list has a reference to tail, the last node. Therefore, it can be retrieved without iterating through the entire bidirectional list node. Bidirectionally linked lists can capture nodes at the head and tail, thus reducing the cost of the process.

class StackLinkedList {
  constructor() {
    this.items = new DoublyLinkedList();
  }

  push(ele) {
    this.items.push(ele);
  }

  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items.removeAt(this.size() - 1);
    return result;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.getElementAt(this.size() - 1).element;
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return this.items.size();
  }

  clear() {
    this.items.clear();
  }

  toString() {
    return this.items.toString(); }}const stackList = new StackLinkedList();

console.log(stackList.isEmpty());
stackList.push(10);
stackList.push(11);
console.log(stackList.toString());
/ / 10 - > 11

stackList.push(12);
console.log(stackList.toString());
// test.js:467 10 -> 11 -> 12

stackList.pop();
console.log(stackList.toString());
/ / 10 - > 11

console.log(stackList.peek()); / / 11
Copy the code

It’s really just calling a method on a two-way list.

conclusion

Linked lists are much more complex to operate than stacks and queues. Because you control the next and prev Pointers, you need to be extremely careful when manipulating linked lists. In my opinion, I would think of a linked list as an iron chain. As you work with linked lists, think of the next and prev Pointers as linked buttons. This is my idea 😅.

All right! Writing is not easy, if you like it, I hope you give me a praise! It’s about one post a week. If have where wrong, welcome everybody big guy gives directions a lot.