(三)前端javascript中的数据结构之链表上

在js中，没有为我们提供原生的数据结构支持的，但是在java中是有提供的。所以需要我们去模拟这种结构实现。
链表中最关键的一个元素，就是头节点，头节点不存储数据，指向第一个节点链表中几乎所有的操作都要从头结点开始。

链表的特点

1.链表中的元素在内存中并不是连续存储的，每个元素都有一个指针指向下一个元素
2.链表中的元素可以非常容易地插入和删除

封装类

//构造函数
function LinkList() {
  this.head = null;
  this.length = 0;
}
//辅助类，也叫内部类
function Node(data) {
  this.data = data;
  this.next = null;
}

1
2
3
4
5
6
7
8
9
10
11

增删改查

第一个方法，向链表末尾添加一个元素

LinkList.prototype.append = function (data) {
  //创建节点
  const node = new Node(data);
  //判断链表是否为空
  //如果为空，则将头节点指向新创建的节点
  if (this.length == 0) {
    this.head = node;
  } else {
    let current = this.head;
    //遍历链表，找到最后一个节点
    while (current.next) {
      current = current.next;  //这里就不是在不断地重新赋值current节点
    }
    current.next = node;
  }
  //链表长度加1
  this.length++;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.查询元素
第二个方法,为了方测试，我们需要一个打印链表的方法

LinkList.prototype.print = function () {
  let current = this.head;
  let str = "";
  while (current) {
    str += current.data + " ";
    current = current.next;
  }
  return str;
};
1
2
3
4
5
6
7
8
9

测试一下

 const link = new LinkList();
 link.append('aaa');
 link.append('ddd');
 link.append('ccc');
 link.append('nba');
 console.log("print",link.print());   //print aaa ddd ccc nba 
1
2
3
4
5
6

3.删除一个元素,根据给点的position去删

//从链表中移除元素
LinkList.prototype.removeAt = function (position) {
  //越界判断
  if (position < 0 || position > this.length) return false;

  let current = this.head,
    previous,
    index = 0;

  //如果移除的是第一个元素
  if (position == 0) {
    //head指向下一个元素
    this.head = current.next;
  } else {
    while (index++ < position) {
      previous = current;
      current = current.next;
    }
    previous.next = current.next;
    console.log("
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/802917