JavaScript Data Structures: Linked Lists (pt. 1)
This week, we’re moving onto another JavaScript data structure — Linked lists!
Linked lists are a bit complicated to comprehend at first, but once you learn it and figure out how to implement one, they’re quite simple, really!
You’ll encounter linked lists on a good amount of algorithm-based questions. I’ll tag a few LeetCode challenges below that I think are good problems to tackle. In the last part of my linked list blogs, I will be going over a traditional challenge — reversing a linked list! Stay tuned.
Let’s get started!
Basics of a Linked List
What is a linked list? They are another type of a linear data structure (like an array) but with features that make it easily distinguishable from an array.
Unlike arrays, elements in a linked list are not stored via an index. Instead, each element points to the next item in the linked list. An element in a linked list is commonly referred to as a node.
To break it down even further, linked lists only contain two items: its’ specific data value and the next node in the linked list. Because of this, you cannot search a linked list for a specific value based off its’ index simply because they don’t have an index (re: the ‘Cons’ section below).
Structurally, a linked list starts with a head node — this is the first value, or entry point, in the linked list. The last node in a linked list always points to null. If a linked list is empty, the head node will be a null reference.
Types of Linked Lists
There are three different types of linked lists:
- Singly linked lists: each node points only to the next node. Each node only has one pointer.
- Doubly linked lists: instead of only pointing to the next node, nodes will also point to the previous node. Each node has two pointers.
- Circular linked lists: instead of having the last node in the list point to null, it will instead point to either the head of the list or another node in the list — creating a loop.
Singly linked lists are the most basic form of linked lists and has been what I’ve been referring to in the bulk of this blog!
Pros
The main and often the only considered pro of a linked list is that nodes can be removed or added really easily — without having to worry about the structure of the list because you won’t have to reorganize the entire list. Instead, you just have to re-set the next value of the previous node to either the following node (if removing) or the new node + set the next value of the new node to the following node (if adding).
Cons
The biggest con of a linked list is that it has a really slow search time. In order to search for a value, you have to start with the head node in the list and keep looking at the next value until you reach the value you’re looking for. Unlike arrays, you cannot access a node in the middle of a linked list or by index value. I’ll go more into the details of traversing through a linked list in a future blog.
Another con of linked lists is that they do require more memory storage because of it’s additional value of knowing the next value.
Next week, I’ll discuss how to implement a linked list along with some helper methods.
LeetCode challenges to try (from easy → medium → hard)
