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

JS linked list 01

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

List of articles

Linked list – Advantages and disadvantages of arrays and linked lists

Insert picture description here

Linked list structure encapsulation

Insert picture description here
Before watching this video , Rookies used to only know how to write a linked list , Always look at others' code , I don't understand how to define the linked list structure , Now I feel I can define the structure of the list without looking at other people's code .

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> One way linked list </title>
</head>
<body>
  <script> //  Encapsulate linked list class  function LinkedList(){
       //  attribute  this.head = null; this.length = 0; // Record length  //  Inner class ： Node class  function Node(data){
       this.data = data; this.next = null; } } </script>
</body>
</html>

What is hard to think of here is the inner class , But after writing the priority list , I found that this can also be compared , As long as a node has multiple variables , Can use this internal class ！（ Remember that classes are basically functions ）

head Attribute is because Every linked list must be accessed from the beginning , So this head Nature is indispensable ！

length Attribute is used to obtain the length of the linked list , And an array of length Same property , Otherwise, you need to traverse the whole list to get the length of the list in the future , It takes a lot of time. ！

Be careful

This video is mainly about headless linked lists ！

List operation

Insert picture description here

append Realization – Tail add

Insert picture description here
Code

// 1  Add method 
LinkedList.prototype.append = function(data){
    
  let newNode = new Node(data);
  if(this.length == 0){
    
    //  No nodes , Just let head The pointer points to the added element 
    this.head = newNode;
  }else{
    
    //  Find the last node through variables 
    let current = this.head;
    // current.next by null When , At this point, jump out of the loop ,current It points to the last node instead of null
    while(current.next){
    
      current = current.next;
    }
    //  At the last node next Point to a new node 
    current.next = newNode;
  }
  this.length += 1;
}

toString Realization

Insert picture description here
Video code

Code

// 2 toString Method 
LinkedList.prototype.toString = function(){
    
  //  Defining variables 
  let current = this.head;
  let arr = [];
  //  This can't be current·next 了 , Because you have to traverse all , Instead of quitting at the last ！
  while(current){
    
    arr.push(current.data);
    current = current.next;
  }
  return arr.join(" ");
}

insert Realization – Insert... At specified location

Insert picture description here
The reason for adding two variables to other locations here is because , When you get the latter node, you cannot get the previous node through it ！

So there's another idea for novices here ： Is to get the previous node , Then add the new node next Point to the previous node next, Then, the previous node's next Point to new node , It feels good , There's no missing ！

Code

// 3 insert Method 
LinkedList.prototype.insert = function(position,data){
    
  // 1  Yes position Entering and crossing boundary judgment 
  if(position < 0 || position > this.length) return false;

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

  // 3  Determine whether the insertion position of the node is the first 
  if(position == 0){
    
    //  Here is this.head instead of head.next, because head It points to the first node 
    // head Pointer, not node 
    newNode.next = this.head;
    this.head = newNode;
  }else{
    
    let index = 0;
    let current = this.head;
    // current When pointing to the first node ,previous Representing the previous node is naturally null
    let previous = null;
    while(index++ < position){
    
      previous = current;
      current = current.next;
    }
    newNode.next = current;
    previous.next = newNode;
  }

  this.length += 1;

  return true;
}

// 4 insert2 My thoughts 
LinkedList.prototype.insert2 = function(position,data){
    
  if(position < 0 || position > this.length) return false;
  let newNode = new Node(data);
  if(position == 0){
    
    newNode.next = this.head;
    this.head = newNode;
  }else{
    
    let index = 0;
    let current = this.head;
    while(index++ < position-1){
    
      current = current.next;
    }
    newNode.next = current.next;
    current.next = newNode;
  }
  this.length += 1;
  return true;
}