A linked list is a linear data structure used to store and organize data. Elements are not stored at contiguous memory locations. It consists of a series of nodes, where each node contains two main components: the data and a reference (or pointer) to the next node in the sequence.
Types of Linked List:
1. Singly Linked List
- In a singly linked list, each node contains data and a reference to the next node in the list.
- The last node points to null, indicating the end of the list.
- Singly linked lists are efficient for insertion and deletion at the beginning or end but require linear traversal for accessing elements in the middle.
Code Implementation of Singly Linked List:
Creation and Traversal of Singly Linked List:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
}
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;
}
}
display() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
// Example usage:
const linkedList = new SinglyLinkedList();
linkedList.append(10);
linkedList.append(20);
linkedList.append(30);
linkedList.display(); // Output: 10, 20, 30
Time Complexity: O(N)
Auxiliary Space: O(N)
2. Doubly Linked List
- In a doubly linked list, each node has references to both the previous and next nodes.
- This allows for efficient traversal in both directions but requires additional memory to store the previous pointers.
Code Implementation of Doubly Linked List:
Creation and Traversal of Doubly Linked List:
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
}
display() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
// Example usage:
const linkedList = new DoublyLinkedList();
linkedList.append(10);
linkedList.append(20);
linkedList.append(30);
linkedList.display(); // Output: 10, 20, 30
Time Complexity:
The time complexity of the append() function is O(1) as it performs constant-time operations to insert a new node at the beginning of the doubly linked list. The time complexity of the display() function is O(n) where n is the number of nodes in the doubly linked list. This is because it traverses the entire list twice, once in the forward direction and once in the backward direction. Therefore, the overall time complexity of the program is O(n).
Space Complexity:
The space complexity of the program is O(n) as it uses a doubly linked list to store the data, which requires n nodes. Additionally, it uses a constant amount of auxiliary space to create a new node in the append() function. Therefore, the overall space complexity of the program is O(n).
3. Circular Linked List
- In a circular linked list, the last node points back to the head, forming a loop.
- This allows for continuous traversal without reaching the end, but requires extra care to handle insertions and deletions.
Code Implementation of Circular Linked List:
Creation and Traversal of Circular Linked List:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class CircularSinglyLinkedList {
constructor() {
this.head = null;
}
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
newNode.next = this.head;
} else {
let current = this.head;
while (current.next !== this.head) {
current = current.next;
}
current.next = newNode;
newNode.next = this.head;
}
}
display() {
if (!this.head) {
console.log("List is empty.");
return;
}
let current = this.head;
do {
console.log(current.data);
current = current.next;
} while (current !== this.head);
}
}
// Example usage:
const linkedList = new CircularSinglyLinkedList();
linkedList.append(10);
linkedList.append(20);
linkedList.append(30);
linkedList.display(); // Output: 10, 20, 30
Time Complexity:
Insertion at the beginning of the circular linked list takes O(1) time complexity.
Traversing and printing all nodes in the circular linked list takes O(n) time complexity where n is the number of nodes in the linked list.
Therefore, the overall time complexity of the program is O(n).
Auxiliary Space:
The space required by the program depends on the number of nodes in the circular linked list.
In the worst-case scenario, when there are n nodes, the space complexity of the program will be O(n) as n new nodes will be created to store the data.
Additionally, some extra space is required for the temporary variables and the function calls.
Therefore, the auxiliary space complexity of the program is O(n).
4. Doubly Circular Linked List
A doubly circular linked list is a type of linked list in which each node has references to both the previous and next nodes, and the last node points back to the head, forming a loop. This allows for efficient traversal in both directions.
Code Implementation of Doubly Circular Linked List:
Creation and Traversal of Doubly Circular Linked List:
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyCircularLinkedList {
constructor() {
this.head = null;
}
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.head.next = this.head;
this.head.prev = this.head;
} else {
const lastNode = this.head.prev;
newNode.next = this.head;
newNode.prev = lastNode;
lastNode.next = newNode;
this.head.prev = newNode;
}
}
displayForward() {
if (!this.head) {
console.log("List is empty.");
return;
}
let current = this.head;
do {
console.log(current.data);
current = current.next;
} while (current !== this.head);
}
displayBackward() {
if (!this.head) {
console.log("List is empty.");
return;
}
let current = this.head.prev;
do {
console.log(current.data);
current = current.prev;
} while (current !== this.head.prev);
}
}
// Example usage:
const linkedList = new DoublyCircularLinkedList();
linkedList.append(10);
linkedList.append(20);
linkedList.append(30);
linkedList.displayForward(); // Output: 10, 20, 30
linkedList.displayBackward(); // Output: 30, 20, 10
Time Complexity:
- Insertion at the beginning or end: O(1)
- Inserting a node at the beginning or end of a doubly circular linked list takes constant time since we have direct access to the head and tail nodes.
- Insertion in the middle: O(N)
- Inserting a node in the middle of a doubly circular linked list requires finding the appropriate position, which may involve traversing through N/2 nodes on average, resulting in a linear time complexity.
- Deletion: O(1)
- Deleting a node from a doubly circular linked list, given a reference to the node, can be done in constant time since we can update the previous and next pointers directly.
- Searching: O(N)
- Searching for a specific element in a doubly circular linked list requires traversing through all the nodes until the element is found or the end of the list is reached, resulting in linear time complexity.
Space Complexity:
- The space complexity of a doubly circular linked list is O(N), where N is the number of nodes in the list.
- Each node in the list requires memory space to store its data and two pointers (prev and next). As the number of nodes increases, the space required also increases linearly.