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

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

链表的特点

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

封装类

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

增删改查

第一个方法，向链表末尾添加一个元素
在这里插入图片描述

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++;
};

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

LinkList.prototype.print = function () {
  let current = this.head;
  let str = "";
  while (current) {
    str += current.data + " ";
    current = current.next;
  }
  return str;
};

测试一下

 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

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("🚀 ~ previous:", previous);
    console.log("🚀 ~ current:", current);
  }
  this.length--;
  return true;
};

根据给定的值删除链表中的元素

//根据元素值去删除
LinkList.prototype.remove = function (element) {
  let current = this.head,
    previous;
  let isNotFound = false;
  while (current) {
    if (current.data == element) {
      previous.next = current.next;
      isNotFound = true;
      this.length--;
      return true;
    }
    previous = current;
    current = current.next;
  }
  if (!isNotFound) {
    return -1;
  }
};

4.更新一个元素

//更新链表中的某个元素
LinkList.prototype.update = function (position, newData) {
  //越界判断
  if (position < 0 || position > this.length) return false;

  const element = this.getElement(position);
  element.data = newData;
  console.log("🚀 ~ element:", element);
  return true;
};

//获取链表中的某个位置的元素
LinkList.prototype.getElement = function (position) {
  //越界判断
  if (position < 0 || position > this.length) return false;
  let current = this.head,
    index = 0;

  while (index++ < position) {
    current = current.next;
  }
  return current;
};

5.查找一个元素

在这里插入图片描述

//获取指定位置的元素
LinkList.prototype.indexOf = function (element) {
  if (this.length == 0) return -1;

  let current = this.head,
    index = 0;

  while (current) {  //判断退出迭代的条件
    if (current.data == element) {
      return index;
    }
    current = current.next;
    index++;
  }
  return -1;
};

几个辅助方法

//为空
LinkList.prototype.isEmpty = function () {
  return this.length === 0;
};
LinkList.prototype.size = function () {
  return this.length;
};
LinkList.prototype.getHead = function () {
  return this.head;
};

测试所有的方法

	   link.insert(4,'maomao')
       console.log("print2",link.print());

       link.removeAt(4)
       console.log("print3",link.print());

       link.append('cba');
       console.log("print4",link.print());
       const index = link.indexOf('cba');
       const index2 = link.indexOf('eee');
       console.log("🚀 ~ index:", index)
       console.log("🚀 ~ index2:", index2)


       //查询链表中的元素
       const element = link.getElement(2);
       console.log("🚀 ~ element:", element)

       //更新元素
       const nElement = link.update(2,'tom')
       console.log("🚀 ~ nElement:", nElement)
       console.log("print5",link.print());
       

       //根据给定的元素删除
       const removeElement = link.remove('tom')
       console.log("🚀 ~ removeElement:", removeElement)
       console.log("🚀 ~ link:", link.print())