(三)前端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;}//链表长度加1this.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())