做网站需要多少钱一年,做黑网站,wordpress手机ui,平面设计素材免费数据结构#xff08;二#xff09;一、什么是链表1.数组的缺点2.链表的优点3.链表的缺点4.链表和数组的区别二、封装单向链表1. append方法#xff1a;向尾部插入节点2. toString方法#xff1a;链表元素转字符串3. insert方法#xff1a;在任意位置插入数据4.get获取某个…
数据结构二一、什么是链表1.数组的缺点2.链表的优点3.链表的缺点4.链表和数组的区别二、封装单向链表1. append方法向尾部插入节点2. toString方法链表元素转字符串3. insert方法在任意位置插入数据4.get获取某个位置的元素5.indexOf根据元素值返回元素位置6.update更新某个位置的元素7.removeAt删除某个位置的节点8.remove删除指定data的元素9.判断是否为空、输出长度三、封装双向链表1.什么是双向链表2.封装双向链表结构搭建3.append向尾部插入元素1链表为空添加的是第一个节点2添加的不是第一个节点那么改变相关指向4.toString链表数据转换为字符串5.insert向任意位置插入节点6.get获取某个位置的元素值7.indexOf根据某个元素值获取该节点位置8.update更新某个元素9.removeAt删除某个位置的节点10.remove删除某个元素11.其他方法一、什么是链表
链表和数组一样可以用于存储一系列的元素但是链表和数组的实现机制完全不同。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用有的语言称为指针或连接组成。类似于火车头一节车厢载着乘客数据通过节点连接另一节车厢。 head属性指向链表的第一个节点链表中的最后一个节点指向null当链表中一个节点也没有的时候head直接指向null 1.数组的缺点
1、数组的创建通常需要申请一段连续的内存空间一整块内存并且大小是固定的。所以当原数组不能满足容量需求时需要扩容一般情况下是申请一个更大的数组比如2倍然后将原数组中的元素复制过去。 2、在数组的开头或中间位置插入数据的成本很高需要进行大量元素的位移。
2.链表的优点
1、链表中的元素在内存中不必是连续的空间可以充分利用计算机的内存实现灵活的内存动态管理。 2、链表不必在创建时就确定大小并且大小可以无限地延伸下去。 3、链表在插入和删除数据时时间复杂度可以达到O(1)相对数组效率高很多。
3.链表的缺点
1、链表访问任何一个位置的元素时都需要从头开始访问需要顺着指针一个一个找无法跳过第一个元素访问任何一个元素。 2、无法通过下标值直接访问元素需要从头开始一个个数组内和指针访问直到找到对应的元素这也是和数组最明显的区别。 3、虽然可以轻松地到达下一个节点但是回到前一个节点是很难的。
4.链表和数组的区别
二、封装单向链表
首先定义一个节点类用来存储新声明的节点
//定义一个节点类用来声明新的节点
class Node {constructor(data) {this.data data; //数据this.next null; //指针}
}开始封装声明两个属性分别是头部指针和长度。
1. append方法向尾部插入节点
1、先声明一个新的节点判断链表是否有数据。如果没有数据直接head指向新节点。 2、如果有数据那么就要声明一个变量current来存储当前的指针。这个指针第一次肯定指向第一个元素看代码理解然后循环看一下current.next是否有指向如果有就改变current为current.next直到current.next为空说明已经到链表尾部了。 3、最后将current指针指向新节点搞定。
//封装一个单向链表
class LinkedList {constructor() {this.head null;this.length 0;}//将元素插入链表尾部的方法append(data) {//1.声明一个新的节点let newNode new Node(data);if(this.length 0) {//2.1如果链表为空那么head直接指向新节点this.head newNode;}else {//2.2如果链表不为空那么循环遍历直到指针指向最后一个节点let current this.head; //这里每次都是指向第一个元素while(current.next) {current current.next;}current.next newNode;}//3.添加完之后length1this.length;}
}2. toString方法链表元素转字符串
//转字符串的方法
toString() {let result ;let current this.head;while (current) {result current.data ; //如果有就拼接current current.next; //指针指向后面的元素}return result;
}顺便测试一下append方法好不好使
let list new LinkedList();
list.append(DantinZhang);
list.append(zzy);
list.append(元素);
console.log(list.toString()); //DantinZhang zzy 元素 3. insert方法在任意位置插入数据
情况1在position为0的位置插入数据那么这样的话就要 1、先让插入的新元素指向原来的第一个元素 2、然后再让head指向插入的新元素。 情况2往其他位置插入 1、首先应该拿到该位置的那个元素 2、让新节点指向该元素 3、让该位置前边的元素指向新节点 代码仔细看注释
//任意位置插入元素
insert(position, data) {//1.对position进行越界判断//positionthis.length说明是往最后插如果比它大就不行了if(position 0 || position this.length) return false;//2.生成新节点let newNode new Node(data);//3.对position的不同情况进行判断//3.1如果插入的位置是第一个position0if(position 0) {newNode.next this.head; //先保存原来的第一个元素this.head newNode; //再把新节点给head//注意上面这两步顺序不能反不然就找不到原来的第一个元素了}else {//如果是往其他位置插入元素let current this.head; //拿到第一个元素let previous null; //声明变量存储position前边的元素//循环查找直到找到这个位置的元素for(let i 0; i position; i) {previous current; //保存上一个位置current current.next; //保存当前位置}//循环结束后current已经是position位置的元素newNode.next current; //让新节点指向当前位置节点挤到后边去previous.next newNode; //让前一个节点指向新节点}//4.长度加1this.length;return true;
}测试代码
let list new LinkedList();
list.append(DantinZhang);
list.append(zzy);
list.append(元素);
list.insert(2,ht);
console.log(list.toString()); //DantinZhang zzy ht 元素 4.get获取某个位置的元素
传入位置返回当前位置元素。 主要的思路就是从head找通过循环依次改变指针的指向直到指针指向当前位置那么就把当前位置返回如果用户输入0那么直接返回this.head
//获取某个位置的元素
get(position) {//1.越界判断,如果获取最后一个位置后面那么是没有滴所以是lengthif (position 0 || position this.length) return false;//2.从头往后找直到找到该位置元素let current this.head;for (let i 0; i position; i) {current current.next;}return current;
}测试代码
let list new LinkedList();
//1.测试尾部插入
list.append(DantinZhang);
list.append(zzy);
list.append(元素);
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, ht);
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个位置元素
console.log(list.get(2)); //Node {data: ht, next: Node}5.indexOf根据元素值返回元素位置
主要的思路是从head依次往后查找需要定义指针current如果当前指针不为空就拿传入的元素值和当前current指针的元素值比较如果相等说明是我们要找的直接return不相等就要依次往后指并且index要1 indexOf(data) {let current this.head;let index 0; //定义一个索引//从头开始一个一个对比如果相等了就返回index的值while(current) {if(current.data data) {return index;}else {//当前节点不是我要找到节点那么就往后指current current.next;index;}}//如果所有都对比完了都没找到说明没有就返回-1return -1;}测试代码
let list new LinkedList();
//1.测试尾部插入
list.append(DantinZhang);
list.append(zzy);
list.append(元素);
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, ht);
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个位置元素
console.log(list.get(2)); //Node {data: ht, next: Node}
//4.测试获取某个元素索引
console.log(list.indexOf(zzy)); //16.update更新某个位置的元素
主要思路 1、通过声明current指针拿到这个位置的元素 2、改变该元素内部的data的值不需要改变前后指针因为对象地址不会变
//更新某个位置的元素值
update(position, data) {//1.越界判断,positonlength是刚好在最后一个元素的后面那个空位if(position 0 || position this.length ) return false;//2.拿到这个位置节点let current this.head;let index 0;while(index postion) {current current.next;}//3.修改当前节点的元素值current.data data;return current;
}测试更新
let list new LinkedList();
//1.测试尾部插入
list.append(DantinZhang);
list.append(zzy);
list.append(元素);
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, ht);
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个元素索引
console.log(list.indexOf(zzy)); //1
//4.测试获取某个位置元素
console.log(list.get(2)); //Node {data: ht, next: Node}
//5.测试修改元素
list.update(2, 修改元素);
console.log(list.toString()); //DantinZhang zzy 修改元素 元素 7.removeAt删除某个位置的节点
1、如果删除的是第一个位置那么head直接指向第二个节点其他不用动被删除的第一个节点由于没有指针指向它会被垃圾回收机制回收 2、如果删除的是其他的位置就要让被删除节点的上一个节点指向被删除节点的下一个节点 代码如下
//删除指定位置的节点
removeAt(position) {//1.越界判断if(position 0 || position this.length) return false;let current this.head;//2.1如果删除的是第一个节点,前边没东西只有headif(position 0) {this.head current.next;}else {//2.2如果删除的是其他位置的节点let index 0;let previous null;//2.2.1先找到前边的节点删除节点后边的节点while(index position) {previous current;current current.next;}//2.2.2将前边的节点指向后边的节点previous.next current.next;}//3.长度-1this.length--;//4.返回被删除的元素return current;
}测试代码
let list new LinkedList();
//1.测试尾部插入
list.append(DantinZhang);
list.append(zzy);
list.append(元素);
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, ht);
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个元素索引
console.log(list.indexOf(zzy)); //1
//4.测试获取某个位置元素
console.log(list.get(2)); //Node {data: ht, next: Node}
//5.测试修改元素
list.update(2, 修改元素);
console.log(list.toString()); //DantinZhang zzy 修改元素 元素
//6.测试删除指定位置元素
list.removeAt(2);
console.log(list.toString()); //DantinZhang zzy 元素 8.remove删除指定data的元素
这里的思路就是先找到data对应的索引然后删除直接调用就行了
//删除指定data所在的节点
remove(data) {//1.先找到data所在的位置let index this.indexOf(data);//2.删除该位置的元素return this.removeAt(index);
}9.判断是否为空、输出长度
//判断链表是否为空
isEmpty() {return this.length 0;
}//判断链表的长度
size() {return this.length;
}全部测试代码
let list new LinkedList();
//1.测试尾部插入
list.append(DantinZhang);
list.append(zzy);
list.append(元素);
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, ht);
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个元素索引
console.log(list.indexOf(zzy)); //1
//4.测试获取某个位置元素
console.log(list.get(2)); //Node {data: ht, next: Node}
//5.测试修改元素
list.update(2, 修改元素);
console.log(list.toString()); //DantinZhang zzy 修改元素 元素
//6.测试删除指定位置元素
list.removeAt(2);
console.log(list.toString()); //DantinZhang zzy 元素
//7.测试删除指定data的元素
list.remove(元素);
console.log(list.toString()); //DantinZhang zzy
//8.测试是否为空和输出长度
console.log(list.isEmpty()); //false
console.log(list.size()); //2三、封装双向链表
1.什么是双向链表
双向链表既可以从头遍历到尾又可以从尾遍历到头。也就是说链表连接的过程是双向的它的实现原理是一个节点既有向前连接的引用也有一个向后连接的引用。 双向链表的缺点 1、每次在插入或删除某个节点时都需要处理四个引用而不是两个实现起来会困难些 2、 相对于单向链表所占内存空间更大一些 3、但是相对于双向链表的便利性而言这些缺点微不足道。 也就是说双向链表就是用空间换时间 双向链表不仅有head指针指向第一个节点而且有tail指针指向最后一个节点每一个节点由三部分组成item储存数据、prev指向前一个节点、next指向后一个节点点双向链表的第一个节点的prev指向null双向链表的最后一个节点的next指向null
2.封装双向链表结构搭建
class Node {constructor(data) {this.pre null;this.data data;this.next null;}
}class DoublyLinedList {constructor() {this.head null;this.tail null;this.length 0;}
}3.append向尾部插入元素
双向链表向尾部插入元素和单向不一样这里不需要再遍历元素直接拿到tail操作就可以了。在插入的时候有两种情况1、链表为空时 2、链表不为空时
1链表为空添加的是第一个节点
我们只需要让head和tail都指向这个节点就可以了
2添加的不是第一个节点那么改变相关指向
改变指向分为两步首先改变下图1、2指向此时tail指向的是原来的最后一个节点。
newNode.pre this.tail; //先让新节点pre指向之前的尾部节点
this.tail.next newNode; //之前尾部节点next指向新节点第二步改变指向3让tail指向新插入的最后一个节点。
this.tail newNode; //tail指向新节点//向尾部插入节点
append(data) {//1.先生成一个节点const newNode new Node(data);//2.添加的是第一个节点只需要让head和tail都指向新节点if(this.length 0) {this.head newNode;this.tail newNode;} else {//3.添加的不是第一个节点,直接找到尾部(不用遍历)newNode.pre this.tail; //先让新节点pre指向之前的尾部节点this.tail.next newNode; //之前尾部节点next指向新节点this.tail newNode; //tail指向新节点console.log(newNode.next); //最后一个指向null}//4.长度加一this.length;
}测试代码
const list new DoublyLinedList();
list.append(DantinZhang);
list.append(努力的但丁);
console.log(list); 4.toString链表数据转换为字符串
这里有两种转字符串的方法分别是顺序和逆序。
主要原理都一样就是定义current变量记录当前指向的节点。首先让current指向第一个最后一个节点然后通过 current current.next 依次向后向前遍历。在while循环或for循环中以(current)作为条件遍历链表只要current null就一直遍历由此可获取链表所有节点的数据。 代码
//1.链表数据转换为字符串的两种遍历顺序、逆序
toString() {return this.forwardString();
}//2.顺序遍历转字符串
forwardString() {let result ;let current this.head;while (current) {result current.data ;current current.next;}return result;
}//3.逆序遍历转字符串
backwardString() {let result ;let current this.tail;for (let i 0; i this.length; i) {result current.data ;current current.pre;}return result;
}测试代码
const list new DoublyLinedList();
list.append(DantinZhang);
list.append(努力的但丁);
list.append(zzy);
console.log(list.toString()); //DantinZhang 努力的但丁 zzy
console.log(list.forwardString()); //DantinZhang 努力的但丁 zzy
console.log(list.backwardString()); //zzy 努力的但丁 DantinZhang 5.insert向任意位置插入节点
这里代码看着比较复杂不过实现的思路不难。 具体可以去看这个人的博客写的真的是非常详细Javascript实现双向链表
//向任意位置插入节点
insert(position, data) {let newNode new Node(data);//1.越界判断其中length位置是最后一个节点的后面那个空位if (position 0 || position this.length) return false;//2.1如果链表为空if (this.length 0) {this.head newNode;this.tail newNode;} else {//2.2如果链表不为空//2.2.1如果位置是1if (position 0) {// this.head此时指的是第一个节点this.head.pre newNode;newNode.next this.head;this.head newNode;}//2.2.2.如果在最后一个节点的后面插入else if (position this.length) {// this.tail此时指的是最后一个节点newNode.pre this.tail;this.tail.next newNode;this.tail newNode;}//2.2.3.如果在其他位置插入else {//先找到这个位置let index 0;let current this.head;let previous null;while (index position) {previous current;current current.next;}//插入新节点到它们俩中间儿previous.next newNode;newNode.pre previous;newNode.next current;current.pre newNode;}}//3.长度别忘了1this.length;return true;
}测试代码
//测试代码//1.创建双向链表let list new DoubleLinklist()//2.测试insert方法list.insert(0, 插入链表的第一个元素)list.insert(0, 在链表首部插入元素)list.insert(1, 在链表中间插入元素)list.insert(3, 在链表尾部插入元素)console.log(list);alert(list)6.get获取某个位置的元素值
整体思路比较简单为了提高效率可以使用二分查找。判断位置是在前半部分还是在后半部分如果在前半部分就从head开始找如果在后半部分就从tail开始找。
//获取某个位置的元素值
get(position) {//1.越界判断if (position 0 || position this.length) return false;//2.1如果该元素在前半部分,从head开始找if (position this.length / 2) {let current this.head;for(let i 0; i position; i) {current current.next;}return current.data;} else {//2.2如果该元素在后半部分,从tail倒着找let current this.tail;let index this.length - 1;while(index-- position) {current current.pre;}return current.data;}
}测试代码
const list new DoublyLinedList();
list.append(DantinZhang);
list.append(努力的但丁);
list.append(zzy);
list.append(ht);
list.insert(2, 第三个位置插入本元素);
console.log(list.forwardString());
console.log(list.backwardString());
console.log(list.get(2)); //第三个位置插入本元素
console.log(list.get(3)); //zzy7.indexOf根据某个元素值获取该节点位置
这个和单向链表一样就是从头找找不到就返回-1找到了就对比并返回索引
//根据元素值获取节点位置
indexOf(data) {let current this.head;let index 0;while(current) {if(current.data data) {return index;}else {current current.next;index;}}return -1
}测试代码
const list new DoublyLinedList();
list.append(DantinZhang);
list.append(努力的但丁);
list.append(zzy);
list.append(ht);
list.insert(2, No.3);
console.log(list.forwardString());//DantinZhang 努力的但丁 No.3 zzy ht
console.log(list.backwardString());
console.log(list.get(2)); //第三个位置插入本元素
console.log(list.get(3)); //zzy
console.log(list.indexOf(zzy));//38.update更新某个元素
主要思路还是先查找然后把数据改了就行。查找的时候采用二分查找。
//更新某个元素
update(position, data) {//1.生成节点let newNode new Node(data);//2.越界判断if(position 0 || position this.length) return false;//3.寻找位置改变元素值二分查找let current null;if(position this.length / 2) {current this.head;let index 0;while(index position) {current current.next;}}else {current this.tail;for(let i this.length-1; i position; i--) {current current.pre; }}current.data data;return current.data;
}测试代码
const list new DoublyLinedList();
list.append(DantinZhang);
list.append(努力的但丁);
list.append(zzy);
list.append(ht);
list.insert(2, No.3);
console.log(list.forwardString());//DantinZhang 努力的但丁 No.3 zzy ht
console.log(list.backwardString());
console.log(list.get(2)); //第三个位置插入本元素
console.log(list.get(3)); //zzy
console.log(list.indexOf(zzy));//3
//测试更新
list.update(2,DJ);
console.log(list.toString()); //DantinZhang 努力的但丁 DJ zzy ht 9.removeAt删除某个位置的节点
这里的主要思路是 1、首先判断是否只有一个节点如果只有一个节点删除后head和tail都要置空. 2、如果有多个节点要看删除的是第一个、最后一个、其他位置。 3、第一个位置先清空第二节节点指向被删除元素的pre指针清空所有指向它的指针这样该节点在内存中没用途会被自动回收然后直接让head指向第二个节点就行了。 4、最后一个位置同理删除倒数第二个节点指向被删除节点的next然后让tail直接指向倒数第二个节点。 5、删除完长度-1
//删除某个位置的元素
removeAt(position) {//1.越界判断if(position 0 || position this.length) return false;let current this.head; //定义在最上面方便各种情况返回数据//2.判断是否只有一个节点if(this.length 1) {//2.1如果只有一个节点那么删除时head和tail都为空this.head null;this.tail null;}else {//2.2如果有多个节点那么就要进行位置判断//2.2.1删除第一个节点if(position 0) {//删除前head指向的是第一个节点this.head.next.pre null; //所有指向它的指针都清掉this.head this.head.next;}//2.2.2删除最后一个节点else if(position this.length-1) {//删除前tail指向的是最后一个节点current this.tail;this.tail.pre.next null; //所有指向它的指针都清掉this.tail this.tail.pre;}//2.2.3删除其他的节点else {//先找到位置let index 0;while(index position) {current current.next;}current.pre.next current.next;current.next.pre current.pre;}}//3.删除完-1this.length - 1;return current.data;
}代码测试
const list new DoublyLinedList();
list.append(DantinZhang);
list.append(努力的但丁);
list.append(zzy);
list.append(ht);
list.insert(2, No.3);
console.log(list.forwardString());//DantinZhang 努力的但丁 No.3 zzy ht
console.log(list.backwardString());
console.log(list.get(2)); //第三个位置插入本元素
console.log(list.get(3)); //zzy
console.log(list.indexOf(zzy));//3
//测试更新
list.update(2,DJ);
console.log(list.toString()); //DantinZhang 努力的但丁 DJ zzy ht
list.removeAt(2);
//测试删除
console.log(list.toString()); //DantinZhang 努力的但丁 zzy ht 10.remove删除某个元素
//删除某个元素
remove(data) {return this.removeAt(this.indexOf(data));
}测试代码 const list new DoublyLinedList();list.append(DantinZhang);list.append(努力的但丁);list.append(zzy);list.append(ht);list.insert(2, No.3);console.log(list.forwardString());//DantinZhang 努力的但丁 No.3 zzy htconsole.log(list.backwardString());console.log(list.get(2)); //第三个位置插入本元素console.log(list.get(3)); //zzyconsole.log(list.indexOf(zzy));//3//测试更新list.update(2,DJ);console.log(list.toString()); //DantinZhang 努力的但丁 DJ zzy ht //测试删除list.removeAt(2);list.remove(努力的但丁);console.log(list.toString()); //DantinZhang zzy ht 11.其他方法
//删除某个元素
remove(data) {return this.removeAt(this.indexOf(data));
}//测试是否为空
isEmpty() {return this.length 0;
}//输出长度
size() {return this.length;
}//获取链表第一个元素值
getHead() {return this.head.data;
}//获取链表最后一个元素值
getTail() {return this.tail.data;
}更详细的图解参考大佬的博客
