Make writing a habit together! This is the 11th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Hello, I’m Yang Chenggong.

In the last article we introduced the concept of linked lists and then implemented the push and removeAt methods. These two methods are just basic features, but the way they are implemented is crucial. Because we understand the principles of these two methods, we can understand how linked lists achieve “ordered collections”.

If you are still feeling a little dizzy, please read the previous article: Angry Liver JavaScript Data Structures – Linked Lists (part 1)

The code implemented in the previous article is as follows:

class Node {
  constructor(value) {
    this.value = value;
    this.next = undefined; }}class linkedList {
  constructor() {
    this.count = 0;
    this.head = undefined;
  }
  push(item) {
    // Add elements to the end
  }
  removeAt(index) {
    // Remove the element at the specified position}}Copy the code

Now let’s continue with this part and continue to improve the linked list function.

Perfect the linked list method

The list also needs to implement the following methods:

  • getItemAt: Gets the element at a specific position in the list
  • insert: Inserts an element at a specific position in the list
  • indexOf: Returns the index of the element in the linked list
  • remove: Removes an element from the list
  • isEmpty: Determines whether the linked list is empty
  • size: Determines the length of the list
  • toString: Returns a string of all the elements of the list

GetItemAt method

The getItemAt method gets the element under an index in the linked list. It takes one parameter, index, to indicate the index.

The value of index is a number, but the value must be greater than or equal to zero and less than or equal to the length of the list in order to be a valid index in the list.

In fact, this method is relatively simple, just loop through until you find the target element.

getItemAt(index) {
  if(index >= 0 && index <= this.count) {
    let current = this.head
    for(let i = 0; i < index; i++) {
      current = current.next
    }
    return current
  }
  return undefined;
}
Copy the code

If no element is found, return undefined.

The insert method

The insert method is used to insert an element anywhere in the list. It takes two arguments, the first item indicating the element to be inserted, and the second index indicating the position at which the element is inserted.

The index is the same as the index in the getItemAt method above, and the logic is the same. Make sure the index parameter is within a valid range.

The implementation code is as follows:

insert(item, index) {
  if(index >= 0 && index <= this.count) {
    let node = new Node(item)
    let current = this.head;
    if(index == 0) {
      node.next = current
      this.head = node
    } else {
      let previous = this.getItemAt(index - 1)
      current = previous.next
      node.next = current
      previous.next = node
    }
    this.count++;
    return true;
  }
  return false;
}
Copy the code

The removeAt method has one thing in common with the removeAt method in the previous article: first determine whether the index is 0, and then process it by case.

If zero, you simply create a new element, point the next of the new element to the original table header, and then assign the head attribute to the new element.

If greater than zero, we need to get the current element and the previous element. The former element can be obtained directly using the getItemAt method written above.

Next points the next element to the element at the index position, and the next attribute of the previous element points to the new element, thus linking the new element between the previous and current elements.

Finally, increment the count attribute, which represents the length of the list, by one.

Method indexOf

IndexOf takes an element as an argument, searches the list for the location of that element, and returns the index. If not, returns -1.

There is a key point here: element parameters are compared to those in the linked list to see if they are equal. If the element is of primitive type, it is equal to. If the element is a reference type, then different data is judged differently, so you need to customize the method of judging.

So we’ll modify our linkedList class to add a custom method that accepts class initialization arguments:

class linkedList {
  constructor(whereFn) {
    let defun = (value, next) = > value === next;
    this.equalFn = whereFn || defun
  }
}
Copy the code

The argument whereFn is a custom function that compares elements.

With the equalFn property, the indexOf method is implemented:

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

Loop convenience, with a custom method to determine whether two elements are equal, equal to terminate the loop return index.

The remove method

The remove method is used to remove an element that needs to be found in the list and removed.

With the indexOf method above, the remove method is simpler to implement:

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

IsEmpty, size method

These are easier:

isEmpty() {
  return this.count == 0
}
size() {
  return this.count;
}
Copy the code

The toString method

The toString method, like the array method of the same name, puts all the elements into a string and separates them with commas.

Here is the code implementation:

toString() {
  if(!this.head) {
    return ' '
  }
  let current = this.head
  let string = current.value
  for(let i = 0; i < this.count; i++) {
    string += `,${current.value}`
    current = current.next
  }
  return string
}
Copy the code

The logic is simply to loop over the length of the list and concatenate the strings.

Use the list

The complete list code is quite long, I put online address, please click online test

First instantiate, add two elements:

let linked = new linkedList();
linked.push("Beijing");
linked.push("Shanghai");
console.log(linked.toString()); // Beijing, Shanghai
Copy the code

Then insert Shenzhen at index 1:

linked.insert('shenzhen'.1)
console.log(linked.toString()); // Beijing, Shenzhen, Shanghai
Copy the code

Then look at the index of the element:

console.log(linked.indexOf('Shanghai')); / / 2
console.log(linked.indexOf('wuhan')); // -1
Copy the code

Finally remove the element:

linked.remove('shenzhen');
console.log(linked.toString()); // Beijing, Shanghai
Copy the code

The result is perfect, and you’re done!

conclusion

This is the end of the list. In fact, after learning the linked list, we previously encountered array performance problems, linked list is a very good alternative.

I suggest that you post the code must hand knock again, master the essence.

This article source public number: programmer success. This is the 10th chapter of JavaScript data structure and algorithm learning, this series will be updated for a month, welcome to pay attention to the official account, click “add group” to join our learning team ~