A linked list is a data structure consisting of nodes where each node contains two parts:
- Data: Stores the value.
- Pointer: A reference to the next node in the sequence (or previous, in the case of doubly linked lists).
Representation of Linked Lists
- Singly Linked List (SLL):
- Each node has a pointer to the next node.
- The last node points to NULL.
struct Node {
int data;
struct Node* next;
};
- Doubly Linked List (DLL):
- Each node has two pointers:
- One pointing to the next node.
- One pointing to the previous node.
- Each node has two pointers:
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
- Circular Linked List:
- The last node’s pointer points back to the first node, forming a circular structure.
- Can be singly or doubly circular.
struct Node {
int data;
struct Node* next;
};
Operations on Linked Lists
1. Traversal
Visiting each node in the list to display or process its value.
void traverse(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}
2. Insertion
Adding a new node at the beginning, end, or a specific position.
a. Insert at the Beginning
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
b. Insert at the End
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
c. Insert at a Specific Position
void insertAtPosition(struct Node** head, int value, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if (position == 1) {
newNode->next = *head;
*head = newNode;
return;
}
struct Node* temp = *head;
for (int i = 1; i < position – 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf(“Position out of range.\n”);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
3. Deletion
Removing a node from the beginning, end, or a specific position.
a. Delete from the Beginning
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
b. Delete from the End
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
if (temp->next == NULL) { // Single node case
*head = NULL;
free(temp);
return;
}
while (temp->next->next != NULL) {
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}
c. Delete a Specific Node
void deleteByValue(struct Node** head, int value) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
// If head node itself holds the value
if (temp != NULL && temp->data == value) {
*head = temp->next;
free(temp);
return;
}
// Search for the value to be deleted
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}
// If value was not found
if (temp == NULL) {
printf(“Value not found in the list.\n”);
return;
}
prev->next = temp->next;
free(temp);
}
4. Searching
Finding a specific value in the linked list.
void search(struct Node* head, int value) {
struct Node* temp = head;
int position = 1;
while (temp != NULL) {
if (temp->data == value) {
printf(“Value %d found at position %d.\n”, value, position);
return;
}
temp = temp->next;
position++;
}
printf(“Value %d not found.\n”, value);
}
5. Reversal
Reversing the order of nodes in the linked list.
void reverse(struct Node** head) {
struct Node* prev = NULL;
struct Node* current = *head;
struct Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
}
Example Program
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Function prototypes
void insertAtEnd(struct Node** head, int value);
void deleteFromBeginning(struct Node** head);
void traverse(struct Node* head);
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf(“Linked List after insertion:\n”);
traverse(head);
deleteFromBeginning(&head);
printf(“Linked List after deletion:\n”);
traverse(head);
return 0;
}
// Function implementations
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
void traverse(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}
Output
Linked List after insertion:
10 -> 20 -> 30 -> NULL
Linked List after deletion:
20 -> 30 -> NULL
Summary
- Representation involves defining nodes and their connections.
- Operations include insertion, deletion, traversal, searching, and reversal.
- Linked lists provide dynamic memory management and are fundamental in various applications like stacks, queues, and graph representations.