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.
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.
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.
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.
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.
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!
Sign up for Infrastructure as a Newsletter.
Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.
Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.