In JavaScript, a linked list is a linear data structure consisting of a sequence of elements, called nodes, where each node contains a value and a reference (or pointer) to the next node in the sequence. Linked lists provide dynamic memory allocation and efficient insertion and deletion operations compared to arrays.
Structure:
- Node: Each node in a linked list contains two components:
- Value: Holds the data or value associated with the node.
- Next Pointer: Points to the next node in the sequence. If the next node does not exist, the pointer is typically set to
nullto indicate the end of the list.
Types of Linked Lists:
Singly Linked List: In a singly linked list, each node has a reference to the next node in the sequence.
[Node1] -> [Node2] -> [Node3] -> ... ->
[NodeN] -> null
Doubly Linked List: In a doubly linked list, each node has references to both the next and the previous nodes.
null <- [Node1] <-> [Node2] <-> [Node3]
<-> ... <-> [NodeN] -> null
- Circular Linked List: In a circular linked list, the last node points back to the first node, forming a circular structure.
Operations:
Insertion:
- At the Beginning: Insert a new node at the beginning of the list by updating the next pointer of the new node to point to the current head, and then updating the head to point to the new node.
- At the End: Insert a new node at the end of the list by traversing the list until reaching the last node, and then updating the next pointer of the last node to point to the new node.
- At a Specific Position: Insert a new node at a specific position in the list by traversing the list until reaching the desired position, and then adjusting the next pointers accordingly.
Deletion:
- At the Beginning: Remove the first node in the list by updating the head to point to the next node.
- At the End: Remove the last node in the list by traversing the list until reaching the second-to-last node and updating its next pointer to
null. - At a Specific Position: Remove a node at a specific position in the list by traversing the list until reaching the node before the target node, and then adjusting the next pointers accordingly.
Traversal: Traverse the linked list from the beginning to the end, visiting each node in the sequence.
Example Implementation (Singly Linked List):
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
insertAtBeginning(value) {
let newNode = new Node(value);
newNode.next = this.head;
this.head = newNode;
}
insertAtEnd(value) {
let newNode = new Node(value);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
display() {
let current = this.head;
while (current !== null) {
console.log(current.value);
current = current.next;
}
}
}
// Example usage:
let linkedList = new LinkedList();
linkedList.insertAtEnd(10);
linkedList.insertAtEnd(20);
linkedList.insertAtBeginning(5);
linkedList.display();
