乐趣区

关于javascript:前端小白应该如何快速理解链表

如果用 js 来模仿链表操作,咱们应该怎么了解?网上大部分就是贴一下概念,一张图,一篇代码,然而对于小白来说还是很形象。什么指针?什么 next?为什么一会儿 next= 值一会儿 next=next?

令很多初学代码的人很困惑,而且 JavaScript 是弱类型语言,没有“指针”这一概念,导致对很多文章里说的指针不太不理。

链表是一种物理存储单元上非间断、非程序的存储构造,数据元素的逻辑程序是通过链表中的指针链接秩序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点能够在运行时动静生成。每个结点包含两个局部:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

在咱们用 JavaScript 示意指针时,能够把它当做是一个小推车。

“小明有一个小推车(小推车里有小梅)”->“小梅有一个小推车(小推车里有小虎)”->“小虎有一个小推车(小推车里有小丽)”

单向

咱们假如工厂有个工作流水线,最开始流水线上没有人:

class Liushuixian {constructor(){this.head = null}
}

以“人”为一个节点,一个人带有一些信息 还有一个推车,车里没有货色

class People {constructor(people) {
    this.people = people
    this.next = null
  }
}

如果咱们招来第一个人:

class Liushuixian {constructor(){this.head = null}

  // 增加人
  appendRen(people) {
    // 入职
    let newPeople = new People(people)
    this.head = newPeople
  }

  // 打印后果
  print() {
    let str = ''
    let current = this.head
    while(current) {
      str += current.people
      current = current.next
    }

    console.log(str)
  }
}

let l = new Liushuixian();

l.appendPeople("小明 - 车 -->"); // 小明 - 车 -->

如果招很多人:

class Liushuixian {constructor(){this.head = null}

  // 增加人
  appendPeople(people) {
    // 入职
    let newPeople = new People(people)

    // 如果流水线上没有人
    if (this.head === null) {this.head = newPeople} else {
      // 否则遍历,让他在线尾工作
      let current = this.head
      // 如果以后这个人小推车里有人,咱们就到下一个人那里
      while(current.next) {current = current.next}
      // 直到这个人小推车里没有人,就往以后这个人小推车里加上新人
      current.next = newPeople
    }
  }


  // 打印后果
  print() {
    let str = ''
    let current = this.head
    while(current) {
      str += current.people
      current = current.next
    }

    console.log(str)
  }
}

往流水线里增加几个人,而后打印一下后果:

let l = new Liushuixian();

l.appendPeople("小明 - 车 -->");
l.appendPeople("小梅 - 车 -->");
l.appendPeople("小虎 - 车 -->");
l.appendPeople("小丽 - 车 -->");
l.print(); // 小明 - 车 --> 小梅 - 车 --> 小虎 - 车 --> 小丽 - 车 -->

咱们解雇某一个人,如果解雇小虎,那么小虎的工作小丽接了,小梅间接与小丽对接:

 deletePeople(item) {
    // 如果 item 等于 0,头节点为下一个节点
    if (item === 0) {this.head = this.head.next; // 假如前一个节点为头结点} else {
      // 从第一个人开始查找
      let index = 0;
      let prev = this.head;
      while (prev) {
        index++;
        if (index === item) {prev.next = prev.next.next // 前节点间接指向后第二位} else {prev = prev.next;}
      }
    }
  }

  //。。。// 解雇小梅
  l.deletePeople(1); // 小明 - 车 --> 小虎 - 车 --> 小丽 - 车 -->
  // 而后解雇小丽
  l.deletePeople(2); // 小明 - 车 --> 小虎 - 车 -->
  // 解雇小明
  l.deletePeople(0); // 小虎 - 车 -->
  // 解雇小虎
  l.deletePeople(0); //

这里须要解决一下临界,当咱们删除的 item 大于链总长时,应进行操作:

//  while (prev) {
  index++;
  if (item > index) {console.error('error: 超出链表长度')
    return
  }
// ...

解雇某一个人后,咱们想再招一个人插入到工作链路中。假如咱们招来小芬,插入到小明前面小梅后面:

insertPeople(people, item) {let newPeople = new People(people);
    let head = this.head

    // 如果在头部插入,新头结点就等于新员工,新员工的小推车里是老头结点
    if (item === 0) {
      this.head = newPeople
      newPeople.next = head
    } else {
      let prev = head
      let index = 0
      while(prev) {
        index ++

        if (index === item) {
          newPeople.next = prev.next
          prev.next = newPeople
        } else {prev = prev.next}
      }
    }
  }

// ...
l.insertPeople('小芬 - 车 -->', 1)  // 小明 - 车 --> 小芬 - 车 --> 小梅 - 车 --> 小虎 - 车 --> 小丽 - 车 -->
结尾

上述 next 属性只咱们说的 小推车 也就是指针域,People构造函数代表节点,外面的 people 是携带的数据信息。current.next = newPeople能够示意把新的节点 newPeople 赋值给了 next,此时next 就是携带了数据信息的属性(援用 newPeople 的地址),next 指针域有指向 newPeople 地址的指针。js 层面明眼儿说,就是一个承载 newPeople 值的属性。

退出移动版