2013.05.15

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:

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.


Comments

[...] source: http://blog.millermedeiros.com/linked-lists/ [...]

I learned linked lists in C and makes much more sense there. I liked the examples in JS. However, IMHO, if you never heard about linked list the article is doesn't do a good introduction (maybe the idea is to check the wikipedia article before keep reading?).

This is my first time pay a visit at here and i am genuinely happy to read all at alone place.

I just like the valuable information you supply on your articles. I'll bookmark your weblog and check again here regularly. I am reasonably certain I'll be told plenty of new stuff right right here! Best of luck for the next!

My web site; [beach body](https://www.youtube.com/watch?v=wkDO3W86Os4 "beach body")

Leave a Comment

Please post only comments that will add value to the content of this page. Please read the about page to understand the objective of this blog and the way I think about it. Thanks.

Comments are parsed as Markdown and you can use basic HTML tags (a, blockquote, cite, code, del, em, strong) but some code may be striped if not escaped (specially PHP and HTML tags that aren't on the list). Line and paragraph breaks automatic. Code blocks should be indented with 4 spaces.