Introduction to Linked List in JavaScript
A Linked List is a linear data structure where elements are connected using pointers and stored in different memory locations (not side by side like arrays).
Just like arrays, linked lists store data in a sequence. The difference is that array elements are stored in a continuous block of memory, while linked list elements (called nodes) can be scattered in memory but are connected together using links (pointers).
Structure of a Linked List Node
Each node in a linked list has two parts:
- Data → stores the value of the node.
- Next Pointer → stores the reference (address) of the next node in the list.
Why Use Linked Lists Instead of Arrays?
-
Flexible size:
In many programming languages like C, C++, or Java, arrays have a fixed size and memory is reserved in advance.
But in JavaScript, arrays are dynamic and can grow or shrink.
Still, linked lists provide more flexibility in certain cases where frequent insertion and deletion operations are needed. -
Easy insertion and deletion:
In arrays, inserting or deleting an element often means shifting many elements, which is slow.
Example:
id[] = [1000, 1010, 1050, 2000, 2040]To insert 1005 in order, elements after 1000 must be shifted.
In a linked list, nodes can be inserted or deleted by just changing the pointers, without shifting.
Limitations of Linked Lists
- No direct access: You can’t jump to any element directly like in arrays. You must start from the first node and go step by step.
- Extra memory needed: Each node stores not just the data but also a pointer, which uses extra space.
- Not cache-friendly: Arrays are faster for some operations because their elements are stored next to each other in memory. Linked lists don’t have this advantage.
How Linked Lists Are Represented
A linked list starts with a head node, which points to the first node in the list.
If the list is empty, the head is NULL.
Each node contains:
- Data
- Pointer to the next node