数据结构与算法
1.链表
相比于之前的数组，链表是一种存储空间不连续的结构。数组的存储是连续的，但是它在移动或者是删除元素时，它后面的元素都要移动相应的位置，所以当数据量比较大时还是比较耗费资源的。链表则是存储空间不连续的一种数据结构，类似于火车，由一个一个节点组成，每个节点包含着指向下一个节点的地址以及数据，当删除或添加时只需要修改节点中存储的引用即可。
链表结构
class NodeList {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.length = 0;
this.head = null;
}
append Node(){
}
……
}
链表的常用方法
1. appendNode(val)：添加一个新节点
appendNode(val) {
let newNode = new NodeList(val)
if (!this.head) {
this.head = newNode;
} else {
let cur = this.head;
while (cur.next) {
cur = cur.next;
}
cur.next = newNode
}
this.length++;
}
2. insertNode(val,position)
向链表中插入节点，参数为节点的值以及插入位置。常规的插入是先找到待插入位置的pre节点，之后将cur节点的next指向pre的next，最后将pre的next的节点设置为curNode
// 指定位置插入节点
insertNode(val, position) {
if (position > this.length || position < 0) return false;
let newNode = new NodeList(val)
if (position === 0) {
newNode.next = this.head;
this.head = newNode
} else {
let previous = this.getNodeByposition(position - 1)
previous.next = newNode.next;
previous.next = newNode
}
this.length++
return true
}
3. removeAt(position)
移除指定位置的节点。常规的删除方法：找到待删除节点的preNode，最后将preNode的next指向preNode的next的next，也就是将curNode节点的上一个节点和下一个节点连在一起，没有指向的节点会在浏览器中自动被垃圾回收机制回收。
removeAt(position) {
if (position >= this.length || position < 0) return false;
let current = this.head
let cur = this.getNodeByposition(position)
if (position === 0) {
this.head = current.next;
} else {
let previous = this.getNodeByposition(position - 1)
previous.next = previous.next.next;
}
this.length--;
return cur
}
4.getNodeBypostion(position)
通过指定位置获取当前的节点信息，返回的是节点类型的数据。
常规方法，将头指针从头开始指，将指针向后移动postion次
getNodeByposition(position) {
if (position < 0 || position > this.length) {
return -1
}
let current = this.head;
while (position--) {
current = current.next
}
return current
}
5.getDataByPostion(position)
通过指定位置来获取节点的data。常规方法：从头开始遍历，当指针移动position次时，将node的data返回。
getDataByPosition(position) {
if (position < 0 || position > this.length) {
return false
}
let current = this.head;
while (position--) {
current = current.next
}
return current.data;
}
6.removeElement(val)
给定值，将链表中的改数据的节点删除。常规方法：从头遍历，将每一个节点的值都与val进行比对，如果相同，就执行删除节点的函数。但这种方法只考虑到data不相同的情况，如果data相同则只会删除第一个
removeElement(val) {
let position = this.getPostionByData(val);
console.log(position);
let previous = this.getNodeByposition(position - 1);
console.log(previous);
let tempNode = previous.next;
if (position > -1) {
previous.next = previous.next.next
return tempNode
}
else {
return false
}
}
7.clearNode()
清空当前的链表。常规方法：将链表的长度置零，头指针置空
// 清空链表
clearNode() {
this.head = null;
this.length = 0;
}
8.nodeToString()
将链表中每一个节点的数据都打印出来
nodeToString() {
let cur = this.head;
let listStr = '';
while (cur) {
listStr += cur.data + ' '
cur = cur.next
}
return listStr
}
9.updateNode(position,newVal)
将指定位置的节点数据替换。常规方法，先找到指定位置的节点，再将节点数据更新
updataNode(position, newVal) {
if (position < -1 || position > this.length) return false;
let cur = this.getNodeByposition(position);
if (cur) {
cur.data = newVal
return true;
} else {
return false;
}
}
2.双向链表
双向链表就是在单链表的基础上给链表中的每个节点增加一个前驱节点，链表可以从头部遍历，也可以从尾部开始遍历
节点结构
相比于单向链表，双向链表中的每个节点都多了一个指向前驱节点的指针。也就是我们可以自由的访问到当前节点的上一个节点以及下一个节点。
class NodeList {
constructor(val) {
this.data = val;
this.pre = null;
this.next = null;
}
}
链表结构
链表中多了一个指向尾部的指针，方便我们从尾部开始遍历
class DoubleLinked {
constructor() {
this.length = 0;
this.head = null;
this.tail = null
}
appendNode(){}
……
}
常用方法
常用的方法与之前的单链表类似，但是在细节上稍作变化，常用的比如有：appendNode、insertNode、removeNode、displayList……,使用的辅助方法有：getNodeByPosition、getPositionByData、getDataByPosition、getNodeByData。这里所说的辅助方法就是可以我们对经常使用的代码的封装，方便我们在其它方法中使用
1.appendNode(val)
向链表尾部插入元素，插入之前先判断所插入的是否为头节点。
appendNode(val) {
if (val == undefined) throw new Error('缺少参数');
let newNode = new NodeList(val)
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
}
else {
this.tail.next = newNode;
newNode.pre = this.tail;
this.tail = newNode
}
this.length++;
return this.displayList()
}
2.getPositionByData(val)
通过传递的值来判断该元素在链表中的索引，比如知道该学生的姓名，但不知道学号，也就是索引。可以从头部和尾部同时查找，两个指针同时开始移动，如果链表中没有这个元素才会遍历链表。
getPositionByData(val) {
let head = this.head;
let tail = this.tail;
let index = 0;
while (head) {
if (head.data === val) return index;
head = head.next;
if (tail.data === val) return this.length - 1 - index;
tail = tail.pre;
index++;
}
return null
}
3.getNodeByData(val)
通过传递的值来返回该值所在的节点，同样的以学生信息管理系统为例，我们只知道这个学生的名字，需要返回该学生的所有相关信息，此时就可以使用该方法，返回该节点，同时该节点中包含前驱指针和后继指针。
getNodeByData(val) {
let headNode = this.head;
let tailNode = this.tail;
while (headNode) {
if (headNode.data == val) return headNode;
if (tailNode.data == val) return tailNode;
headNode = headNode.next;
tailNode = tailNode.pre;
}
return null
}
4.getDataByPosition(position)
通过索引来返回该节点的值，同样的还是先找到该节点，之后再返回该节点的值
getDataByPosition(position) {
if (position >= this.length || position < 0) return false;
let middlePosition = Math.floor(position / 2);
let curNode = null;
if (position > middlePosition) {
curNode = this.tail;
let i = this.length - 1;
while (i > position) {
curNode = curNode.pre;
i--
}
} else {
curNode = this.head;
while (position--) {
curNode = curNode.next
}
}
return curNode.data
}
5.getNodeByPosition(position)
返回指定位置的节点,，比如返回某个班级中23号同学的信息。
getNodeByPosition(position) {
if (position >= this.length || position < 0) return false;
let middlePosition = Math.ceil(position / 2);
let curNode = null;
if (position >= middlePosition) {
curNode = this.tail;
let i = this.length - 1
while (i > position) {
curNode = curNode.pre;
i--;
}
} else {
curNode = this.head;
while (position--) {
curNode = curNode.next
}
}
return curNode
}
6. insertNode(position,val)
向指定位置插入元素，需要分三种情况进行判断。先判断它是否是尾部插入或者是头部插入，如果是头部插入的话还需要判断它是否作为头节点。最后一种情况则是大多数情况，也就是中间插入。此时只需要改变前驱节点以及后继节点的指向即可。
insertNode(position, val) {
if (arguments.length === 1) throw new Error('缺少参数');
if (position >= this.length || position < 0) return '索引越界'
if (position === this.length - 1) {
return this.appendNode(val);
}
else if (position === 0) {
if (this.head === null) {
this.appendNode(val)
} else {
let headNode = new NodeList(val);
headNode.next = this.head;
this.head.pre = headNode;
this.head = headNode;
}
}
else {
let newNode = new NodeList(val);
let curNode = this.getNodeByPosition(position);
newNode.next = curNode;
newNode.pre = curNode.pre;
curNode.pre.next = newNode;
curNode.pre = newNode;
}
this.length++;
return true
}
7.remoNode(position)
删除指定位置的节点，返回值为被删除的节点。同样的还是需要判断是头部删除还是尾部删除，中间删除只需要改变前驱节点和后继节点的指向即可。
removeNodeByPosition(position) {
if (position > this.length - 1 || position < 0) return null;
let curNode = this.getNodeByPosition(position)
if (position = 0) {
this.head = this.head.next;
this.head.pre = null;
} else if (position === this.length - 1) {
this.tail = this.tail.pre;
this.tail.next = null;
}
else {
let preNode = curNode.pre;
let nextNode = curNode.next;
preNode.next = nextNode;
nextNode.pre = preNode;
}
this.length--;
return curNode
}
8.displayList(join)
将链表中的所有数据以字符串的形式进行拼接并打印。可以接收参数拼接，参数默认为空格。
displayList(join = ' ') {
let curNode = this.head;
let str = '';
while (curNode) {
curNode.next !== null ? str += curNode.data + join : str += curNode.data
curNode = curNode.next;
}
return str
}
调用
let linkList = new DoubleLinked()
linkList.appendNode('apple');
linkList.appendNode('banana');
linkList.appendNode('peach');
linkList.appendNode('7777')
linkList.getDataByPosition(2)
linkList.getPositionByData('apple')
console.log(linkList.displayList());
|