A Linked List is a dynamic data structure consisting of nodes connected using pointers. Unlike arrays, which have fixed sizes, linked lists can grow or shrink dynamically, making them highly flexible for managing data.
Features of Linked List
- Dynamic Size: The size of a linked list can be adjusted during runtime.
- Efficient Memory Use: Memory is allocated as needed, avoiding wastage.
- Non-contiguous Storage: Elements are not stored in adjacent memory locations.
- Efficient Insertion/Deletion: Operations are faster compared to arrays (no shifting of elements).
Components of a Linked List
- Node: The basic unit of a linked list containing:
- Data: The value stored in the node.
- Pointer: A reference to the next node in the list.
- Head: A pointer to the first node in the linked list.
- Tail: The last node, where the pointer is NULL.
Types of Linked Lists
- Singly Linked List: Each node points to the next node.
- Doubly Linked List: Each node points to both the next and the previous nodes.
- Circular Linked List: The last node points back to the first node.
Structure of a Node in C
struct Node {
int data; // Data part of the node
struct Node* next; // Pointer to the next node
};
Basic Operations on a Singly Linked List
- Insertion: Add a node at the beginning, end, or a specific position.
- Deletion: Remove a node from the beginning, end, or a specific position.
- Traversal: Visit all nodes in the list.
- Search: Find an element in the list.
Implementation of a Singly Linked List in C
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// Insert at the beginning
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = createNode(value);
newNode->next = *head;
*head = newNode;
printf(“Inserted %d at the beginning.\n”, value);
}
// Insert at the end
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = createNode(value);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
printf(“Inserted %d at the end.\n”, value);
}
// Delete a node
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;
// If head node itself holds the key
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
printf(“Deleted %d from the list.\n”, key);
return;
}
// Search for the key to be deleted
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// Key not found
if (temp == NULL) {
printf(“Element %d not found.\n”, key);
return;
}
// Unlink the node and free memory
prev->next = temp->next;
free(temp);
printf(“Deleted %d from the list.\n”, key);
}
// Display the linked list
void displayList(struct Node* head) {
struct Node* temp = head;
if (head == NULL) {
printf(“List is empty.\n”);
return;
}
printf(“Linked List: “);
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtBeginning(&head, 5);
displayList(head);
deleteNode(&head, 10);
displayList(head);
return 0;
}
Output Example
Inserted 10 at the end.
Inserted 20 at the end.
Inserted 5 at the beginning.
Linked List: 5 -> 10 -> 20 -> NULL
Deleted 10 from the list.
Linked List: 5 -> 20 -> NULL
Advantages of Linked Lists
- Dynamic Size: No need to declare the size in advance.
- Efficient Insert/Delete: No shifting is required as in arrays.
- Memory Utilization: Memory is allocated as needed.
Disadvantages of Linked Lists
- Memory Overhead: Requires extra memory for pointers.
- Sequential Access: Traversal is slower compared to arrays.
- Complex Implementation: More complex than arrays due to pointer manipulation.
Applications of Linked Lists
- Dynamic Memory Allocation: Managing memory in real-time.
- Data Structures: Used in stacks, queues, graphs, and more.
- Symbol Tables: Storing symbols in compilers.
- Sparse Matrices: Efficient storage of sparse data.
Summary
Linked lists are versatile, dynamic data structures ideal for applications where efficient insertion and deletion are required. While their implementation requires careful pointer management, they are a foundational concept in data structures and algorithms.