Linked list is a linear data structure where each node is connected with each other with the help of pointers of node type.
There are basic terminologies that you need to revise before further moving to the implementation of linked list in c using arrays in the blog.
- Node : Node is an important part of the linked list. It is a structure that contains two forms i.e, data and next pointer. Data part in a node contains value and the next part contains the address of the next node.
- Next Pointer : Next pointer in a linked list data structure points the next node in the arrangement. The next pointer of the last node in the linked list points to NULL to avoid undefined behaviour.
- Head : Head is also a pointer in a linked list but it points to the first node of the entire list.
We are doing implementation of linked list in c using array data structure
Defining a node in a linked list using structure
typedef struct {
int data;
int Linked_next;
} LinkedList_Node; // This a node in linked list
This code defines a node using structure where we have created a variable data of int type and next_pointer that points to the next node in a linked list.
Function to initialize linked list
// Here is a function to initialize linked list using array
void initialize_linkedlist() {
for (int i = 0; i < List_size - 1; i++) {
linkedList_Array[i].Linked_next = i + 1; // Link to the next free node
}
linkedList_Array[SIZE - 1].Linked_next = -1; // End of the free list
Linked_head = -1;
temp = 0;
printf("Linked list initialized.\n");
}
This code initializes an array-based linked list by creating a “free list” of nodes. Each element in the array, representing a node, has a Linked_next field that stores the index of the next node in the free list.
The loop links all nodes sequentially, except for the last node, which is marked with -1 to indicate the end of the free list.
The Linked_head variable is set to -1, showing that the actual linked list is initially empty, while a temp variable is initialized to 0. This setup prepares the array for efficient allocation of nodes when the linked list is constructed, ensuring that all nodes are readily available for use.
Finally, a confirmation message is printed to indicate the successful initialization of the linked list.
Function to insert new node in the linked list
// Defining function here in the linked list to insert newnode
void insertNode_linkedlist(int data) {
if (temp == -1) {
printf("List is full.\n");
return;
}
int newNode1 = temp; // Get the next free index
temp = linkedList_Array[temp].Linked_next; // Update the free index
linkedList_Array[newNode1].data = data;
linkedList_Array[newNode1].Linked_next = Linked_head;
Linked_head = newNode1;
printf("Inserted %d into the list.\n", data);
The insertNode_linkedlist function adds a new node to an array-based linked list by utilizing the free list structure. It first checks if the list is full by verifying if temp (the index of the next free node) is -1.
If not, it assigns temp to a new node (newNode1), updates temp to the next free node, and stores the given data in the new node’s data field.
The new node’s Linked_next is set to the current head (Linked_head), and Linked_head is updated to point to the new node, making it the list’s new head. If the insertion is successful, it prints a confirmation message; otherwise, it informs the user that the list is full.
Function to delete a node in a linked list
// We are defining here function to delete a node in a linked list
void deleteNode_linkedlist(int value) {
int current_node = Linked_head, prev_node = -1;
while (current != -1 && linkedList_Array[current_node].data != value) {
prev_node = current_node;
current_node = linkedList_Array[current_node].Linked_next;
}
if (current_node == -1) {
printf("Value %d not found in the list.\n", value);
return;
}
if (prev_node == -1) {
Linked_head = linkedList_Array[current_node].Linked_next; // Delete the head node
} else {
linkedList_Array[prev_node].Linked_next = linkedList_Array[current_node].Linked_next;
}
linkedList_Array[current_node].Linked_next = temp; // Add the node back to the free list
temp = current_node;
printf("Deleted %d from the list.\n", value);
}
The deleteNode_linkedlist function removes a node containing a specific value from an array-based linked list. It starts by traversing the list, using current_node to track the current node and prev_node for the previous node, searching for the node with the specified value.
If the value is not found (current_node==-1), it prints a message and exits.
If found, it updates Linked_head to skip the deleted node if it’s the head, or adjusts the Linked_next pointer of the previous node to bypass the deleted node for other cases.
Finally, it adds the deleted node back to the free list by updating its Linked_next to temp (the index of the next free node) and updating temp to the current node, ensuring the node can be reused. A confirmation message is printed upon successful deletion.
Function for displaying elements of linked list
// Defining function here for displaying elements of the entire linked list
void display_linkedlist() {
int current_node = Linked_head;
if (current_node == -1) {
printf("List is empty.\n");
return;
}
printf("Linked List: ");
while (current_node != -1) {
printf("%d -> ", linkedList_Array[current_node].data);
current_node = linkedList_Array[current_node].Linked_next;
}
printf("NULL\n");
}
The display_linkedlist function prints all elements of an array-based linked list. Starting from the head node (Linked_head), it traverses the list using the Linked_next pointers.
If the list is empty (Linked_head==-1), it prints “List is empty” and exits. Otherwise, it iterates through each node, printing its data followed by an arrow (->) to indicate the link to the next node.
When the traversal reaches the end of the list (current_node==-1), it prints NULL to signify the termination of the linked list. This function provides a clear visualization of the linked list’s structure.
Function for searching a node in a linked list
//we are defining function here to search for a particular node in the linked list
void searchNode_linkedlist(int value) {
int current_node = Linked_head;
while (current_node != -1) {
if (linkedList_Array[current_node].data == value) {
printf("Value %d found in the list.\n", value);
return;
}
current_node = linkedList_Array[current_node].Linked_next;
}
printf("Value %d not found in the list.\n", value);
}
The searchNode_linkedlist function searches for a specific value in an array-based linked list. It starts at the head of the list (Linked_head) and iterates through each node using the Linked_next pointers.
For each node, it checks if the data field matches the target value. If a match is found, it prints a message confirming the value is in the list and exits the function.
If the end of the list is reached (current_node==-1)without finding the value, it prints a message indicating the value is not present. This function efficiently traverses the list to locate the desired value.
Main Program
Below is the combined program to define the entire operation to be performed in the linked list data structure for the implementation of linked list in c
#include <stdio.h>
#define List_size 200
// here we are defining node in a linked list
typedef struct {
int data;
int Linked_next;
} linkedList_Node;
linkedList_Node linkedList_Array[List_size];
int Linked_head = -1; // Head of the linked list
int temp = 0; // Tracks the next free index in the array
// Here is a function to initialize linked list using array
void initialize_linkedlist() {
for (int i = 0; i < List_size - 1; i++) {
linkedList_Array[i].Linked_next = i + 1; // Link to the next free node
}
linkedList_Array[List_size - 1].Linked_next = -1; // End of the free list
Linked_head = -1;
temp = 0;
printf("Linked list initialized.\n");
}
// Defining function here in the linked list to insert newnode
void insertNode_linkedlist(int data) {
if (temp == -1) {
printf("List is full.\n");
return;
}
int newNode1 = temp; // Get the next free index
temp = linkedList_Array[temp].Linked_next; // Update the free index
linkedList_Array[newNode1].data = data;
linkedList_Array[newNode1].Linked_next = Linked_head;
Linked_head = newNode1;
printf("Inserted %d into the list.\n", data);
}
// We are defining here function to delete a node in a linked list
void deleteNode_linkedlist(int value) {
int current_node = Linked_head, prev_node = -1;
while (current_node != -1 && linkedList_Array[current_node].data != value) {
prev_node = current_node;
current_node = linkedList_Array[current_node].Linked_next;
}
if (current_node == -1) {
printf("Value %d not found in the list.\n", value);
return;
}
if (prev_node == -1) {
Linked_head = linkedList_Array[current_node].Linked_next; // Delete the head node
} else {
linkedList_Array[prev_node].Linked_next = linkedList_Array[current_node].Linked_next;
}
linkedList_Array[current_node].Linked_next = temp; // Add the node back to the free list
temp = current_node;
printf("Deleted %d from the list.\n", value);
}
// Defining function here for displaying elements of the entire linked list
void display_linkedlist() {
int current_node = Linked_head;
if (current_node == -1) {
printf("List is empty.\n");
return;
}
printf("Linked List: ");
while (current_node != -1) {
printf("%d -> ", linkedList_Array[current_node].data);
current_node = linkedList_Array[current_node].Linked_next;
}
printf("NULL\n");
}
//we are defining function here to search for a particular node in the linked list
void searchNode_linkedlist(int value) {
int current_node = Linked_head;
while (current_node != -1) {
if (linkedList_Array[current_node].data == value) {
printf("Value %d found in the list.\n", value);
return;
}
current_node = linkedList_Array[current_node].Linked_next;
}
printf("Value %d not found in the list.\n", value);
}
// Here is the main function that take input from the end user to check the flow of operations performed in the linked list
int main() {
int choose_option, value;
initialize_linkedlist();
while (1) {
printf("\nChoose option from here\n");
printf("1. Insert Node in a linked list \n");
printf("2. Delete Node in a linked list\n");
printf("3. Display elements from the linked list\n");
printf("4. Search a particular node in a linked list\n");
printf("5. Exit the execution of the program\n");
printf("Enter the option that you have selected: ");
scanf("%d", &choose_option);
switch (choose_option) {
case 1:
printf("Enter the respective value that you want to enter : ");
scanf("%d", &value);
insertNode_linkedlist(value);
break;
case 2:
printf("Enter the value that you want to delete from the linked list: ");
scanf("%d", &value);
deleteNode_linkedlist(value);
break;
case 3:
display_linkedlist();
break;
case 4:
printf("Enter the data that you want to search from the linked list ");
scanf("%d", &value);
searchNode_linkedlist(value);
break;
case 5:
printf("Exiting from the executing program.\n");
return 0;
default:
printf("No option as such available .\n");
}
}
}
