By Joshua Hall
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.
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
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.
Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.