1. 链表
1.1基本概念
通常我们储存多个元素, 数组或链表是最合适的数据结构,数组给我们提供了非常方便的[]操作符,但是它有一个致命的缺点,当我们往数组进行插入和删除数据时,后面的所有元素的都需要移动位置,使得我们操作数据的性能成本很大.当数据较多时,频繁地删除的插入/删除数据时, 再用数据充当储存结构的效率是非常低的.
链表 (LinkedList) 也可以用来储存有序的数据,它与数组的不同之处在于,链表中的元素在内存中并不是连续放置的.每一个节点由自身的数据和一个指向下一个节点的next(也称指针或者链接)组成.通过next指针将所有的节点串联起来形成类似于链的结构.
1.2创建链表结构
首先我们看看链表的主要功能需求
单向列表
1. 向链尾追加节点(push);
2. 查找指定元素对应的节点(find);
3. 向链表的特定位置插入节点(insert);
4. 移除指定数据对应的节点(remove);
5. 打印链表结构(print)
6. 返回链表长度
可能还会需要额外的功能
查找数据对应索引（indexOf）
按照索引查找节点（find的参数设计）
按照索引插入节点（insert的参数设计）
按照索引移除节点（remove的参数数据）
下面是一个简单的单向链表的实现.
const LinkedList = (function(){
let HEAD = Symbol();
// 创建节点的基本类
class Node{
constructor(element){
this.element = element;
// 指向下一个节点的指针
this.next = null;
}
}
return class{
constructor(){
// 头节点
this[HEAD] = null;
// 链表的个数
this.count = 0;
}
//往链表链尾追加数据
append(element){
// 创建对应的链节点
const node = new Node(element);
// 获取链头
let head = this[HEAD];
// 如果链头是null;
if(this[HEAD] === null){
this[HEAD] = node;
}else{
// 如果不是链头则循环找到链尾
while(head.next !== null){
head = head.next;
}
// 将其next指向新节点, 建立链接
head.next = node
}
this.count++;
return this
}
// 查找指定元素对应的节点
find(element,index){
let result = [];
let head = this[HEAD];
// 如果头节点为 null 则返回空数组
if (head === null) return result;
// index没有传值, 将按元素是是否相等进行查找
if(index === undefined){
while(head !== null){
if(head.element === element){
result.push(head);
}
head = head.next;
}
}
// 如果index有中则按照下标进行查找
if(typeof index === "number"){
let i = 0;
while(head !== null){
if(index === i){
result.push(head)
}
head = head.next;
i++;
}
}
return result
}
//在链表指定位置进行插入元素
insert(element,index){
// 检测所以值, 防止越界
if(index >=0 && index <= this.count){
const node = new Node(element);
if(index === 0) {// 在第一个位置添加
const current = this[HEAD];
node.next = current;
this[HEAD] = node;
}else{
// 将上一个节点的next指向插入的节点
// 并且当插入的节点的next指向上一个节点的next
const pre = this.find("",index-1)[0];
const current = pre.next;
node.next = current;
pre.next = node;
this.count++
return true;
}
}
// 表示插入失败
return false;
}
// 通过指定数据或者下标删除指定节点
remove(element,index){
//获取当前删除的节点
let head = this[HEAD];
// 如果index没有传值则, 则通过查找元素是否相等来进行删除
if(index === undefined){
// 如果为头节点则直接清空
if(head.element === element){
this[HEAD] = head.next;
return
}
// 遍历链表直到指针不为空, 如果当前节点的元素的下一个节点元素与目标元素相等
// 则将其指针指向指针得下一个的下一个,来进行清空节点
while(head.next !== null){
if(head.next.element = element){
head.next = head.next.next;
this.count--
}
return;
head = head.next
}
}
else if (typeof index === "number") {
//如果为头节点则直接清空头节点
if(index === 0){
this[HEAD] = head.next;
return
}
// 通过index进行查找
let i = 0;
while(head.next !== null){
if(i === index){
head.next = head.next.next;
this.count--
return
}
i++;
head = head.next;
}
}
}
// 返回链表个数
size(){
return this.count
}
// 打印链表
print(){
let current = this[HEAD];
while(current !== null){
console.log(current.element);
current = current.next
}
}
//返回元素在链表中的索引, 如果没有则返回-1
indexOf(element){
let head = this[HEAD],
index = 0;
while(head.next !== null){
if(head.element === element){
return index
}
index++;
head = head.next
}
return -1
}
}
})();
双向链表和循环链表
双向链表和普通链表的区别在于, 在链表中一个节点只有链向下一个的节点, 而在双向链表中,链接是双向的, 一个链向下一个元素, 一个链向前一个元素.
循环链表可以向链表一样只有单向引用,也可以像双向链表一样有双向引用.循环链表和链表之间的唯一的区别在于,最后一个元素指向下一个元素的指针(tail.next)不是引用undefined,而是指向第一个元素head.
总结: 相当于传统的数组, 链表有一个好处,添加或者删除元素的时不需要移动其他元素,而链表需要使用指针,当数据过多时,会产生较大的内存开销.当我们需要对数据进行频繁新增和删除操作时,应该选择使用链表结构,链表想要访问中间某一个元素比较麻烦,需要从表头起点开始迭代直到找到需要的元素.
2. 集合
2.1基本概念
集合是由一组无序且唯一的数据组成的.该数据集合使用了与有限集合相同的数学概念,但应用在计算机科学的数据结构中.
ES6中Set结构就是集合结构,我们将基于ES6的Set类来实现我们自己的Set类.
2.2创建集合基本结构
首先我们声明一些集合可用的方法
- add(element): 向集合中添加一个元素.
- delete(element): 从集合中删除一个元素.
- has(element):返回一个元素是否存在集合的布尔值
- chear(): 清空集合中所有元素.
- size(): 返回集合中包含元素的数量,他与数组length属性类型.
- values(): 返回一个包含集合所有值(元素)的数组.
class MySet{
constructor(){
this.items = {}
}
// 向集合中添加一个元素
add(element){
if(!this.has(element)){
Reflect.set(this.items,element,element);
// 返回this方便链式调用
return this;
}
return false;
}
// 从集合中删除元素
delete(elemennt){
if(this.has(elemennt)){
Reflect.deleteProperty(this.items,this.items[elemennt]);
return true;
}
return false
}
//集合是否存在对应元素
has(elemennt){
return Reflect.has(this.items,elemennt);
}
// 返回集合的长度
size(){
return Object.keys(this.items).length;
}
// 清空集合
clear(){
this.items = {};
}
// 返回一个包含集合所有值的数组
values(){
return Object.values(this.items)
}
}
接下来我们测试一下上面的代码
let set = new MySet();
set.add(43).add(45).add(52);
console.log(set.size())//3;
console.log(set.has(43))//true
console.log(set.delete(43));//true.
console.log(set.has(43))//false
console.log(set.values())//[45,52]
2.3 集合的应用
我们都知道集合是数学中基础的概念,在计算机领域也非常重要.集合之间的运算有并集,交集,差集,子集.
下面我们简单实现这几种运算.
并集
对应给定的两个集合,返回一个包含两个中所有元素的新集合.
现在我们实现MySet类的union方法
union(otherSet){
const unionSet = new MySet();
return [...this.values(),...otherSet.values()].reduce((total,val) =>{
total.add(val);
return total
}, unionSet)
}
上面这个方法首先会创建一个新的集合, 接下来将实例上的所有value和传入的实例的所有alue值数组合并成一个数组,然后利用数组的reduce方法进行迭代并传入当前的新实例,往新创建的实例添加对应的value.接着迭代继续会返回对应的新实例对象.
交集
对于两个给定的集合,返回一个包含两个集合共有元素的新集合
接下来我们实现MySet类中的interserction方法
intersection(otherSet){
const intersection = new MySet();
// 遍历实例的每一个集合值, 如果传入的集合实例也包含对于的值
// 则添加到新集合中
this.values().forEach(val =>{
if(otherSet.has(val)){
intersection.add(val)
}
})
return intersection;
}
intersection方法通过迭代当前MySet实例上的所有值,来判断它是否也存在在otherSet实例中,利用实例身上的has方法我们可以很方便的判断,如果存在我们就将其添加到新创建的实例上.最后我们返回新集合.
差集
对于两个给定的集合,返回一个包含存在于第一个集合且不存在第二个集合的元素的新集合.
接下来我们实现MySet类中的difference方法.
difference(otherSet){
const differenceSet = new MySet();
this.values().forEach(val =>{
if(!otherSet.has(val)){
differenceSet.add(val)
}
})
return differenceSet
}
difference方法的实现和intersection方法的实现非常类似,intersection方法是获取两个集合相同的元素,difference方法则是获取两个集合中存在差异的元素.代码实现起来非常简单,只需要迭达MySet实例上的每一个值, 如果不存在与otherSet集合中则添加到新集合中,并最终返回.
子集
验证一个给定集合是否是另一个集合的子集.
接下来我们来实现MySet类的isSubsetof方法
isSubsetof(otherSet){
if(this.size() > otherSet.size()) {
return false;
}
for(let val of this.values()){
if(!otherSet.has(val)){
return false
}
}
return true
}
首先我们先验证当前实例的大小, 如果当前实例中的元素要比ohterSet实例中的元素多,那么它就不给一个子集.因为子集的元素要小于或等于要比较的集合.
接下来我们假定当前实例是给定元素的子集,我们迭代当前实例上的所有元素,验证这些元素是否也存在于otherSet中,如果有任何元素不存在则意味它不是一个子集,返回false.如果所有元素都存在于ohteSet中,那么最终返回true.
总结: 集合是一种不允许存在重复值的顺序数据结构,集合的特性就是无序且唯一(即不存在重复),集合在计算机科学中的主要应用就是之一就是数据库,而数据库是大多数应用程序的根基,集合通常被由于查询的设计和处理.
