A singly linked list is a linear data structure consisting of nodes connected in a sequential manner. Each node contains a value and a reference, called the “next” pointer, to the next node in the list. The first node in the list is called the head, and the last node is called the tail, which points to null to indicate the end of the list.
Unlike arrays, which use contiguous memory allocation, linked lists use dynamic memory allocation. This feature allows for efficient insertion and deletion of elements at any position within the list, making them a suitable choice for scenarios where frequent modifications are expected.
Key Characteristics of Singly Linked Lists
- Nodes: A node is a fundamental building block of a linked list. Each node contains a value and a pointer to the next node. In some implementations, a node may also contain additional metadata.
- Head: The head of the linked list represents the first node in the sequence. It serves as the entry point to access the list.
- Tail: The tail of the linked list represents the last node. Its “next” pointer points to null, indicating the end of the list.
- Traversal: To access or manipulate elements in a linked list, we typically start at the head and traverse the list by following the “next” pointers until we reach the desired node or the end of the list.
- Dynamic Size: Linked lists have a dynamic size, meaning they can grow or shrink as elements are inserted or removed.
Here’s an example implementation of a singly linked list in JavaScript:
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(2);
linkedList.append(5);
linkedList.append(3);
linkedList.append(7);
linkedList.display(); // Output: 2, 5, 3, 7
Common Operations on Singly Linked Lists
Here are the basic operations performed on a singly linked list, along with their time and space complexity analysis:
1.Insertion at the Head (prepend)
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
// ...
prepend(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
}
// ...
}
// Usage example
const linkedList = new LinkedList();
linkedList.prepend(2);
linkedList.prepend(1);
console.log(linkedList.toArray()); // Output: [1, 2]
- Time Complexity: O(1)
- Space Complexity: O(1)
2.Insertion at the Tail (append)
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
// ...
append(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
// ...
}
// Usage example
const linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
console.log(linkedList.toArray()); // Output: [1, 2, 3]
- Time Complexity: O(1)
- Space Complexity: O(1)
3.Deletion
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
// ...
delete(value) {
if (!this.head) {
return;
}
if (this.head.value === value) {
this.head = this.head.next;
if (!this.head) {
this.tail = null;
}
return;
}
let currentNode = this.head;
while (currentNode.next) {
if (currentNode.next.value === value) {
currentNode.next = currentNode.next.next;
if (!currentNode.next) {
this.tail = currentNode;
}
return;
}
currentNode = currentNode.next;
}
}
// ...
}
// Usage example
const linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.delete(2);
console.log(linkedList.toArray()); // Output: [1, 3]
- Time Complexity: O(n)
- Space Complexity: O(1)
4.Traversal
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
// ...
traverse() {
let currentNode = this.head;
while (currentNode) {
console.log(currentNode.value);
currentNode = currentNode.next;
}
}
// ...
}
// Usage example
const linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.traverse();
// Output:
// 1
// 2
// 3
- Time Complexity: O(n)
- Space Complexity: O(1)
The time complexity of these basic operations on a singly linked list depends on the size of the list (n). The prepend and append operations have a time complexity of O(1) since they directly modify.
Conclusion
Singly linked lists offer a versatile and efficient approach for managing collections of data elements. They excel in scenarios where frequent insertions and deletions are required. By understanding the basic principles, characteristics, and operations of singly linked lists, you can leverage them effectively in your software development projects. Remember to consider the time and space complexities of operations to ensure optimal performance.