当前位置：网站首页>js 链表 01

js 链表 01

2022-07-28 14:51:00 【PBitW】

文章目录

链表 – 数组和链表的优缺点

在这里插入图片描述

链表结构封装

在这里插入图片描述
看这个视频之前，菜鸟以前只知道链表怎么写，每次都要看别人的代码，不够理解怎么样定义链表结构，现在感觉可以不看别人的代码自己定义出来列表的结构了。

代码

<!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>单向链表</title>
</head>
<body>
  <script> // 封装链表类 function LinkedList(){
       // 属性 this.head = null; this.length = 0; //记录长度 // 内部类：节点类 function Node(data){
       this.data = data; this.next = null; } } </script>
</body>
</html>

这里比较难以想到的就是内部类，但是写了优先级列表后，就发现这个也可以类比，只要是一个节点有多个变量的时候，都可以用到这内部类！（记住类基本上就是函数）

head属性是因为每个链表都必须从头开始访问，所以这个head自然是少不了的！

length属性就是用于获得链表的长度，和数组的length属性一样，不然你今后获取链表的长度还要把链表整个的给遍历一次，很耗时间！

注意

该视频讲的主要是无头链表！

链表操作

在这里插入图片描述

append实现 – 尾部添加

在这里插入图片描述
代码

// 1 追加方法
LinkedList.prototype.append = function(data){
    
  let newNode = new Node(data);
  if(this.length == 0){
    
    // 没有节点，就直接让head指针指向添加的元素
    this.head = newNode;
  }else{
    
    // 通过变量找最后的节点
    let current = this.head;
    // current.next为null的时候，此时以跳出循环，current指向的就是最后一个节点而不是null
    while(current.next){
    
      current = current.next;
    }
    // 最后节点的next指向新节点
    current.next = newNode;
  }
  this.length += 1;
}

toString实现

在这里插入图片描述
视频代码

代码

// 2 toString方法
LinkedList.prototype.toString = function(){
    
  // 定义变量
  let current = this.head;
  let arr = [];
  // 这里就不能是current·next了，因为要遍历全部，而不是到最后一个就退出！
  while(current){
    
    arr.push(current.data);
    current = current.next;
  }
  return arr.join(" ");
}

insert实现 – 指定位置插入

在这里插入图片描述
这里添加到其它位置之所以要两个变量是因为，当你获取到了后一个节点就不能通过其获取前一个节点获取前一个节点！

所以这里菜鸟感觉还有一种思路：就是获取到前一个节点，然后将新加入的节点的next指向前一个节点的next，然后再将前一个节点的next指向新的节点，感觉挺好的，不会缺失！

代码

// 3 insert方法
LinkedList.prototype.insert = function(position,data){
    
  // 1 对position进越界判断
  if(position < 0 || position > this.length) return false;

  // 2 创建节点
  let newNode = new Node(data);

  // 3 判断节点插入的位置是否是第一个
  if(position == 0){
    
    // 这里是this.head而不是head.next，因为head指向的就是第一个节点
    // head是指针而非节点
    newNode.next = this.head;
    this.head = newNode;
  }else{
    
    let index = 0;
    let current = this.head;
    // current指向第一个节点时，previous代表前一个节点自然是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我的想法
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;
}