【JS】基于链表实现的迭代器

最近一直在研究链表相关的结构，突发奇想实现一下类似数组的entries功能

先贴链表的代码，以单向链表为例

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。
每个 元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。
下图展 示了一个链表的结构。
【JS】基于链表实现的迭代器

class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}

class LinkList {
constructor() {
this.head = null;
this.count = 0;
}
push(val) {
const node = new Node(val);
if (this.head == null) {
this.head = node;
} else {
let current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
this.count++;
return this.count;
}
removeAt(index) {
if (index >= 0 && index < this.count) {
let head = this.head;
if (index === 0) {
this.head = head.next;
} else {
// 上一个
let prev = this.getElementAt(index - 1);
let current = prev.next;
prev.next = current.next;
}
this.count--;
return head.value;
}
return undefined;
}
getElementAt(index) {
if (index >= 0 && index < this.count) {
let current;
if (index === 0) {
current = this.head;
} else {
current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
}
return current;
}
return undefined;
}
insert(element, index) {
if (index >= 0 && index < this.count) {
let node = new Node(element)
if (index === 0) {
node.next = this.head;
this.head = node;
} else {
// 上一个
let prev = this.getElementAt(index - 1);
let next = prev.next;
node.next = next;
prev.next = node;
}
this.count++;
return element;
}
return undefined;
}
indexOf(element) {
let current = this.head;
for (let i = 0; i < this.count; i++) {
if (current.value === element) {
return i;
}
current = current.next;
}
return undefined;
}
getHead() {
return this.head;
}
remove(element) {
const index = this.indexOf(element);
this.removeAt(index);
}
isEmpty() {
return this.size() === 0;
}
size() {
return this.count;
}
toString() {
let current = this.head;
let str = `${current.value}`;
for (let i = 1; i < this.count; i++) {
current = current.next;
str = `${str},${current.value}`;
}
return str;
}
}

以原型继承方式实现entries

LinkList.prototype.entries = function() {
let current = this.head;
const count = this.count;
let selfCount = 0;
return new function() {
this.next = function() {
if(selfCount > count || current == null) {
return {value: undefined, done: true};
}
let [index, value] = [selfCount, current.value];
selfCount++;
let done = count === selfCount;
current = current.next;
return {index, value, done};
}
}
}

此处采用闭包是为了获取链表结构的头节点与节点数量，返回构造函数来实现next方法

let l = new LinkList();
l.push(1);
l.push(2);
l.push(3);
l.insert(1.5, 1)
const item = l.entries();
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())

【JS】基于链表实现的迭代器

此处针对数组返回做了一些改动，将index和value做了单独抽取

以上是 【JS】基于链表实现的迭代器 的全部内容， 来源链接： utcz.com/a/98316.html

回到顶部