Linked Lists for Dummies
On high-level languages like JavaScript we usually don’t care about how the objects are stored in the memory, we let the VM handle it for us, and since the language contains Arrays most users never find a need for Linked Lists even tho it’s a very powerful and useful data structure.
Like most front-end developers I don’t have a Computer Science degree and started to program using high level languages, it took me a while to stumble into Linked Lists, that’s why I’m going to explain the basic use cases, pros/cons of this simple data-structure and why it’s widely used. - You probably used it before without knowing.
This post was motived by this tweet:
Can anyone explain what a Linked List is and why I’d use one (if I even could in Ruby, PHP, JS). I’m not quite grokking their purpose?— integralist (@integralist) May 12, 2013
Linked Lists are not indexed
The main difference from an Array is that Linked Lists are not indexed.
The Linked List doesn’t hold a reference to all the items that it stores, it usually only contain references to its head (first element) and/or tail (last item). Each item of the Linked List is responsible for storing a reference to the next and/or previous element of the list.
Not having indexes is the main advantage and drawback of Linked Lists.
It doesn’t support arbitrary access
The search and iteration over a linked list is usually sequential.
On an Array you can grab the 4th item by it’s index, like myArray[3]. Since the Linked Lists doesn’t contain indexes (or references to all items) you need to grab a reference to the head or tail of the list and iterate over the list items like myLinkedList.head.next.next.next.
As you can see, Linked Lists are not recommended when you need arbitrary access to the elements, in this case Arrays or Dictionaries/Hashes (plain old JavaScript objects) are better suited.
Adding/removing items is usually faster
Adding and removing items from a non-indexed list is usually faster since it doesn’t need to rebuild the index every time the items change, it just needs to update the references to the next and/or previous element.
Searching/iteration can be slower/cubersome
The lack of index and the simple structure can be a drawback, since you can’t skip to a certain position on the list some operations will require iterating over most nodes on the list or all of the list elements. - There are always pros and cons.
Linked lists usually don’t contain helper methods like the ES5 Array methods (map, reduce, some, forEach) which can make things a little bit harder to manage (you can implement it by yourself tho).
Lower-Level languages
Liked Lists are very common in lower level languages since you usually need to define how many bytes should be allocated for each object beforehand (returning a pointer to that location in memory and making sure it doesn’t collide with other pointers). Since linked lists doesn’t store a reference to all the items they can expand indefinitely without causing memory overlaps and items don’t need to be stored sequentially in memory or have the same size – it’s a very flexible data structure and very common because of that.
Basic Implementation
The very-minimal implementation of a linked list in JavaScript is:
// items of the list
var bird = {name:'Mockingbird'};
var cat = {name:'Keyboard'};
var dog = {name:'Fort'};
var duck = {name:'Scrooge'};
// the linked-list itself
var animals = {
head : bird
};
// each item of the list stores reference to the next one
bird.next = cat;
cat.next = dog;
dog.next = duck;
To iterate over all items in the list you can simply do:
var animal = animals.head;
while (animal) {
console.log(animal.name);
animal = animal.next;
}
The DOM is a Linked List
The DOM is a linked list, you use node.nextSibling, node.parentNode, node.firstChild, etc to iterate over the elements. Linked Lists are very good for this use case since we add/remove items and rearrange the nodes many times during the application life cycle. It also simplifies the traversal a lot, navigating lists by index can be very cumbersome, node.previousSibling is way simpler than nodesList[nodesList.indexOf(node) - 1].
Doubly/Multiply/Circular Linked List
Linked lists can have references to other elements besides the next element. It is specially useful when you need to iterate the list backwards or need to speed up some complex iteration/manipulation.
A Doubly Linked List is a list where the nodes also contains references to the previous elements.
// doubly-linked cat.prev = bird; dog.prev = cat; // storing the tail (last item) is also useful in some cases animals.tail = dog;
In a Multiply Linked List each node contains reference to 2 or more nodes. Circular lists have the tail.next point to the list head and are less common.
On rocambole I use a doubly-linked list for the tokens (prev and next references). On the nodes I use a multiply linked list (references to parent, startToken, endToken, next and prev), it simplifies the AST manipulation a lot and allows the creation of helper methods similar to jQuery very easily.
Cross references are extremely useful, don’t let the lack of index be a limitation, abuse it when needed.
Removing/Adding Items
Another big advantage of linked lists is that if you add/remove items during the iteration it usually doesn’t cause undesired side effects, imagine this scenario:
var animals = [bird, cat, dog, duck];
for(var i = 0, n = animals.length; i < n; i++) {
// OOPS! TypeError!
// length changed during iteration, animals[3] doesn't exist anymore.
var animal = animals[i];
console.log(animal.name);
if (animal.name === 'Fort') {
animals.splice(i, 1);
}
}
If you used a Linked List (or didn't cached the animals.length value) this problem wouldn't exist, removing items from a linked list doesn't break the iteration:
var animal = animals.head;
while (animal) {
console.log(animal.name);
if (animal.name === 'Fort') {
removeItem(animals, animal);
}
animal = animal.next;
}
// to remove an item we just need to remove all references to it
function removeItem(list, item){
// assuming that list is doubly-linked
if (list.head === item) list.head = item.next;
if (list.tail === item) list.tail = item.prev;
if (item.prev) item.prev.next = item.next;
item.next = item.prev = null;
// on a singly-linked list the process is more expensive since you need to
// loop over the items to find out where to remove
}
Sum Up
I hope it was clear enough and that you find some good use for it. I find it really important to learn about data structures and other computer sciency subjects, you never know when this kind of knowledge can be useful and a lot of smart people already thought about these problems before, it's good to have options.
Wikipedia contains a detailed explanation of the pros/cons in case you are interested in getting all the details. (not for dummies tho).
You could also create a generic implementation that works for multiple cases but that is outside the scope of this article, I tried to keep it as simple as possible just to explain the concept and not a specific implementation - a quick Google search returned many results. I have an old implementation on my personal files but to be honest I'm not using it on any projects and nowadays I would build it in a different way - make it a doubly linked list, remove the iteration helpers and simplify the structure (there is no need for a wrapper object for each node, prev and next are very unlikely to cause name collisions). Maybe one day I update it and release as a separate project...
That's it!
Edit 2013/05/16: Simplified removeItem implementation and moved it into it's own section.
