Linked Lists vs. Array Lists: A Comparison
When working on my data structure implementations recently, I built both an ArrayList and a LinkedList. This turned out to be a perfect scenario to demonstrate the power of iterators and generators. With ES6, JavaScript gained a fresh iteration mechanism for traversing data, along with corresponding protocols that offer a consistent way to loop over structures. When an object adheres to the iteration and iterator protocols, it can define custom iteration behavior that modern language features like the for..of loop and the spread operator can take advantage of.
This piece doesn't aim to dive deep into the theoretical details but rather focuses on a practical scenario where these concepts shine. For thorough explanations, refer to the MDN documentation and Axel Rauschmayer's excellent Exploring ES6 book.
The LinkedList and the ArrayList serve as the foundation for many other sophisticated structures. Both belong to the List ADT category, but they differ significantly in their performance characteristics for core operations like retrieving, inserting, and removing elements.
An ArrayList is a contiguous memory structure. It manages an internal fixed-size array, which it dynamically expands or contracts by allocating new memory and shifting elements over to the new array.
This setup grants swift random access — meaning you can retrieve any element in constant time, no matter the list's size. On the flip side, adding or removing an element at the front is a slow, linear operation because most of the other elements need to be shifted.
A LinkedList, conversely, is a linked structure. It connects separate memory segments using pointers, with each element (or node) holding a reference to the next one.
This design makes inserting or deleting from the front very efficient, but finding an element in the middle requires a linear walk from the head node.
For our discussion here, the focus will be on the internal representation and the get operation, setting aside insertion and deletion for now.
A First Implementation
To see the difference in practice, let's build both data structures using ES6 classes. We'll skip the complexity of insert methods and instead populate the lists within the constructor. We'll only code the get method and omit any defensive programming like boundary checks.
ArrayList in Code
module.exports = class ArrayList {
constructor() {
const el1 = {value: 1};
const el2 = {value: 2};
const el3 = {value: 3};
this.list = [];
this.list.push(el1);
this.list.push(el2);
this.list.push(el3);
this.size = 3;
}
get(index) {
return this.list[index];
}
};
LinkedList in Code
module.exports = class LinkedList {
constructor() {
const el1 = {data: {value: 1}, next: null};
const el2 = {data: {value: 2}, next: null};
const el3 = {data: {value: 3}, next: null};
// link elements together
el1.next = el2;
el2.next = el3;
// set a pointer to the first node
this.head = el1;
this.size = 3;
}
get(index) {
let counter = 0;
let element = this.head;
while (counter < index) {
element = element.next;
counter++;
}
return element.data;
}
};
If linked lists are new to you, notice this: pulling the last item via get is a single step for the array list, but it requires N steps for the linked list as it traverses the chain. Keep that distinction in mind for what follows.
Looping Through the Lists
Imagine we have a generic list object and we want to sift out all numbers smaller than 3. This sounds straightforward since we know the list exposes a get method. We could just write a standard for loop using indices:
const filtered = [];
for (let i = 0; i < list.size; i++) {
const element = list.get(i);
if (element.value > 2) {
filtered.push(element);
}
}
At first, this seems perfectly fine. But there's a subtle issue if list happens to be a linked list. As we saw, accessing an element by index in a linked list requires internal traversal. This means we're iterating once in our loop and then iterating again inside get. This duplication of effort results in very poor performance.
Because both lists are meant to be traversed the same way, a better approach is to give each structure a forEach method. This lets us iterate without repeating the index lookups. Here’s how that looks:
// implement the method on prototype and extend ArrayList
class ForEachArrayListIterator {
forEach(fn) {
for (let i = 0; i < this.list.length; i++) {
fn(this.list[i]);
}
}
}
// implement the method on prototype and extend LinkedList
class ForEachLinkedListIterator {
forEach(fn) {
let element = this.head;
while (element !== null) {
fn(element.data);
element = element.next;
}
}
}
class ArrayList extends ForEachArrayListIterator { ... }
class LinkedList extends ForEachLinkedListIterator { ... }
You'd use it like this:
const filtered = [];
list.forEach((element) => {
if (element.value > 2) {
filtered.push(element);
}
});
While this resolves the redundancy problem, it introduces other limitations:
- there's no way to exit the loop before it finishes
- we'll miss out on leveraging the
listin features that rely on iteration, such as thefor..ofloop or thespreadoperator
Bringing in an iterator will address both of these concerns.
Building an Iterator
The iterable protocol dictates that an object must have a method at the [Symbol.iterator] property. Typically, this is triggered automatically when used with constructs like for..of. This method's job is to return an object that adheres to the iterator protocol, which requires a next method.
Writing an iterator for both an array and a linked list is not hard. The key is to track the current position, returning the current item via next, and then bumping the position counter. When we run out of elements, we signal completion with {done: true}. Here’s a possible implementation:
class ForEachLinkedListIterator {
[Symbol.iterator]() {
let element = this.head;
return {
next() {
let value, done = true;
if (element !== null) {
value = element.data;
done = false;
element = element.next;
}
return {
value: value,
done: done
}
}
}
}
}
class ForEachArrayListIterator {
[Symbol.iterator]() {
const self = this;
let i = 0;
return {
next() {
let value, done = true;
if (self.list[i] !== undefined) {
value = self.list[i];
done = false;
i += 1;
}
return {
value: value,
done: done
}
}
};
}
}
With this in place, we can now plug the list into a for..of loop or use it with the spread operator:
const list = new LinkedList();
for (let element of list) {
console.log(element);
}
console.log([...list]);
The iterator solves our earlier issues. Still, writing the next method manually is a bit tedious and opens up room for mistakes. Is there a simpler way?
Yes, there is. ES6 brought in generator functions. They look like classic functions but can pause and resume over time. They work by producing a generator object that follows the iterator protocol, which is precisely what we need.
Generator Approach
Generators can be used as methods in a class. Inside the generator, each yield operator echoes the value written for each next call. Essentially, we can express the loop as we did with forEach, but instead of invoking a callback, we produce the value with yield. The result is our final, much cleaner implementation:
class ForEachLinkedListIterator {
*[Symbol.iterator]() {
let element = this.head;
while (element !== null) {
yield element.data;
element = element.next;
}
}
}
class ForEachArrayListIterator {
*[Symbol.iterator]() {
for (let i = 0; i < this.list.length; i++) {
yield this.list[i];
}
}
}
That wraps it up. The complete code is published on GitHub.