Singly Linked List
A singly linked list is a fundamental linear data structure and consists of a sequence of elements, where each element points to the next one in the sequence. The elements are not stored contiguously. It's called "singly" linked because it only has one reference or pointer, which points from one element to the next. Here are some key details about singly linked lists:
1.Node: The basic building block of a singly linked list is a node.Each node contains two parts:
Data: The actual data or value that the node holds.
Next Pointer/Reference: A reference or pointer to the next node in the sequence.
2.Head: The first node in the list is called the "head." It serves as the entry point to the list and is used to traverse the list by following the next pointers.
3.Tail: The last node in the list is called the "tail." The next pointer of the tail node typically points to a NULL value to indicate the end of the list.
4.Traversal: You can traverse a singly linked list by starting at the head and following the next pointers until you reach the end of the list (i.e., the node with a null reference).
5.Insertion: You can insert a new node at various positions in a singly linked list, such as at the beginning (changing the head), at the end (updating the tail's next pointer), or in the middle (adjusting the next pointers of adjacent nodes).
6.Deletion: You can delete a node from a singly linked list by updating the next pointer of the preceding node to skip the node you want to remove.
Advantages:
Dynamic Size: Singly linked lists can easily grow or shrink in size during runtime since memory allocation for each node is done dynamically. This makes them flexible for managing data.
Efficient Insertions and Deletions: Inserting or deleting elements at the beginning of a singly linked list is an O(1) operation, as it only requires updating a few pointers. This makes them suitable for use as stacks and queues.
Low Memory Overhead: Singly linked lists have relatively low memory overhead compared to data structures like arrays or doubly linked lists, as they only require a single pointer per element.
Easy to Implement: Singly linked lists are relatively simple to implement and understand, making them a good choice for introductory data structure exercises and educational purposes.
Memory Allocation Flexibility: Each node in a singly linked list can be allocated separately, allowing for efficient memory management in systems with limited memory resources.
Disadvantages:
No Random Access: Unlike arrays, accessing elements in a singly linked list by their index is inefficient. To access an element, you have to traverse the list from the beginning, resulting in O(n) time complexity for search operations.
Inefficient Reversal: Reversing a singly linked list requires traversing the entire list and changing the pointers, resulting in O(n) time complexity. In contrast, doubly linked lists make reversing easier.
Memory Overhead for Pointers: Singly linked lists use memory to store pointers (references) to the next element, which can lead to higher memory consumption compared to arrays, especially for small data types.
Lack of Bidirectional Traversal: Unlike doubly linked lists, singly linked lists can only be traversed in one direction, from the head to the tail. Bidirectional traversal is not possible without additional data structures or modifications.
Difficulty in Acessing the Last Element: Deleting the last element or adding at the end of a singly linked list can be inefficient, as you need to traverse the list.O(n) complexity.
Applications:
Dynamic Data Structures: Singly linked lists are the building blocks for implementing more complex dynamic data structures, such as stacks, queues, and symbol tables.
Memory Management: Operating systems use linked lists to manage memory allocation. Free memory blocks can be maintained in a linked list, and when a program requests memory, it can be allocated from these blocks.
File Systems: Singly linked lists are used to represent the structure of directories and files in file systems. Each directory can contain a linked list of files or subdirectories.
Music and Video Playlists: Playlists in music and video players are often implemented as singly linked lists. Each node represents a song or video, with a pointer to the next item in the list.
Garbage Collection: Some garbage collection algorithms use singly linked lists to keep track of allocated memory blocks. When memory is no longer needed, it can be easily freed.
Hash Tables: In certain implementations of hash tables, singly linked lists are used to handle collisions when two keys hash to the same index. Each index in the hash table can be a singly linked list of key-value pairs.
Resource Management: In resource allocation systems, singly linked lists can be used to track the allocation and deallocation of resources.
Graph Algorithms: In some graph algorithms like Breadth-First Search (BFS), singly linked lists are used to represent adjacency lists, facilitating efficient traversal of graph nodes.
Operating System Process Control Blocks: In operating systems, singly linked lists are used to manage process control blocks (PCBs), which store information about each process in the system.
Linked List Vs Array
Linked lists and arrays each have their own advantages and disadvantages, and the choice between them depends on the specific needs of your application. Here are some reasons why you might choose to use a linked list over an array:
Dynamic Size: Linked lists can easily grow or shrink in size during runtime because they allocate memory for each node dynamically. In contrast, arrays have fixed sizes in most programming languages, which can be inefficient if you don't know the size of your data in advance or if it changes frequently.
Memory Efficiency: Linked lists can be more memory-efficient than arrays when you have sparse data or when the data size varies significantly. Linked lists only allocate memory for the data and the next pointer/reference, while arrays allocate memory for the entire fixed-size structure.
Insertions and Deletions: Linked lists are efficient for insertions and deletions at arbitrary positions, especially at the beginning, which can be done in constant time (O(1)). Arrays require shifting elements, resulting in a time complexity of O(n) for such operations.
No Wasted Space: Linked lists allocate memory exactly as needed, whereas arrays might have unused or wasted space if you preallocate a large array but only use a fraction of it.
No Need for Copying: Inserting or removing elements from the middle of an array requires shifting elements, which can be slow and requires copying data. Linked lists avoid this issue by simply updating pointers.
No Need for Reallocation: Arrays may require reallocation and copying of data when they reach their capacity. Linked lists do not have this problem since they allocate memory for each element separately.
Easier to Resize: If you need to resize a dynamic data structure, linked lists are often easier to resize than arrays, which may require creating a new larger array and copying data.
Versatility: Linked lists can be used to implement other data structures like stacks, queues, and symbol tables more easily than arrays due to their dynamic nature.
However, it's important to note that linked lists also have their disadvantages. For instance, they have slower access times (O(n)) compared to arrays (O(1)) for random access, and they have a higher memory overhead due to the need for pointers/references. The choice between linked lists and arrays depends on the specific requirements of your application, and sometimes a combination of both data structures is used to take advantage of their respective strengths.
The choice of using a singly linked list or another data structure depends on the specific requirements of your application and the trade-offs you are willing to make in terms of time complexity, memory usage, and ease of implementation.
Defining the node
struct Node {
int data;
struct Node* next;
};
Algorithms
1. Insertion at the Beginning:
Create a new node with the given data.
Set the next pointer of the new node to point to the current head of the list.
Update the head of the list to be the new node.
struct Node* insertAtBeginning(struct Node* head, int newData)
{
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData; // Set the next of the new node to the current head
newNode->next = head; // Update the head to the new node
head = newNode; // Return the updated head
return head;
}
2. Insertion at the End:
Create a new node with the given data.
If the list is empty (head is NULL), make the new node the head of the list.
Otherwise, traverse the list until you reach the last node (the node whose next pointer is NULL).
Set the next pointer of the last node to point to the new node.
// Function to insert a node at the end of a linked list
struct Node* insertAtEnd(struct Node* head, int newData) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;
// If the list is empty, make the new node the head
if (head == NULL) { head = newNode; }
else {
// Traverse to the end of the list
struct Node* current = head;
while (current->next != NULL)
{ current = current->next; }
// Insert the new node at the end
current->next = newNode; }
// Return the head of the updated list
return head;
}
3. Insertion at a Specific Position:
3. Insertion at a Specific Position:
Create a new node with the given data.
If the specified position is 0, make the new node the new head of the list.
Otherwise, traverse the list while keeping track of the current node and its position.
Stop when you reach the node just before the desired position.
Update the next pointers to insert the new node at the specified position.
// Function to insert a node at a specific position in a linked list struct Node* insertAtPosition(struct Node* head, int newData, int position)
{
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;
// Special case: Insert at the beginning
if (position == 1) { newNode->next = head; return newNode; }
// General case: Traverse to the specified position
struct Node* current = head;
for (int i = 1; i < position - 1 && current != NULL; i++)
{ current = current->next; }
// Insert the new node at the specified position
if (current == NULL)
{ // Position is beyond the end of the list, do nothing or handle accordingly.
free(newNode);
return head;
}
newNode->next = current->next;
current->next = newNode;
// Return the head of the updated list
return head;
}
4. Deletion by Value:
Start from the head of the list and keep track of the current node and the previous node.
If the value to be deleted is in the head node, update the head to point to the next node and free the memory of the old head.
Otherwise, iterate through the list until you find the node with the desired value or reach the end of the list.
Update the next pointer of the previous node to skip the node with the desired value.
Free the memory of the node with the desired value if found.
// Function to delete a node with a specific value in a linked list struct Node* deleteNodeByValue(struct Node* head, int valueToDelete)
{
// Special case: If the list is empty, do nothing
if (head == NULL) { return NULL; }
// Special case: If the node to be deleted is the head
if (head->data == valueToDelete)
{ struct Node* newHead = head->next;
free(head);
return newHead;
}
// General case: Traverse the list to find the node to be deleted
struct Node* current = head;
while (current->next != NULL && current->next->data != valueToDelete)
{ current = current->next; }
// If the value is not found, do nothing
if (current->next == NULL) { return head; }
// Delete the node with the specified value
struct Node* nodeToDelete = current->next;
current->next = current->next->next;
free(nodeToDelete);
// Return the head of the updated list
return head;
}
// Function to print the linked list
5. Traversal:
Start from the head of the list.
While the current node is not NULL, do the following:
Print the data stored in the current node.
Move to the next node by following the next pointer.
Continue this process until you reach the end of the list (i.e., the next pointer of the current node is NULL).
void printList(struct Node* head)
{
struct Node* current = head;
while (current != NULL)
{
printf("%d---> ", current->data);
current = current->next; }
printf("NULL\n");
}
Complexity Analysis
1. Traversal:
3. Insertion at the End:
4. Deletion at the Beginning:
1. Traversal:
Time Complexity: O(n) where n is the number of nodes in the linked list. This is because we visit each node once.
Space Complexity: O(1) as we use a constant amount of extra space (only a few pointers).
2. Insertion at the Beginning:Time Complexity: O(1) since we are inserting at the beginning, and the operation doesn't depend on the size of the list.
Space Complexity: O(1) for the same reason.3. Insertion at the End:
Time Complexity: O(n) in the worst case, where n is the number of nodes. This is because we may need to traverse the entire list to find the last node.
Space Complexity: O(1) as we only use a constant amount of extra space.4. Deletion at the Beginning:
Time Complexity: O(1) since we are deleting from the beginning, and the operation doesn't depend on the size of the list.
Space Complexity: O(1).
Space Complexity: O(1).
5. Deletion at the End:
Time Complexity: O(n) in the worst case, similar to insertion at the end. We may need to traverse the entire list to find the second-to-last node.
Space Complexity: O(1).6.Insertion at a Specific Position:
Time Complexity: O(n), where n is the number of nodes in the linked list.
In the worst case, you may need to traverse the list to find the node at the specified position, and this traversal takes linear time. The actual insertion operation, once the position is found, is constant time.
C Program- Singly Linked List Implementation
/*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Function to insert a node at the beginning of a linked list
struct Node* insertAtBeginning(struct Node* head, int newData) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
// Set the next of the new node to the current head
newNode->next = head;
// Update the head to the new node
head = newNode;
// Return the updated head
return head;
}
// Function to insert a node at the end of a linked list
struct Node* insertAtEnd(struct Node* head, int newData) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;
// If the list is empty, make the new node the head
if (head == NULL) {
head = newNode;
} else {
// Traverse to the end of the list
struct Node* current = head;
while (current->next != NULL) {
current = current->next;
}
// Insert the new node at the end
current->next = newNode;
}
// Return the head of the updated list
return head;
}
// Function to insert a node at a specific position in a linked list
struct Node* insertAtPosition(struct Node* head, int newData, int position) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;
// Special case: Insert at the beginning
if (position == 1) {
newNode->next = head;
return newNode;
}
// General case: Traverse to the specified position
struct Node* current = head;
for (int i = 1; i < position - 1 && current != NULL; i++) {
current = current->next;
}
// Insert the new node at the specified position
if (current == NULL) {
// Position is beyond the end of the list, do nothing or handle accordingly.
free(newNode);
return head;
}
newNode->next = current->next;
current->next = newNode;
// Return the head of the updated list
return head;
}
// Function to delete a node with a specific value in a linked list
struct Node* deleteNodeByValue(struct Node* head, int valueToDelete) {
// Special case: If the list is empty, do nothing
if (head == NULL) {
return NULL;
}
// Special case: If the node to be deleted is the head
if (head->data == valueToDelete) {
struct Node* newHead = head->next;
free(head);
return newHead;
}
// General case: Traverse the list to find the node to be deleted
struct Node* current = head;
while (current->next != NULL && current->next->data != valueToDelete) {
current = current->next;
}
// If the value is not found, do nothing
if (current->next == NULL) {
return head;
}
// Delete the node with the specified value
struct Node* nodeToDelete = current->next;
current->next = current->next->next;
free(nodeToDelete);
// Return the head of the updated list
return head;
}
// Function to print the linked list
void printList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d--> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// Main function for testing
int main() {
// Initialize an empty linked list
struct Node* head = NULL;
// Insert nodes at the beginning
head = insertAtBeginning(head, 3);
head = insertAtBeginning(head, 2);
head = insertAtBeginning(head, 1);
// Print the linked list
printf("Linked List after Insertion at the Beginning: ");
printList(head);
// Insert nodes at the end
head = insertAtEnd(head, 4);
head = insertAtEnd(head, 5);
// Print the linked list
printf("Linked List after Insertion at the End: ");
printList(head);
// Insert nodes at specific positions
head = insertAtPosition(head, 10, 3);
head = insertAtPosition(head, 7, 5);
// Print the linked list
printf("Linked List after Insertion at Specific Positions: ");
printList(head);
// Delete a node with a specific value
int valueToDelete = 4;
head = deleteNodeByValue(head, valueToDelete);
// Print the linked list after deletion
printf("Linked List after Deletion of %d: ", valueToDelete);
printList(head);
return 0;
}
Comments
Post a Comment