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.

Don't let medkcal negligrnce take those rights away from you. My final advice for finding a good personal injury attorney hhas to do with your oown behavior. To ensure that you get the best compensation foor the damages yoou have incurred, it would be pertinent to find a professional Toronto pesonal injury lawyers to repdesent you.

Here iis my weblog ... [personal injury lawyers in ottawa](http://orad.onocom.co.jp/userinfo.php?uid=54848 "personal injury lawyers in ottawa")

I must thank you for the efforts you've put in writing this blog. I aam hoping tto see the sam high-grade content from youu later on as well.

In truth, your creative writing abilities has encouraged me to get my own, personal blog now ;)

Feel free to surf to my blog ... [Seo Letchworth](http://www.purevolume.com/listeners/futuristicpsych84/posts/820085/Simon+King%C2%A0B.App.Sc.%28Chiro%29%2C+DIBAK "Seo Letchworth")

First of all I would like to say awesome blog! I had a quick question that I'd like to ask if you do not mind. I was curious to know how you center yourself and clear your head before writing. I've had a tough time clearing my thoughts in getting my thoughts out there.

I truly do take pleasure in writing but it just seems like the first 10 to 15 minutes are lost simply just trying to figure out how to begin. Any suggestions or hints? Many thanks!

Here is my site :: [Judy Neinstein Toronto](https://twitter.com/JudyNeinstein "Judy Neinstein Toronto")

hello!,I love your writing very so much! percentage we communicate eztra about your post on AOL? I need an expert in this house to solve my problem. Maybe that's you! Hving a look forward to look you.

Here is my webpage :: [resume writing services](http://www.resumebridges.com/ "resume writing services")

You have made some good points there. I looked on the web to learn more about the issue and found most people will go along with your views on this site.

My blog post ... [cartier love bracelet replica](http://support.mclarensyoung.com/entries/47191194-The-Way-To-Maintance-Jewelry-Like-Cartier-Love-Ring "cartier love bracelet replica")

Hi there! I just wanted to ask if you ever have any trouble with hackers? My last blog (wordpress) was hacked and I ended up losing months of hard work due to no data backup. Do you have any methods to protect against hackers?

my page; [Video Maker FX Review](http://snappeople.mohammediatechnologies.in/index.php?do=/VirgieBehanooov/info/ "Video Maker FX Review")

Thanks for the good writeup. It if truth be told was once a leisure account it. Glance advanced to more added agreeable from you! By the way, how can we communicate?

Feel free to surf to my blog: Flat Iron Chi [[Laboredidea1060.Beeplog.Com](http://laboredidea1060.beeplog.com "Laboredidea1060.Beeplog.Com")]

t seen it, ɗo youгѕelf a favor and watch On Golden Pond.

Thhey dօ not contain ennough nutrients fοr your body to notice.

It helps tо reduce the effects οf stress ɑnd givve ʏoս a stronger immunity.

Mу page Goonies, ([Janell](http://americanhairlessterriers.com/index.php?option=com_lyftenbloggie&view=entry&year=2012&month=09&day=04&id=9:american-hairless-terriers-with-allergies%FF%FFnofollow%FF1 "Janell"))

Thanks very interesting blog!

my homepage :: car accident lawyer sarasota ([Sophie](http://www.youtube.com/watch?v=Ar19bQ_mU8M "Sophie"))

Today, I went to the beach front with my kids. I found a sea shell and gave it to my 4 year old daughter and said "You can hear the ocean if you put this to your ear." She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is totally off topic but I had to tell someone!

My weblog; khasiat kulit manggis [[Emely](http://obatkulitmanggis.com "Emely")]

The mall well known due to the all in all one stop place for fun, frolic, hang-outs, shopping and food had more in store to produce its visitors require a break and laugh at life as well as ways with its 'Stand Up Comedy' event. roller-coaster ride that can be impossible to obtain off knowning that usually leaves you acting. Couples could be from literature (Romeo and Juliet), history (Antony and Cleopatra), show business (Brad Pitt and Angelina Jolie), and thus on. These toddler music games can reach musically inclined kids when little else can, and they also’re very exciting for other toddlers also.

Stop by my weblog [hack android games](http://makunagamefamilie.de/index.php?page=User&userID=30019 "hack android games")

I enjoy lookiong through an article that can make men and women think. Also, many thanks forr permitting me too comment!

Feel free to surf to my page :: [Tampa wrongful death](http://www.youtube.com/watch?v=Ar19bQ_mU8M "Tampa wrongful death")

Do you mind if I quote a few of your articles as long as I provide credit and sources back to your website? My blog site is in the very same area of interest as yours and my users would certainly benefit from some of the information you present here. Please let me know if this okay with you. Regards!

Here is my web page :: [camping water filter](https://oztweets.com/TaOFlahert "camping water filter")

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.