Intro to Linked Lists via JavaScript - Part 1: Overview

As your application and data becomes increasingly complex, being restricted to basic arrays will become a major bottleneck in performance and in what you’re able to accomplish. We’re going to need to develop something greater than the most basic out-of-the-box data type that JavaScript offers us. With linked lists, we can build the foundation for learning more advanced data structures and algorithms.

Concept

Linked lists are a special way of using classes to create chains of connected objects. Each of these objects contains two pointers, one to the next node and one to the previous node.

While arrays allow you to access an item directly by its index, which is always O(1), our nodes don’t have indexes so we would need to start from the head or tail of the list and use the pointers to search through each item for the one we want to change, so O(n).

Why would we ever want a linked list over an array? Arrays are superior when it comes to searching and sorting, because it’s easier to directly access and move items. Linked lists are much more efficient for inserting and deleting items, particularly at the ends. When you insert or remove an item into an array your computer also needs to re-index the rest of the data, giving us O(n), with linked lists can do it in O(1) plus the search time, which we have a few ways to optimize.

Many browsers use a linked list to record your search history, since it’s much more practical for moving up and down a chain when the users rarely need to search for anything or see the whole thing.

While an array would let you access Google again directly, a linked list forces you to either set it as the new tail or to manually traverse back through to what you want, we cannot jump over anything in between.

Singly vs Doubly Linked Lists

There are two main ways we can setup our linked lists, either with one pointer, forcing it into one direction, or two, making it bi-directional.

Searching through a singly linked list requires us to look at each item for what we want, while a doubly linked list can start the search from the head or tail depending on which half the item is on, giving us O(n / 2).

Doubly linked lists also require more memory since each item has to store pointers for the next and previous items, which can mean a big difference if you’re storing a lot of data.

Later, when we implement linked lists in other structures we’ll mostly use singly linked lists. For example, in stack and queues we only interact with the ends and have very little need to traversing the whole list, so two pointers would just be impractical.

Why Bother?

• Linked lists act as the foundation for more sophisticated data structures such as stacks, queues, trees, graphs, and heaps. All of which have ways to build on the benefits of linked lists while nullifying some of their downsides, depending on your intended usage.
• They have much better performance over arrays when you need to make a lot of additions and deletions and better search times when paired with other techniques such as using skip lists.
• Easily creating a looped list by setting the next pointer on the tail to the head, such as in a carousel component.

Conclusion

Hopefully after this short introduction you’re ready to start exploring some better alternatives to your standard arrays. Check out Part 2 to learn how to start implementing a fully decked-out doubly linked list in JavaScript.