Linked Lists: The Backbone of Dynamic Data Structures
Linked lists are fundamental data structures that underpin many complex algorithms and applications. They provide a flexible way to store a collection of items, making it easy to insert and delete elements. Unlike arrays, linked lists don't require contiguous memory allocation, which can be a significant advantage when managing large datasets. In this article, we'll explore the basics of linked lists, different types of linked lists, and their operations with examples in TypeScript and C.
What is a Linked List?
A linked list is a linear data structure where each element is a separate object, known as a node. Each node contains:
- Data: The value stored in the node.
- Next: A reference (or pointer) to the next node in the sequence.
The primary advantage of linked lists over arrays is their dynamic size and ease of insertion/deletion. However, they don't provide direct access to elements by index, requiring traversal to access specific elements.
Types of Linked Lists
1. Singly Linked List: Each node points to the next node.
2. Doubly Linked List: Each node points to both the next and the previous node.
3. Circular Linked List: The last node points back to the first node.
Linked List Operations
Singly Linked List Operations
1. Insertion
- At the Beginning:
Inserting a node at the beginning of a linked list is straightforward. The new node's next pointer is set to the current head of the list, and then the head is updated to point to the new node. This operation takes constant time, O(1), because it doesn't depend on the size of the list.
// TypeScript
class Node {
constructor(public data: any, public next: Node | null = null) {}
}
class SinglyLinkedList {
head: Node | null = null;
insertAtBeginning(data: any) {
const newNode = new Node(data, this.head);
this.head = newNode;
}
}
const list = new SinglyLinkedList();
list.insertAtBeginning(10);
console.log(list.head); // Node { data: 10, next: null }
// C
typedef struct Node {
int data;
struct Node* next;
} Node;
void insertAtBeginning(Node** head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = *head;
*head = newNode;
}
Node* head = NULL;
insertAtBeginning(&head, 10);
printf("%d\n", head->data); // 10
- At the End:
Inserting a node at the end of a linked list requires traversing the list to find the last node and then updating its next pointer to point to the new node. This operation takes O(n) time, where n is the number of nodes in the list, because you have to traverse the entire list.
// TypeScript
class SinglyLinkedList {
head: Node | null = null;
insertAtEnd(data: any) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
}
const list = new SinglyLinkedList();
list.insertAtEnd(20);
console.log(list.head); // Node { data: 10, next: Node { data: 20, next: null } }
// C
void insertAtEnd(Node** head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
insertAtEnd(&head, 20);
printf("%d\n", head->next->data); // 20
2. Deletion
- From the Beginning:
Deleting a node from the beginning of a linked list involves updating the head to point to the second node in the list. This operation takes constant time, O(1), because it only involves updating one pointer.
// TypeScript
class SinglyLinkedList {
head: Node | null = null;
deleteFromBeginning() {
if (this.head) {
this.head = this.head.next;
}
}
}
list.deleteFromBeginning();
console.log(list.head); // Node { data: 20, next: null }
// C
void deleteFromBeginning(Node** head) {
if (*head != NULL) {
Node* temp = *head;
head = (head)->next;
free(temp);
}
}
deleteFromBeginning(&head);
printf("%d\n", head->data); // 20
- From the End:
Deleting a node from the end of a linked list requires traversing the list to find the second-to-last node and then updating its next pointer to null. This operation takes O(n) time because you have to traverse the entire list.
// TypeScript
class SinglyLinkedList {
head: Node | null = null;
deleteFromEnd() {
if (!this.head) return;
if (!this.head.next) {
this.head = null;
return;
}
let current = this.head;
while (current.next && current.next.next) {
current = current.next;
}
current.next = null;
}
}
list.deleteFromEnd();
console.log(list.head); // Node { data: 10, next: null }
// C
void deleteFromEnd(Node** head) {
if (*head == NULL) return;
if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}
Node* current = *head;
while (current->next->next != NULL) {
current = current->next;
}
free(current->next);
current->next = NULL;
}
deleteFromEnd(&head);
printf("%d\n", head->data); // 10
3. Search
- By Value:
Searching for a node by value involves traversing the list and comparing each node's data with the target value. This operation takes O(n) time because, in the worst case, you might have to check every node.
// TypeScript
class SinglyLinkedList {
head: Node | null = null;
search(data: any): Node | null {
let current = this.head;
while (current) {
if (current.data === data) {
return current;
}
current = current.next;
}
return null;
}
}
console.log(list.search(10)); // Node { data: 10, next: null }
// C
Node* search(Node* head, int data) {
Node* current = head;
while (current != NULL) {
if (current->data == data) {
return current;
}
current = current->next;
}
return NULL;
}
Node* foundNode = search(head, 10);
if (foundNode != NULL) {
printf("%d\n", foundNode->data); // 10
}
4. Update
- By Value:
Updating a node's value involves traversing the list to find the node with the target value and then updating its data. This operation takes O(n) time because, in the worst case, you might have to check every node.
// TypeScript
class SinglyLinkedList {
head: Node | null = null;
update(oldValue: any, newValue: any) {
let current = this.head;
while (current) {
if (current.data === oldValue) {
current.data = newValue;
return;
}
current = current.next;
}
}
}
list.update(10, 99);
console.log(list.head); // Node { data: 99, next: null }
// C
void update(Node* head, int oldValue, int newValue) {
Node* current = head;
while (current != NULL) {
if (current->data == oldValue) {
current->data = newValue;
return;
}
current = current->next;
}
}
update(head, 10, 99);
printf("%d\n", head->data); // 99
5. Traversal
- Print All Elements:
Traversing a linked list involves starting at the head and following the next pointers to visit each node. This operation takes O(n) time because you have to visit every node.
// TypeScript
class SinglyLinkedList {
head: Node | null = null;
traverse() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
list.traverse(); // 99
// C
void traverse(Node* head) {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
traverse(head); // 99
Conclusion
Linked lists are essential data structures that provide flexibility in managing collections of data. By understanding the basic operations of insertion, deletion, search, update, and traversal, you can efficiently manipulate linked lists in your programs. Whether you're using TypeScript or C, mastering linked lists will enhance your programming skills and open up new possibilities for dynamic data management.
Happy coding! ??