当前位置：网站首页>JS bidirectional linked list 01

JS bidirectional linked list 01

2022-07-28 15:56:00 【PBitW】

List of articles

Understanding two-way linked list
The illustration
Two way linked list structure encapsulation
Common operations of two-way linked list

Understanding two-way linked list

Insert picture description here

The illustration

Insert picture description here

Two way linked list structure encapsulation

Code

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script> function DoublyLinkedList(){
       //  attribute  this.head = null; this.tail = null; this.length = 0; //  Inner class  function Node(data){
       this.data = data; this.prev = null; this.next = null; } } </script>
</body>
</html>

Rookies now feel it's easy to write this structure package anyway , Because as long as you understand What parameters are required Where to point , then Inner classes are the encapsulation of nodes , What is encapsulated inside is the node content ！

Common operations of two-way linked list

Insert picture description here
In fact, it is similar to a one-way linked list , But the way of encapsulation is different , The methods provided for external use are roughly the same , After all, they are all linked lists , It's all about adding, deleting, and checking ！ In fact, you will find that the method of linked list is very similar to that of array , After all, the linked list is used to replace the array at some time to make the operation simpler ！

append Realization – Tail add item

Novice Watch Video , It turned out that there was no video , I had to write it myself , The idea is the same as that of a single linked list , The video code is found later , Find yourself writing complicated ！

My code

// 1 append Method 
DoublyLinkedList.prototype.append = function(data){
    
  //  Create nodes 
  let newNode = new Node(data);

  //  Determine the insertion location 
  if(this.length === 0){
    
    this.head = newNode;
    this.tail = newNode;
  }else{
    
    let current = this.head;
    //  Find the last node 
    while(current.next){
    
      current = current.next;
    }
    current.next =newNode;
    newNode.prev = current;
  }

  // length+1
  this.length += 1;
}

Video code

// 2 append2 Method   video 
DoublyLinkedList.prototype.append2 = function(data){
    
  // 1  Create nodes 
  let newNode = new Node(data);

  // 2  Determine whether the added node is the first node 
  if(this.length === 0){
    
    this.head = newNode;
    this.tail = newNode;
  }else{
    
    newNode.prev = this.tail;
    this.tail.next =newNode;
    this.tail = newNode;
  }

  // length+1
  this.length += 1;
}

In fact, this is a rookie who didn't jump out of the single chain list thinking , After all, it's already There is a parameter that points to the last node 了 , As a result, rookies still rely on circulation to find , Ha ha ha ha ！

String method implementation

Code

// 3 backwardString Method  --  Before and after 
DoublyLinkedList.prototype.backwardString = function(){
    
  //  Defining variables 
  let current = this.head;
  let string = '';

  //  Traverse backward one by one 
  while(current){
    
    string += current.data + " ";
    current = current.next;
  }

  return string;
}

// 4 forwardString Method  --  From back to front 
DoublyLinkedList.prototype.forwardString = function(){
    
  let current = this.tail;
  let string = '';
  //  Traverse forward in turn 
  while(current){
    
    string += current.data + " ";
    current = current.prev;
  }
  return string;
}

// 5 toStirng Method 
DoublyLinkedList.prototype.toString = function(){
    
  return this.backwardString();
}

insert Realization – Insert... At specified location

This is compared to the single linked list , Consider more pointer points , More （ One more. tail The pointer ）, however Make good use of tail、head, It simplifies the code ！ There is also to Consider the change of pointer , If it changes so that the later ones cannot be found, the order must be changed ！

Code

// 6 insert Method 
DoublyLinkedList.prototype.insert = function(position,data){
    
  // 1  Cross border judgment 
  if(position < 0 || position > this.length) return false;

  //  Create nodes 
  let newNode = new Node(data);

  //  Judge whether the original linked list is empty 
  if(this.length === 0){
    
    this.head = newNode;
    this.tail = newNode;
  }else{
    
    //  Judge position Is it 0
    if(position === 0){
    
      newNode.next = this.head;
      //  It's easy to forget this step if you write more single linked lists 
      this.head.prev = newNode; 
      this.head = newNode;
    }else if(position === this.length){
    
      //  This step is different from the one-way linked list , It can't be classified into the same category as inserting , because tail
      //  There's no need to call this.append, Part of the operation is repeated 
      newNode.prev = this.tail;
      this.tail.next =newNode;
      this.tail = newNode;
    }else{
    
      let current = this.head;
      let index = 0;
      while(index++ < position){
    
        current = current.next;
      }
      //  Modify pointer  -- 4 individual  --  The order of the second and fourth cannot be confused （ It doesn't matter ）, Otherwise, there will be errors due to the change of direction 
      newNode.next = current;
      current.prev.next = newNode;
      newNode.prev = current.prev;
      current.prev = newNode;
    }
  }

  this.length += 1;
  return true;
}