In computer science, a linked list is a fundamental data structure used to store a sequence of elements. Unlike arrays, linked lists allow for efficient insertion and deletion of elements, as they dynamically allocate memory for each element. In this post, we'll guide you step-by-step through implementing a basic singly linked list in C.
By the end of this tutorial, you will understand:
- What a linked list is and how it works
- How to create nodes dynamically
- How to insert, delete, and display nodes in the list
1. Understanding the Linked List Structure
A singly linked list is made up of nodes where each node contains two components:
- Data: Stores the actual value of the node.
- Pointer: A reference (or pointer) to the next node in the sequence.
The last node in the list points to NULL, indicating the end of the list.
Example of a node structure:
struct Node {
int data;
struct Node* next;
};
Here:
int dataholds the value.struct Node* nextis a pointer to the next node.
2. Creating a Node
To create a node, you need to allocate memory dynamically using the malloc function and initialize it with data and a pointer to NULL.
Example:
#include <stdio.h>
#include <stdlib.h>
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));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1); // Exit if memory allocation fails
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}
In this function:
mallocallocates memory for a new node.- We assign the passed value to the node’s
datafield. - The
nextpointer is set toNULLsince it's not pointing to any other node yet.
3. Inserting Nodes into the Linked List
There are several ways to insert nodes into a linked list, but two common ones are:
- At the beginning: The new node becomes the head of the list.
- At the end: The new node is added after the last node.
a) Inserting at the Beginning
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = createNode(value);
newNode->next = *head;
*head = newNode;
}
Here:
- We create a new node and set its
nextpointer to the current head. - Then, we update the head pointer to point to the new node.
b) Inserting 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;
}
This function traverses the list until it finds the last node (whose next is NULL) and then updates its next pointer to point to the new node.
4. Displaying the Linked List
To display the elements of a linked list, you need to traverse it from the head node to the last node, printing each node's data.
Example:
void displayList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
In this function:
- We start from the head and move through the list using the
nextpointers. - When we reach a node whose
nextpointer isNULL, we print "NULL" to indicate the end of the list.
5. Deleting a Node
You may also need to remove nodes from the list. Let's discuss how to delete the first node (head) and how to delete a node with a specific value.
a) Deleting the First Node (Head)
void deleteFirstNode(struct Node** head) {
if (*head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
This function:
- Checks if the list is empty.
- Updates the head to point to the second node.
- Frees the memory of the old head node.
b) Deleting a Node by Value
void deleteNode(struct Node** head, int value) {
struct Node* temp = *head;
struct Node* prev = NULL;
// If the head node holds the value to be deleted
if (temp != NULL && temp->data == value) {
*head = temp->next;
free(temp);
return;
}
// Search for the node holding the value to delete
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}
// If the value was not found
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
This function:
- Handles the case where the node to delete is the head.
- Traverses the list to find the node with the specified value.
- Adjusts the pointers and frees the node once found.
6. Complete Example
Let's combine all the concepts and write a full program to create a linked list, insert nodes, display the list, and delete nodes.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
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;
}
void displayList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void deleteFirstNode(struct Node** head) {
if (*head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf("Initial list: ");
displayList(head);
deleteFirstNode(&head);
printf("After deleting first node: ");
displayList(head);
return 0;
}
Conclusion
By following this tutorial, you have learned how to implement a basic singly linked list in C, including adding nodes, displaying the list, and deleting nodes. Linked lists are a versatile data structure that forms the foundation for more complex structures like stacks, queues, and graphs. Understanding how they work and how to implement them will be invaluable as you progress in computer engineering.