Today I’ll be covering Linked List data structure in JavaScript. Even though it’s not native to JS, knowing it is essential to being a good engineer.
A linked list is a sequential collection of elements. Each element is called a node. Every node has a pointer to the following node and/or the previous node. The first element is called the head node and the last element is called the tail node.
The 3 most common types of Linked List are Singly Linked List, Doubly Linked List and Circular Linked List.
As you can see in the image above, in the Singly LL, the tail points to null. In the Doubly LL, both the head and tail point to null. In the Circular LL, the head and tail point to each other rather than null.
So, why should we use linked lists to store data instead of arrays? The main difference between them is how they are stored in memory.
Arrays store all elements in a contiguous block of memory, which means each element of an array is located right next to each other. Because of this, an array provides direct (aka random) access to any element. For example, to get element 10 we can just jump directly to that position and grab it without having to step through the first 9 elements.
In linked lists, on the other hand, elements can be stored anywhere in memory. Because of this, a linked list only provides sequential access such that we can’t just directly jump to a certain position. To get the 10th node, you need to first step through the other 9 elements.
This is one of the drawbacks of using linked lists. Nevertheless, they are still extremely useful in that they add and remove elements much faster than arrays.
When adding an element in an array, if a block of memory is occupied by something else, then the entire array might have to be relocated in order to keep the contiguous block of memory. In a linked list, all you need to add an element is to make a new node anywhere in the memory and make the previous element point to it. That way, you never have to move your elements. To delete an element, just change what the preceding element points to.
Another difference between linked lists and arrays is the time complexity, as demonstrated in the table below.
Top comments (0)