Make writing a habit together! This is the 12th 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 previous two articles, we introduced linked lists in detail. We know that a linked list is an ordered set of elements that are independent but connected to each other. When we query an element, we must start at the top of the table and work backwards.

Bidirectional linked list is actually on the basis of linked list, added a “from the back forward” query function. Because the list can only be traced back to the beginning of the list. A bidirectional list allows you to start at the last element and work your way up.

So elements in a bidirectionally linked list have two references, one to the previous element and one to the next element.

Implement bidirectional linked lists

A bidirectional linked list is a type of linked list that provides basic functions. So to achieve bidirectional linked list, directly in the original linked list method can be expanded above.

We use ES6 class inheritance to implement bidirectional linked lists.

class doubLinkedList extend linkedList {
  constructor(whereFn) {
    super(whereFn)
    this.tail = undefined}}Copy the code

The basic code above is to add a tail attribute to the linkedList, representing the element reference to the tail. The role of the super method is to call the constructor of linkedList for full inheritance.

Add a prev attribute to the previous element in the list, so use inherited methods:

class doubNode extend Node {
  constructor(value) {
    super(value)
    this.prev = undefined}}Copy the code

Let’s see how bidirectional lists add and remove elements.

Update insert method

The insert method of a linked list article simply adds a next reference to the new element; A preV reference is also required for bidirectional list insertion. We do an update based on the insert method of linked list sections.

insert(item, index) {
  if(index >= 0 && index <= this.count) {
    let node = new doubNode(item)
    let current = this.head;
    if(index == 0) {
      // 1. Add logic first
      if(!this.head) {
        this.head = node
        this.tail = node
      } else {
        node.next = current
        current.prev = node
        this.head = node
      }
    } else if(index === this.count) {
      // 2. Add logic at the end
      current = this.tail
      current.next = node
      node.prev = current
      this.tail = node
    } else {
      // 3. Add logic in the middle position
      let previous = this.getItemAt(index - 1)
      current = previous.next
      previous.next = node
      node.prev = previous
      node.next = current
      current.prev = node
    }
    this.count++;
    return true;
  }
  return false;
}
Copy the code

To clarify, the current variable in the code represents the element at the index position.

The comment part of the code is the part to be modified, there are three parts, let’s talk about one by one.

The first to add

The first addition is adding the first element, depending on the case. If the list is empty, assign the head and tail attributes to new elements. Because the new element is both the header and the tail of the table.

If the list is not empty, the header and tail already exist. We assign next to the new element as the header, prev to the new element as the new element, and finally set the new element to the new header.

At the end of the add

The main change added at the end is the tail property. We first assign next at the end of the table to the new element, then prev of the new element to the end of the table, and finally assign the new element to the new end of the table.

Middle position add

An intermediate addition means that the insertion is not the first or the last. In this case, it means that neither the header nor the tail need to move, just associate the new element with the preceding and subsequent elements.

First, get the previous element of the index location, previous; And then get the index element current, which is previous.next. Now put the new element between them.

The method is to set the prev and next properties one by one.

Upgrade the removeAt method

The removeAt method is the same as the insert method above. You only need to change the prev and next attributes of the elements before and after the deletion, and change the tail attribute when the table tail is involved.

removeAt(index) {
  if (index >= 0 && index < this.count) {
    let current = this.head;
    if (index === 0) {
      // 1. Delete logic first
      if(! current) {return undefined;
      }
      this.head = current.next;
      if (this.count === 1) {
        this.tail = undefined;
      } else {
        this.head.prev = undefined;
      }
      this.head = current.next;
    } else if (index === this.count) {
      // 2. Delete logic at the end
      current = this.tail;
      this.tail = current.prev;
      this.tail.next = undefined;
    } else {
      // 3. Delete logic in middle position
      current = this.getItemAt(index);
      let previous = current.prev;
      previous.next = current.next;
      current.next.prev = previous;
    }
    this.count--;
    return current.value;
  }
  return undefined;
}
Copy the code

The commented part of the code is the part to be modified, as follows.

First remove

The first deletion is the deletion of the first element, depending on the circumstances.

If the list is empty, delete is meaningless, return undefined; If there is only one element, it will become an empty list when deleted, so set both the head and tail attributes to undefined. If the list length is greater than 1, simply move the head of the list back one bit and set prev, which is far away from ah, to undefined.

At the end of delete

This one is relatively simple, and the main change is the tail property.

Set the end of the table to the current element, then move the end of the table forward one bit and set the prev of the new end to undefined.

Delete middle position

Middle position deletion does not need to consider the case of the table header or table tail. Get the element at the index position directly through the class method getItemAt, and then get the previous element through current-.prev.

Change the next attribute of the previous element and the prev attribute of the next element, bypassing the element at the current index position.

Use bidirectional linked lists

Let’s experiment with the two methods written above:

var doublinked = new doubLinkedList()
doublinked.insert('Beijing'.0)
doublinked.insert('Shanghai'.1)
doublinked.insert('chengdu'.2)
console.log(doublinked.toString()) // Beijing, Shanghai, Chengdu
Copy the code

This is ok, and then get the middle element:

let node = doublinked.getItemAt(1)
console.log(node.prev.value) / / Beijing
console.log(node.next.value) / / chengdu
Copy the code

The test results are correct, and we’re done!

conclusion

This article introduces the concept of a bidirectional list, and then uses class inheritance to implement insert and removeAt methods on the basis of the linked list class.

There are only two methods written, but the rest of the methods are the same as they are, except that they operate on tail and prev on the list elements.

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