Linked lists are fundamental data structures in computer science, offering a dynamic and flexible way to store and manipulate data. In this comprehensive guide, we'll dive deep into the world of linked lists in C, exploring their implementation, operations, and practical applications.
Understanding Linked Lists
🔗 A linked list is a linear data structure where elements are stored in nodes. Each node contains a data field and a pointer (or link) to the next node in the sequence.
Unlike arrays, linked lists don't require contiguous memory allocation, making them more flexible for dynamic data storage. They come in various forms:
- Singly Linked List: Each node points to the next node
- Doubly Linked List: Each node points to both the next and previous nodes
- Circular Linked List: The last node points back to the first node
For this tutorial, we'll focus on implementing a singly linked list.
Implementing a Singly Linked List in C
Let's start by defining the structure for our linked list node:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
This structure defines a node with an integer data field and a pointer to the next node.
Creating a New Node
Now, let's implement a function to create a new node:
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
This function allocates memory for a new node, initializes its data, and sets the next pointer to NULL.
Inserting a Node at the Beginning
Let's implement a function to insert a node at the beginning of the list:
struct Node* insertAtBeginning(struct Node* head, int data) {
struct Node* newNode = createNode(data);
newNode->next = head;
return newNode;
}
This function creates a new node, sets its next pointer to the current head, and returns the new node as the new head of the list.
Displaying the Linked List
To visualize our linked list, we'll implement a display function:
void displayList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
This function traverses the list, printing each node's data.
Putting It All Together
Let's create a main function to demonstrate these operations:
int main() {
struct Node* head = NULL;
// Insert some nodes
head = insertAtBeginning(head, 3);
head = insertAtBeginning(head, 2);
head = insertAtBeginning(head, 1);
printf("Linked List: ");
displayList(head);
return 0;
}
Output:
Linked List: 1 -> 2 -> 3 -> NULL
This program creates a linked list with three nodes and displays it.
Advanced Operations on Linked Lists
Now that we have a basic implementation, let's explore some more advanced operations.
Inserting a Node at the End
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
This function traverses to the end of the list and adds a new node there.
Deleting a Node
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head, *prev = NULL;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
This function removes the first occurrence of a node with the given key value.
Reversing a Linked List
struct Node* reverseList(struct Node* head) {
struct Node *prev = NULL, *current = head, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
This function reverses the order of nodes in the list.
Practical Example: Student Record System
Let's use our linked list implementation to create a simple student record system.
struct Student {
int id;
char name[50];
float gpa;
struct Student* next;
};
struct Student* createStudent(int id, const char* name, float gpa) {
struct Student* newStudent = (struct Student*)malloc(sizeof(struct Student));
if (newStudent == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newStudent->id = id;
strcpy(newStudent->name, name);
newStudent->gpa = gpa;
newStudent->next = NULL;
return newStudent;
}
void addStudent(struct Student** head, int id, const char* name, float gpa) {
struct Student* newStudent = createStudent(id, name, gpa);
newStudent->next = *head;
*head = newStudent;
}
void displayStudents(struct Student* head) {
struct Student* current = head;
printf("\nStudent Records:\n");
printf("ID\tName\tGPA\n");
printf("------------------------\n");
while (current != NULL) {
printf("%d\t%s\t%.2f\n", current->id, current->name, current->gpa);
current = current->next;
}
}
int main() {
struct Student* studentList = NULL;
addStudent(&studentList, 1, "Alice", 3.8);
addStudent(&studentList, 2, "Bob", 3.5);
addStudent(&studentList, 3, "Charlie", 3.9);
displayStudents(studentList);
return 0;
}
Output:
Student Records:
ID Name GPA
------------------------
3 Charlie 3.90
2 Bob 3.50
1 Alice 3.80
This example demonstrates how linked lists can be used to manage a collection of student records, allowing for easy addition and display of student information.
Performance Considerations
🚀 When working with linked lists, it's important to consider their performance characteristics:
- Insertion at the beginning: O(1)
- Insertion at the end: O(n)
- Deletion: O(n) in the worst case
- Search: O(n)
Linked lists excel at insertions and deletions, especially when working with the beginning of the list. However, they can be slower for random access compared to arrays.
Memory Management in Linked Lists
⚠️ When working with linked lists in C, proper memory management is crucial to prevent memory leaks. Always remember to free allocated memory when it's no longer needed:
void freeList(struct Node** head) {
struct Node* current = *head;
struct Node* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
*head = NULL;
}
This function should be called when you're done with the linked list to properly deallocate all memory.
Conclusion
Linked lists are versatile data structures that offer dynamic memory allocation and efficient insertions and deletions. In this article, we've explored the implementation of singly linked lists in C, covering basic and advanced operations, and demonstrating a practical application with a student record system.
By mastering linked lists, you'll have a powerful tool in your programming toolkit, enabling you to solve a wide range of problems efficiently. Remember to consider the performance implications and manage memory carefully when working with linked lists in your C programs.
As you continue to explore data structures, consider implementing doubly linked lists or circular linked lists to further enhance your understanding and skills in C programming.
