使链表实例可通过索引访问并可迭代

Question

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

我想用linkedlistobject[i]通过索引得到一个值，linkedlistobject[i] = x到改变一个按指数计算的价值。

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

Answer 1

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

所以这里有两个不同的概念。我们可以通过实现 Symbol.iterator generator method. We can provide index access by setting a trap on property access using a 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);

使链表实例可通过索引访问并可迭代

Make a linked list instance accessible by index and iterable

javascript

arrays

oop

iterator

linked-list