Linked Lists in C Language:
Linked Lists
A linked list is a linear data structure where each element is a separate object, called a node. Each node contains a data field and a reference (link) to the next node in the sequence. Linked lists are dynamic, allowing for efficient insertion and deletion of elements.
Node Structure
A typical node in a linked list can be defined using a structure in C:
<![CDATA[#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};]]>
Creating a Linked List
To create a linked list, we need to dynamically allocate memory for nodes and link them together:
<![CDATA[struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}]]>
Displaying a Linked List
To display the elements of a linked list, we can traverse the list from the head node and print each node's data:
<![CDATA[void display(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}]]>
Inserting into a Linked List
Inserting at the Beginning
To insert a node at the beginning of the linked list:
<![CDATA[void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}]]>
Inserting at the End
To insert a node at the end of the linked list:
<![CDATA[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;
}]]>
Searching in a Linked List
To search for a node with a specific value in the linked list:
<![CDATA[struct Node* search(struct Node* head, int key) {
struct Node* current = head;
while (current != NULL) {
if (current->data == key) {
return current;
}
current = current->next;
}
return NULL;
}]]>
Deleting from a Linked List
To delete a node with a specific value from the linked list:
<![CDATA[void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;
// If the head node itself holds the key to be deleted
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
// Search for the key to be deleted, keep track of the previous node
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL) return;
// Unlink the node from linked list
prev->next = temp->next;
free(temp);
}]]>
Complete Example
Here is a complete example demonstrating the creation, insertion, deletion, searching, and displaying of a linked list:
<![CDATA[#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void display(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
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;
}
struct Node* search(struct Node* head, int key) {
struct Node* current = head;
while (current != NULL) {
if (current->data == key) {
return current;
}
current = current->next;
}
return NULL;
}
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* 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);
}
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAtBeginning(&head, 0);
printf("Linked List: ");
display(head);
printf("Searching for 2: ");
struct Node* result = search(head, 2);
if (result != NULL) {
printf("Found %d\n", result->data);
} else {
printf("Not found\n");
}
printf("Deleting 2\n");
deleteNode(&head, 2);
printf("Linked List after deletion: ");
display(head);
return 0;
}]]>