最近重新开始翻起《大话数据结构》,看到了静态链表部分里面讲C语言是利用数组模拟,觉得十分有趣。但是在JavaScript中,也可以用类似的方式去实现,定义一个数据域和一个结点域,然后实现链表的基础操作。弱类型语言没有指针,所以需要自己区实现。算法的乐趣就在于解决一些思路上的问题,直击问题的本质。
首先可以定义Node类,如下所示:
class Node {
constructor(value) {
this.data = value;
this.next = null;
}
}
然后实现StaticLinkedList类,先定义简单的append和display方法:
class StaticLinkedList {
constructor() {
this.head = null;
this.length = 0;
}
append(value) {
const newNode = new Node(value);
this.length++;
if (this.head === null) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
display() {
console.log('the static linked list is:rn');
let current = this.head;
if (current === null) {
console.log('empty!');
return;
}
while (current !== null) {
console.log(JSON.stringify(current));
console.log(`its value is ${current.data}rn`);
current = current.next;
}
}
}
其中append方法是在链表尾部添加新的Node对象,display方法可以打印出Node对象和它的数据。使用这个静态链表类也很简单,比如添加4个结点到这个链表里面:
const staticLinkedList = new StaticLinkedList();
staticLinkedList.append(3);
staticLinkedList.append(7);
staticLinkedList.append(16);
staticLinkedList.append(24);
我们还应该提供更加灵活添加结点的方法,比如我想在第三个结点位置插入一个新的结点,数值为11,那么现有的append方法就不适用了,需要定义一个新的插入结点的方法,代码如下:
/**
* Method to insert an new element at the specific location
*
* @param {*} elementValue the value of the element that to be inserted
* @param {*} index the position of the element, from 1 to maximum of the list
* @returns true/false
*/
insertAt(elementValue, index) {
if (index this.length + 1) {
console.log('index is out of the range!');
return false;
}
const newNode = new Node(elementValue);
let startPos = 1;
let current = this.head;
while (startPos
这段代码需要理解的是新结点如何添加到链表的那两行代码,首先是newNode.next = current.next,这行代码是把新结点的next指向了原来插入前位置的结点的下一个结点。然后current.next = nextNode,把新结点替换掉原来该位置的结点。
为了更好地理解,我画了一张示意图:
要注意的是step1和step2的顺序不能颠倒,否则会导致代码运行错误。
然后我们还需要定义一个移除指定位置结点的方法,如下所示:
removeAt(index) {
if (index this.length + 1) {
console.log('index is out of the range!');
return;
}
let current = this.head;
let startPos = 1;
let previous = null;
while (startPos
我对previous.next = current.next也画了一张示意图,删除原来结点,需要把它前面一个结点的next指向该结点的next。
总结:
静态链表的添加和移除略有不同,需要利用Node中的next进行模拟指针操作,让新的结点加入到链表,让需要被删除的结点直接从上一个结点的next指向到原有结点的next。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
下面的题目是最近我在力扣上面刷了每日一题之后所做的总结。 题目一 比较字符串最小字母出现频次 定义一个函数 f(s),统计 s 中(按字典序比较)最小字母的出现频次 ,其中 s 是一个非空字符串。 例如,若 s = “dcce”,那么 f(s) = 2,因为…