JS bidirectional linked list 02

get Realization – Get the corresponding location element

The idea is the same as that of the single linked list ！

Code

// 7 get Method  --  The efficiency is not high , It can be divided equally , After all, there is a tail node ！
DoublyLinkedList.prototype.get = function(position){
    
  if(position < 0 || position >= this.length) return null;
  let current = this.head;
  let index = 0;
  while(index++ < position){
    
    current = current.next;
  }
  return current.data;
}

The code shared equally here is not written by rookies , The idea is hold position and length/2 Compare , If it is larger than tail, Use less than head！

indexOf Realization – Determine whether it contains elements

This is also the same idea as the single linked list ！

Code

DoublyLinkedList.prototype.indexOf = function(data){
    
  let current = this.head;
  let index = 0;
  while(current){
    
    if(current.data === data){
    
      return index;
    }
    current = current.next;
    index++;
  }
  return -1;
}

update Realization – Change the value of a position

Here rookies use the idea of equal sharing , above get Readers who don't write equally , You can learn from here ！

Code

// 9 update Method 
DoublyLinkedList.prototype.update = function(position,data){
    
  if(position < 0 || position >= this.length) return false;
  if(position < this.length/2){
    
    let current = this.head;
    let index = 0;
    while(index++ < position){
    
      current = current.next;
    }
    current.data = data;
  }else{
    
    let current2 = this.tail;
    //  Be careful ：index be equal to length-1, because length It's length. , And the subscript is from 0 Start , therefore index The biggest can only be length-1
    let index = this.length - 1;
    while(index-- > position){
    
      current2 = current2.prev;
    }
    current2.data = data;
  }
  return true;
}

removeAt Realization – Remove the element at a certain position

There are a lot of things here ,eg：

1. Only one node
2. The second node is removed
3. What is removed is the last node
4. Remove intermediate nodes

2、3 It has been , Because we need to change head、tail The direction of ！

Rookies didn't consider so many situations when they wrote their own code at the beginning , Then I thought of it while watching the video , I wrote it with my own ideas and the video .

Code

// 11 removeAt1  Video method 
DoublyLinkedList.prototype.removeAt1 = function(position){
    
  if(position < 0 || position >= this.length) return false;
  //  Determine whether there is only one node 
  if(this.length === 1){
    
    this.head = null;
    this.tail = null;
  }else {
    
    if(position === 0){
     // Determine whether the deleted node is the first node 
      this.head.next.prev = null;
      this.head = this.head.next;
    }else if(position === this.length - 1){
     //  Judge whether the last node is deleted 
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
    }else{
    
      //  Divide ideas equally 
      if(position < this.length/2){
    
        let current = this.head;
        let index = 0;
        while(index++ < position - 1){
    
          current = current.next;
        }
        current.next.neaxt.prev = current;
        current.next = current.next.next;
      }else{
    
        let current = this.tail;
        let index = this.length - 1;
        while(index-- > position+1){
    
          current = current.prev;
        }
        current.prev.prev.next = current;
        current.prev =current.prev.prev;
      }
    }
  }

  this.length -= 1;
  return true;
}

Rookies here have different ideas from the video , What is saved is the previous or next node to be deleted , Not the deleted node itself , So the value cannot be returned , But I feel The video is better （ Save the deleted node ）, Because a two-way linked list is not like a one-way linked list , You need to save the information of two nodes , Because it can access both the front node and the back node ！

Video code

remove Realization – Remove a value

Just call two methods directly here , Rookies don't write

Other methods

summary

It's not hard to see , The difficulty of one-way linked list and two-way linked list lies in insert and removeAt Method , Just figure out these two methods Some special circumstances , In fact, it is not particularly difficult to write ; Other operations of the two-way linked list are really no different from those of the one-way linked list , Some even because With tail Pointer and simpler ！