// Tutorial //

Intro to Linked Lists via JavaScript - Part 1: Overview

Published on February 21, 2020
Default avatar
By Joshua Hall
Developer and author at DigitalOcean.
Intro to Linked Lists via JavaScript - Part 1: Overview

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

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.

Linked List Diagram

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.

History with Linked List Diagram

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.


Want to learn more? Join the DigitalOcean Community!

Join our DigitalOcean community of over a million developers for free! Get help and share knowledge in our Questions & Answers section, find tutorials and tools that will help you grow as a developer and scale your project or business, and subscribe to topics of interest.

Sign up
About the authors
Default avatar
Developer and author at DigitalOcean.

Still looking for an answer?

Was this helpful?
Leave a comment

This textbox defaults to using Markdown to format your answer.

You can type !ref in this text area to quickly search our full set of tutorials, documentation & marketplace offerings and insert the link!