时间戳

首页 > 解决方案 > 使链表实例可通过索引和可迭代访问

javascript - 使链表实例可通过索引和可迭代访问

问题描述

我正在开发一个库，它将为链表实现数组函数。

我想用来linkedlistobject[i]按索引获取值，并按索引更改linkedlistobject[i] = x值。

如何使我的类可迭代？例如，在 Python 中，可以使用一些魔术函数使其可迭代（如果我没记错的话，它是__iter__）。如何创建可与[ ]符号一起使用的可迭代对象？

标签： javascriptarraysooplinked-listiterator

解决方案

能够通过索引访问值与使对象可迭代不同。在 Python 中也是如此：实现__iter__不会提供通过索引访问值的可能性。

所以这里有两个不同的概念。我们可以通过实现Symbol.iterator生成器方法使对象可迭代。我们可以通过使用Proxy设置属性访问陷阱来提供索引访问。

下面的demo提供了一个链表，方法如下：

  • _nodeAt: 将获取指定索引处的节点。当代理检测到被访问的属性表示一个整数（索引）时，将调用此方法。与数组相反，负整数也将被解释为索引，从列表的后面开始计数。

  • Symbol.iterator: 允许迭代列表的值。

  • push：与数组一样，可以采用可变数量的值，这些值将被添加到列表中。当给定一个或多个值来初始化链表时，构造函数会调用此方法。与 Array 构造函数相反，只提供一个值没有特殊的长度含义。

  • length: 就像数组一样，这是一个 getter/setter。但是，它不允许将列表扩展到比它已经拥有的更长的长度。

  • toString：由箭头字符分隔的字符串表示形式。

实例仅维护对头节点的引用。它不跟踪当前长度也不跟踪尾节点。这可能是稍后添加的选项，但也会增加开销。

该演示说明了如何构造列表、如何通过索引访问值、如何通过索引修改以及可以迭代：

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

class LinkedList {
    constructor(...values) {
        this._head = null;
        this.push(...values);
        return new Proxy(this, {
            get(that, prop) {
                return typeof prop === "string" && /^(0|-?[1-9]\d*)$/.test(prop) 
                    ? that._nodeAt(+prop).value 
                    : Reflect.get(...arguments);
            },
            set(that, prop, value) {
                return typeof prop === "string" && /^(0|-?[1-9]\d*)$/.test(prop)
                    ? (that._nodeAt(+prop).value = value) 
                    : Reflect.set(...arguments);
            }
        });
    }
    _nodeAt(i) {
        // Contrary to Array, support negative indexes: they count from the back of the list
        if (i < 0 && (i += this.length) < 0) throw new Error("Invalid index"); 
        let node = this._head;
        while (i-- > 0 && node) node = node.next;
        if (!node) throw new Error("Invalid index");
        return node;
    }
    push(...values) {
        if (!values.length) return;
        if (!this._head) this._head = new Node(values.shift());
        let tail = this._nodeAt(-1);
        for (let value of values) tail = tail.next = new Node(value);
        // Contrary to Array, return the linked list, not its new length
        return this; 
    }
    get length() {
        let count = 0;
        for (let _ of this) count++;
        return count;
    }
    set length(length) {
        if (length == 0) {
            this._head = null;
        } else try {
            this._nodeAt(length - 1).next = null;
        } catch {
            throw new Error("Invalid length");
        }
    }
    * [Symbol.iterator]() {
        for (let node = this._head; node; node = node.next) yield node.value;
    }
    toString() {
        return "«" + [...this].join("→") + "»";
    }
}

// Create list: a->b->c->d
let list = new LinkedList("a", "b", "c", "d");
console.log("initial list to string: " + list);

console.log("index access:");
for (let i = 0; i < list.length; i++) {
    console.log(list[i]);
}
console.log("last is: " + list[-1]);
console.log("double each value");
for (let i = 0; i < list.length; i++) {
    list[i] += list[i];
}
console.log("" + list);
console.log("iterate:");
for (let value of list) {
    console.log(value);
}
console.log("convert to array:");
console.log([...list]);
console.log("set length to 2:");
list.length = 2;
console.log("" + list);

推荐阅读