Linked List with Typescript
What is a linked list?
A linked list is a data structure that holds objects arranged in a linear order, this order is determined by a pointer in each node. Unlike an array, a linked list doesn’t provide constant-time access to a particular index, you have to iterate through the list to find an element, on the other hand, is possible to add and remove items from the beginning of the list in a constant time. Linked lists can be used to implement other data structures, such as stacks, queues, and graphs.
There are some types of linked lists:
- Singly linked list — Each node has only a pointer to the next node.
- Doubly linked list — Each node has pointers to both the previous and next node.
- Circular linked list — The last node points to the first element.
Let’s focus on implementation directly
Nodes
Every item of the linked list is a node. Let’s create a Node
class first.
Since we are working on the doubly linked list our Node
has next
and prev
fields, that point to another node or null
. Also a Node
contains our data, which has a generic type T
.
Linked list’s implementation
Here is how the final version of the linked list will look like.
Practical Applications
Linked lists serve a variety of purposes in the real world. They can be used to implement (spoiler alert!) queues or stacks as well as graphs. They’re also useful for much more complex tasks, such as lifecycle management for an operating system application.
React Hooks under the hood use doubly linked list. It allows you to use and set state with the intention to help you reuse stateful logic between components.
Applications of Linked Lists in the Real World :
- You must be reading this article on your web browser, and in web browsers, we open multiple URLs, and we can easily switch between those URLs using the previous and next buttons because they are connected using a linked list.
- In music players, we can create our song playlist and can play a song either from starting or ending of the list. And these music players are implemented using a linked list.
- We watch the photos on our laptops or PCs, and we can simply see the next or previous images easily. This feature is implemented using a linked list.
challenge yourself — leetcode.com