Tutorial

Intro to Linked Lists via JavaScript - Part 1: Overview

Published on February 21, 2020
author

Joshua Hall

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.

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.

Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.

Learn more about our products

About the authors
Default avatar
Joshua Hall

author

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.

Still looking for an answer?

Ask a questionSearch for more help

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!

Try DigitalOcean for free

Click below to sign up and get $200 of credit to try our products over 60 days!

Sign up

Join the Tech Talk
Success! Thank you! Please check your email for further details.

Please complete your information!

Featured on Community

Get our biweekly newsletter

Sign up for Infrastructure as a Newsletter.

Hollie's Hub for Good

Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.

Become a contributor

Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

Welcome to the developer cloud

DigitalOcean makes it simple to launch in the cloud and scale up as you grow — whether you're running one virtual machine or ten thousand.

Learn more