Data Structures and Algorithms in JavaScript : Linked List
A Linked List is a linear data structure commonly used in computer science to store and manage a collection of elements. Unlike arrays, which use contiguous memory locations to store data, a linked list consists of a series of nodes, where each node contains both data and a reference (or pointer) to the next node in the sequence. This data structure is flexible and can grow or shrink dynamically, making it an essential tool in various applications.
Key characteristics of a linked list:
1. **Nodes:** Each element in a linked list is called a node. A node typically contains two fields: the data or value it stores and a reference (pointer) to the next node in the list.
2. **Head:** The first node in the linked list is called the head. It serves as the starting point for traversing the list.
3. **Tail:** The last node in the linked list is called the tail. In a singly linked list (where nodes have references to the next node only), the tail’s reference is typically set to `null`.
4. **Singly Linked Lists:** In a singly linked list, each node has a reference to the next node in the list, forming a unidirectional sequence.
5. **Doubly Linked Lists:** In a doubly linked list, each node has references to both the next and the previous nodes, allowing bidirectional traversal.
Linked lists are useful for various applications, including dynamic memory allocation, implementing data structures like stacks and queues, managing large datasets, and representing certain types of data structures in computer science. They provide dynamic memory allocation and efficient insertions and deletions, making them particularly valuable for scenarios where the size of the data structure may change frequently.
Linked lists have their own set of advantages and disadvantages based on their characteristics and use cases. Here are some of the pros and cons of using linked lists:
**Pros of Linked Lists:**
1. **Dynamic Size:** Linked lists can grow or shrink dynamically, making them suitable for situations where the size of the data structure needs to change frequently. This dynamic size feature allows efficient memory allocation and utilization.
2. **Efficient Insertions and Deletions:** Adding or removing elements in a linked list, especially when operating on elements in the middle of the list, is generally more efficient compared to arrays. It doesn’t require shifting of elements as it does with arrays.
3. **No Fixed Size:** Linked lists do not have a fixed size, and you can keep adding elements as long as there is available memory.
4. **Flexible Memory Allocation:** Linked lists allow for flexible memory allocation since each node can be allocated separately. This is particularly useful in languages where memory allocation is a concern.
5. **Constant-Time Insertions and Deletions at Head:** In a singly linked list, inserting or deleting an element at the head of the list can be done in constant time.
**Cons of Linked Lists:**
1. **Inefficient Random Access:** Accessing elements in a linked list by index is not as efficient as in arrays. You need to traverse the list from the head (or tail) to reach the desired element, which can take O(n) time, where n is the number of elements.
2. **Higher Memory Overhead:** Linked lists require extra memory for the storage of pointers or references, which can result in higher memory overhead compared to arrays.
3. **Cache Performance:** Accessing elements in a linked list may not utilize the CPU cache efficiently due to non-contiguous memory storage.
4. **Complexity:** Managing linked lists can be more complex than arrays due to the need to handle pointers and node management.
5. **Lack of Direct Access to Previous Elements:** In singly linked lists, you cannot directly access the previous element of a given node. For such access, you would need to use a doubly linked list.
In summary, linked lists are a versatile data structure with advantages such as dynamic size, efficient insertions and deletions, and flexible memory allocation. However, they are not the best choice for all scenarios, particularly when direct access to elements by index or cache performance is crucial. Your choice of data structure should depend on the specific requirements of your problem.
Implementation of Linked List(using Classes).
(1) Creating a Linked List.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}(2) Append : Append an element to the end of the list.
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
}(3) Prepend : Prepend an element to the beginning of the list.
prepend(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}(4) Insert : Insert an element at a specific index.
insertAtIndex(data, index) {
if (index < 0) {
console.log("Invalid index");
return;
}
const newNode = new Node(data);
if (index === 0) {
newNode.next = this.head;
this.head = newNode;
return;
}
let current = this.head;
let count = 0;
while (current) {
if (count === index - 1) {
newNode.next = current.next;
current.next = newNode;
return;
}
current = current.next;
count++;
}
console.log("Index out of bounds, element not inserted");
}(5) Delete : Delete an element by value.
delete(data) {
if (!this.head) {
return;
}
if (this.head.data === data) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
current.next = current.next.next;
return;
}
current = current.next;
}
}(6) Search : Search for an element by value and return the first occurrence.
search(data) {
let current = this.head;
while (current) {
if (current.data === data) {
return current;
}
current = current.next;
}
return null;
}(7) Display : Display the elements in the linked list.
display() {
const elements = [];
let current = this.head;
while (current) {
elements.push(current.data);
current = current.next;
}
console.log(elements.join(" -> "));
}
}Example :
const myList = new LinkedList();
myList.append(1);
myList.append(2);
myList.append(3);
myList.insertAtIndex(1.5, 1);
myList.display(); // Output: 1 -> 1.5 -> 2 -> 3
