I am working on a library that will implement array functions for linked lists.
I want to use linkedlistobject[i] to get a value by index, and linkedlistobject[i] = x to change a value by index.
How can I make my class iterable? For example, in Python, it can be made iterable using some magic functions (if I'm not wrong, it was __iter__).
How can I create an iterable object that can be used with [ ] notation?
Having the possibility to access values by index is not the same thing as making an object iterable. This is also true in Python: implementing __iter__ will not provide the possibility to access values by index.
So there are two different concepts here. We can make an object iterable by implementing the Symbol.iterator generator method. We can provide index access by setting a trap on property access using a Proxy.
The following demo provides a linked list with the following methods:
_nodeAt: will get the node at the specified index. This method will be called by the proxy when it detects that the property being accessed represents an integer (index). Contrary to Array, negative integers will also be interpreted as indexes, counting from the back of the list.
Symbol.iterator: to allow iteration over the list's values.
push: like for arrays, can take a variable number of values which will be added to the list. The constructor calls this method when it is given one or more values to initialise the linked list with. Contrary to the Array constructor, there is no special length meaning to providing only one value.
length: like for arrays, this is a getter/setter. However, it does not allow to extend the list to a longer length than it already has.
toString: a string representation delimited by an arrow character.
An instance only maintains a reference to the head node. It does not track the current length nor the tail node. This could be an option to add later, but also adds overhead.
The demo illustrates how a list can be constructed, how values can be accessed by index, can be modified by index, and can be iterated over:
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);