c
examples
examples.c🔧c
/**
* Linked Lists in C - Comprehensive Examples
*
* This file demonstrates various types of linked lists and operations.
*
* Compilation:
* gcc -Wall -o examples examples.c
* gcc -std=c99 -Wall -o examples examples.c
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* ============================================================
* BASIC NODE STRUCTURES
* ============================================================ */
/* Singly Linked List Node */
typedef struct SLLNode {
int data;
struct SLLNode *next;
} SLLNode;
/* Singly Linked List */
typedef struct {
SLLNode *head;
SLLNode *tail;
size_t size;
} SinglyLinkedList;
/* Doubly Linked List Node */
typedef struct DLLNode {
int data;
struct DLLNode *prev;
struct DLLNode *next;
} DLLNode;
/* Doubly Linked List */
typedef struct {
DLLNode *head;
DLLNode *tail;
size_t size;
} DoublyLinkedList;
/* Circular Singly Linked List */
typedef struct CSLLNode {
int data;
struct CSLLNode *next;
} CSLLNode;
typedef struct {
CSLLNode *tail;
size_t size;
} CircularSLL;
/* ============================================================
* EXAMPLE 1: Singly Linked List - Basic Operations
* ============================================================ */
/* Create empty singly linked list */
SinglyLinkedList *sll_create(void) {
SinglyLinkedList *list = malloc(sizeof(SinglyLinkedList));
if (list == NULL) return NULL;
list->head = NULL;
list->tail = NULL;
list->size = 0;
return list;
}
/* Create a new node */
SLLNode *sll_create_node(int data) {
SLLNode *node = malloc(sizeof(SLLNode));
if (node == NULL) return NULL;
node->data = data;
node->next = NULL;
return node;
}
/* Insert at beginning */
int sll_prepend(SinglyLinkedList *list, int data) {
SLLNode *node = sll_create_node(data);
if (node == NULL) return -1;
node->next = list->head;
list->head = node;
if (list->tail == NULL) {
list->tail = node;
}
list->size++;
return 0;
}
/* Insert at end */
int sll_append(SinglyLinkedList *list, int data) {
SLLNode *node = sll_create_node(data);
if (node == NULL) return -1;
if (list->tail == NULL) {
list->head = node;
list->tail = node;
} else {
list->tail->next = node;
list->tail = node;
}
list->size++;
return 0;
}
/* Delete first node */
int sll_delete_first(SinglyLinkedList *list) {
if (list->head == NULL) return -1;
SLLNode *temp = list->head;
list->head = list->head->next;
if (list->head == NULL) {
list->tail = NULL;
}
free(temp);
list->size--;
return 0;
}
/* Print list */
void sll_print(SinglyLinkedList *list) {
printf("[");
SLLNode *current = list->head;
while (current != NULL) {
printf("%d", current->data);
if (current->next != NULL) {
printf(" -> ");
}
current = current->next;
}
printf("] (size: %zu)\n", list->size);
}
/* Free list */
void sll_free(SinglyLinkedList *list) {
if (list == NULL) return;
SLLNode *current = list->head;
while (current != NULL) {
SLLNode *next = current->next;
free(current);
current = next;
}
free(list);
}
void example1_basic_singly_linked_list(void) {
printf("=== Example 1: Basic Singly Linked List ===\n\n");
SinglyLinkedList *list = sll_create();
printf("Appending 10, 20, 30:\n");
sll_append(list, 10);
sll_append(list, 20);
sll_append(list, 30);
sll_print(list);
printf("\nPrepending 5:\n");
sll_prepend(list, 5);
sll_print(list);
printf("\nDeleting first element:\n");
sll_delete_first(list);
sll_print(list);
sll_free(list);
printf("\n");
}
/* ============================================================
* EXAMPLE 2: Singly Linked List - Search and Delete by Value
* ============================================================ */
/* Search for value */
SLLNode *sll_search(SinglyLinkedList *list, int value) {
SLLNode *current = list->head;
while (current != NULL) {
if (current->data == value) {
return current;
}
current = current->next;
}
return NULL;
}
/* Delete by value */
int sll_delete_value(SinglyLinkedList *list, int value) {
if (list->head == NULL) return -1;
/* Check head */
if (list->head->data == value) {
return sll_delete_first(list);
}
/* Find node before target */
SLLNode *prev = list->head;
while (prev->next != NULL && prev->next->data != value) {
prev = prev->next;
}
if (prev->next == NULL) return -1; /* Not found */
SLLNode *temp = prev->next;
prev->next = temp->next;
if (temp == list->tail) {
list->tail = prev;
}
free(temp);
list->size--;
return 0;
}
void example2_search_and_delete(void) {
printf("=== Example 2: Search and Delete by Value ===\n\n");
SinglyLinkedList *list = sll_create();
for (int i = 1; i <= 5; i++) {
sll_append(list, i * 10);
}
printf("Initial list: ");
sll_print(list);
int search_val = 30;
SLLNode *found = sll_search(list, search_val);
printf("Search for %d: %s\n", search_val, found ? "Found" : "Not found");
search_val = 35;
found = sll_search(list, search_val);
printf("Search for %d: %s\n", search_val, found ? "Found" : "Not found");
printf("\nDeleting 30:\n");
sll_delete_value(list, 30);
sll_print(list);
printf("\nDeleting 10 (head):\n");
sll_delete_value(list, 10);
sll_print(list);
printf("\nDeleting 50 (tail):\n");
sll_delete_value(list, 50);
sll_print(list);
sll_free(list);
printf("\n");
}
/* ============================================================
* EXAMPLE 3: Insert at Position
* ============================================================ */
/* Get node at index */
SLLNode *sll_get(SinglyLinkedList *list, size_t index) {
if (index >= list->size) return NULL;
SLLNode *current = list->head;
for (size_t i = 0; i < index; i++) {
current = current->next;
}
return current;
}
/* Insert after node */
int sll_insert_after(SinglyLinkedList *list, SLLNode *prev, int data) {
if (prev == NULL) return -1;
SLLNode *node = sll_create_node(data);
if (node == NULL) return -1;
node->next = prev->next;
prev->next = node;
if (prev == list->tail) {
list->tail = node;
}
list->size++;
return 0;
}
/* Insert at position */
int sll_insert_at(SinglyLinkedList *list, size_t position, int data) {
if (position > list->size) return -1;
if (position == 0) {
return sll_prepend(list, data);
}
if (position == list->size) {
return sll_append(list, data);
}
SLLNode *prev = sll_get(list, position - 1);
return sll_insert_after(list, prev, data);
}
void example3_insert_at_position(void) {
printf("=== Example 3: Insert at Position ===\n\n");
SinglyLinkedList *list = sll_create();
sll_append(list, 10);
sll_append(list, 30);
sll_append(list, 50);
printf("Initial list: ");
sll_print(list);
printf("\nInsert 20 at position 1:\n");
sll_insert_at(list, 1, 20);
sll_print(list);
printf("\nInsert 40 at position 3:\n");
sll_insert_at(list, 3, 40);
sll_print(list);
printf("\nInsert 5 at position 0:\n");
sll_insert_at(list, 0, 5);
sll_print(list);
printf("\nInsert 60 at end (position %zu):\n", list->size);
sll_insert_at(list, list->size, 60);
sll_print(list);
sll_free(list);
printf("\n");
}
/* ============================================================
* EXAMPLE 4: Reverse a Linked List
* ============================================================ */
/* Iterative reverse */
void sll_reverse(SinglyLinkedList *list) {
if (list->head == NULL || list->head->next == NULL) {
return;
}
SLLNode *prev = NULL;
SLLNode *current = list->head;
list->tail = list->head;
while (current != NULL) {
SLLNode *next = current->next;
current->next = prev;
prev = current;
current = next;
}
list->head = prev;
}
/* Recursive reverse helper */
SLLNode *reverse_recursive_helper(SLLNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
SLLNode *rest = reverse_recursive_helper(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}
/* Recursive reverse */
void sll_reverse_recursive(SinglyLinkedList *list) {
if (list->head == NULL) return;
SLLNode *old_head = list->head;
list->head = reverse_recursive_helper(list->head);
list->tail = old_head;
}
void example4_reverse_list(void) {
printf("=== Example 4: Reverse a Linked List ===\n\n");
SinglyLinkedList *list = sll_create();
for (int i = 1; i <= 5; i++) {
sll_append(list, i);
}
printf("Original list: ");
sll_print(list);
printf("\nAfter iterative reverse: ");
sll_reverse(list);
sll_print(list);
printf("\nAfter recursive reverse: ");
sll_reverse_recursive(list);
sll_print(list);
sll_free(list);
printf("\n");
}
/* ============================================================
* EXAMPLE 5: Find Middle Element (Floyd's Algorithm)
* ============================================================ */
SLLNode *sll_find_middle(SinglyLinkedList *list) {
if (list->head == NULL) return NULL;
SLLNode *slow = list->head;
SLLNode *fast = list->head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
void example5_find_middle(void) {
printf("=== Example 5: Find Middle Element ===\n\n");
SinglyLinkedList *list = sll_create();
/* Odd number of elements */
for (int i = 1; i <= 5; i++) {
sll_append(list, i * 10);
}
printf("List (odd): ");
sll_print(list);
SLLNode *middle = sll_find_middle(list);
printf("Middle element: %d\n\n", middle->data);
sll_free(list);
/* Even number of elements */
list = sll_create();
for (int i = 1; i <= 6; i++) {
sll_append(list, i * 10);
}
printf("List (even): ");
sll_print(list);
middle = sll_find_middle(list);
printf("Middle element: %d (second middle for even length)\n", middle->data);
sll_free(list);
printf("\n");
}
/* ============================================================
* EXAMPLE 6: Detect Cycle in Linked List
* ============================================================ */
int has_cycle(SLLNode *head) {
if (head == NULL) return 0;
SLLNode *slow = head;
SLLNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return 1;
}
}
return 0;
}
SLLNode *find_cycle_start(SLLNode *head) {
if (head == NULL) return NULL;
SLLNode *slow = head;
SLLNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}
void example6_detect_cycle(void) {
printf("=== Example 6: Detect Cycle in Linked List ===\n\n");
/* Create nodes manually for cycle testing */
SLLNode *n1 = sll_create_node(1);
SLLNode *n2 = sll_create_node(2);
SLLNode *n3 = sll_create_node(3);
SLLNode *n4 = sll_create_node(4);
SLLNode *n5 = sll_create_node(5);
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
printf("List without cycle: 1 -> 2 -> 3 -> 4 -> 5 -> NULL\n");
printf("Has cycle: %s\n\n", has_cycle(n1) ? "Yes" : "No");
/* Create cycle: 5 -> 3 */
n5->next = n3;
printf("List with cycle: 1 -> 2 -> 3 -> 4 -> 5 -> (back to 3)\n");
printf("Has cycle: %s\n", has_cycle(n1) ? "Yes" : "No");
SLLNode *cycle_start = find_cycle_start(n1);
printf("Cycle starts at node with value: %d\n", cycle_start->data);
/* Break cycle and free */
n5->next = NULL;
free(n1); free(n2); free(n3); free(n4); free(n5);
printf("\n");
}
/* ============================================================
* EXAMPLE 7: Merge Two Sorted Lists
* ============================================================ */
SLLNode *merge_sorted(SLLNode *l1, SLLNode *l2) {
SLLNode dummy;
SLLNode *tail = &dummy;
dummy.next = NULL;
while (l1 != NULL && l2 != NULL) {
if (l1->data <= l2->data) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = (l1 != NULL) ? l1 : l2;
return dummy.next;
}
void example7_merge_sorted_lists(void) {
printf("=== Example 7: Merge Two Sorted Lists ===\n\n");
SinglyLinkedList *list1 = sll_create();
sll_append(list1, 1);
sll_append(list1, 3);
sll_append(list1, 5);
sll_append(list1, 7);
SinglyLinkedList *list2 = sll_create();
sll_append(list2, 2);
sll_append(list2, 4);
sll_append(list2, 6);
sll_append(list2, 8);
printf("List 1: ");
sll_print(list1);
printf("List 2: ");
sll_print(list2);
SLLNode *merged = merge_sorted(list1->head, list2->head);
printf("\nMerged: [");
SLLNode *current = merged;
while (current != NULL) {
printf("%d", current->data);
if (current->next) printf(" -> ");
current = current->next;
}
printf("]\n");
/* Free merged list */
current = merged;
while (current != NULL) {
SLLNode *next = current->next;
free(current);
current = next;
}
/* Free list structs (nodes already freed) */
list1->head = NULL;
list2->head = NULL;
free(list1);
free(list2);
printf("\n");
}
/* ============================================================
* EXAMPLE 8: Doubly Linked List
* ============================================================ */
DoublyLinkedList *dll_create(void) {
DoublyLinkedList *list = malloc(sizeof(DoublyLinkedList));
if (list == NULL) return NULL;
list->head = NULL;
list->tail = NULL;
list->size = 0;
return list;
}
DLLNode *dll_create_node(int data) {
DLLNode *node = malloc(sizeof(DLLNode));
if (node == NULL) return NULL;
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}
int dll_prepend(DoublyLinkedList *list, int data) {
DLLNode *node = dll_create_node(data);
if (node == NULL) return -1;
if (list->head == NULL) {
list->head = node;
list->tail = node;
} else {
node->next = list->head;
list->head->prev = node;
list->head = node;
}
list->size++;
return 0;
}
int dll_append(DoublyLinkedList *list, int data) {
DLLNode *node = dll_create_node(data);
if (node == NULL) return -1;
if (list->tail == NULL) {
list->head = node;
list->tail = node;
} else {
node->prev = list->tail;
list->tail->next = node;
list->tail = node;
}
list->size++;
return 0;
}
int dll_delete_node(DoublyLinkedList *list, DLLNode *node) {
if (node == NULL) return -1;
if (node->prev != NULL) {
node->prev->next = node->next;
} else {
list->head = node->next;
}
if (node->next != NULL) {
node->next->prev = node->prev;
} else {
list->tail = node->prev;
}
free(node);
list->size--;
return 0;
}
void dll_print_forward(DoublyLinkedList *list) {
printf("Forward: [");
DLLNode *current = list->head;
while (current != NULL) {
printf("%d", current->data);
if (current->next) printf(" <-> ");
current = current->next;
}
printf("]\n");
}
void dll_print_backward(DoublyLinkedList *list) {
printf("Backward: [");
DLLNode *current = list->tail;
while (current != NULL) {
printf("%d", current->data);
if (current->prev) printf(" <-> ");
current = current->prev;
}
printf("]\n");
}
void dll_free(DoublyLinkedList *list) {
if (list == NULL) return;
DLLNode *current = list->head;
while (current != NULL) {
DLLNode *next = current->next;
free(current);
current = next;
}
free(list);
}
void example8_doubly_linked_list(void) {
printf("=== Example 8: Doubly Linked List ===\n\n");
DoublyLinkedList *list = dll_create();
for (int i = 1; i <= 5; i++) {
dll_append(list, i * 10);
}
printf("After appending 10, 20, 30, 40, 50:\n");
dll_print_forward(list);
dll_print_backward(list);
printf("\nPrepending 5:\n");
dll_prepend(list, 5);
dll_print_forward(list);
printf("\nDeleting node with value 30 (middle):\n");
DLLNode *current = list->head;
while (current && current->data != 30) {
current = current->next;
}
if (current) dll_delete_node(list, current);
dll_print_forward(list);
printf("\nDeleting head (5):\n");
dll_delete_node(list, list->head);
dll_print_forward(list);
printf("\nDeleting tail (50):\n");
dll_delete_node(list, list->tail);
dll_print_forward(list);
dll_free(list);
printf("\n");
}
/* ============================================================
* EXAMPLE 9: Circular Singly Linked List
* ============================================================ */
CircularSLL *csll_create(void) {
CircularSLL *list = malloc(sizeof(CircularSLL));
if (list == NULL) return NULL;
list->tail = NULL;
list->size = 0;
return list;
}
int csll_prepend(CircularSLL *list, int data) {
CSLLNode *node = malloc(sizeof(CSLLNode));
if (node == NULL) return -1;
node->data = data;
if (list->tail == NULL) {
node->next = node;
list->tail = node;
} else {
node->next = list->tail->next;
list->tail->next = node;
}
list->size++;
return 0;
}
int csll_append(CircularSLL *list, int data) {
int result = csll_prepend(list, data);
if (result == 0) {
list->tail = list->tail->next;
}
return result;
}
void csll_print(CircularSLL *list) {
if (list->tail == NULL) {
printf("(empty)\n");
return;
}
printf("[");
CSLLNode *head = list->tail->next;
CSLLNode *current = head;
do {
printf("%d", current->data);
current = current->next;
if (current != head) printf(" -> ");
} while (current != head);
printf(" -> (back to %d)]\n", head->data);
}
void csll_free(CircularSLL *list) {
if (list == NULL) return;
if (list->tail != NULL) {
CSLLNode *head = list->tail->next;
CSLLNode *current = head;
do {
CSLLNode *next = current->next;
free(current);
current = next;
} while (current != head);
}
free(list);
}
void example9_circular_linked_list(void) {
printf("=== Example 9: Circular Singly Linked List ===\n\n");
CircularSLL *list = csll_create();
printf("Appending 10, 20, 30:\n");
csll_append(list, 10);
csll_append(list, 20);
csll_append(list, 30);
csll_print(list);
printf("\nPrepending 5:\n");
csll_prepend(list, 5);
csll_print(list);
/* Traverse multiple rounds */
printf("\nTraversing 2 complete rounds:\n");
if (list->tail) {
CSLLNode *head = list->tail->next;
CSLLNode *current = head;
int count = 0;
printf(" ");
while (count < list->size * 2) {
printf("%d ", current->data);
current = current->next;
count++;
}
printf("\n");
}
csll_free(list);
printf("\n");
}
/* ============================================================
* EXAMPLE 10: Nth Node from End
* ============================================================ */
SLLNode *sll_nth_from_end(SinglyLinkedList *list, size_t n) {
if (list->head == NULL || n == 0) return NULL;
SLLNode *fast = list->head;
SLLNode *slow = list->head;
/* Move fast n nodes ahead */
for (size_t i = 0; i < n; i++) {
if (fast == NULL) return NULL;
fast = fast->next;
}
/* Move both until fast reaches end */
while (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
void example10_nth_from_end(void) {
printf("=== Example 10: Nth Node from End ===\n\n");
SinglyLinkedList *list = sll_create();
for (int i = 1; i <= 7; i++) {
sll_append(list, i * 10);
}
printf("List: ");
sll_print(list);
for (size_t n = 1; n <= 7; n++) {
SLLNode *node = sll_nth_from_end(list, n);
if (node) {
printf("%zu from end: %d\n", n, node->data);
}
}
sll_free(list);
printf("\n");
}
/* ============================================================
* EXAMPLE 11: Remove Duplicates
* ============================================================ */
void sll_remove_duplicates_sorted(SinglyLinkedList *list) {
SLLNode *current = list->head;
while (current != NULL && current->next != NULL) {
if (current->data == current->next->data) {
SLLNode *duplicate = current->next;
current->next = current->next->next;
if (duplicate == list->tail) {
list->tail = current;
}
free(duplicate);
list->size--;
} else {
current = current->next;
}
}
}
void sll_remove_duplicates_unsorted(SinglyLinkedList *list) {
SLLNode *current = list->head;
while (current != NULL) {
SLLNode *runner = current;
while (runner->next != NULL) {
if (runner->next->data == current->data) {
SLLNode *duplicate = runner->next;
runner->next = runner->next->next;
if (duplicate == list->tail) {
list->tail = runner;
}
free(duplicate);
list->size--;
} else {
runner = runner->next;
}
}
current = current->next;
}
}
void example11_remove_duplicates(void) {
printf("=== Example 11: Remove Duplicates ===\n\n");
/* Sorted list */
SinglyLinkedList *sorted = sll_create();
int sorted_data[] = {1, 1, 2, 3, 3, 3, 4, 5, 5};
for (int i = 0; i < 9; i++) {
sll_append(sorted, sorted_data[i]);
}
printf("Sorted list with duplicates: ");
sll_print(sorted);
sll_remove_duplicates_sorted(sorted);
printf("After removing duplicates: ");
sll_print(sorted);
sll_free(sorted);
/* Unsorted list */
SinglyLinkedList *unsorted = sll_create();
int unsorted_data[] = {3, 1, 2, 1, 3, 4, 2, 5, 1};
for (int i = 0; i < 9; i++) {
sll_append(unsorted, unsorted_data[i]);
}
printf("\nUnsorted list with duplicates: ");
sll_print(unsorted);
sll_remove_duplicates_unsorted(unsorted);
printf("After removing duplicates: ");
sll_print(unsorted);
sll_free(unsorted);
printf("\n");
}
/* ============================================================
* EXAMPLE 12: Check if Palindrome
* ============================================================ */
int sll_is_palindrome(SinglyLinkedList *list) {
if (list->head == NULL || list->head->next == NULL) {
return 1;
}
/* Find middle */
SLLNode *slow = list->head;
SLLNode *fast = list->head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
/* Reverse second half */
SLLNode *prev = NULL;
SLLNode *current = slow;
while (current != NULL) {
SLLNode *next = current->next;
current->next = prev;
prev = current;
current = next;
}
/* Compare halves */
SLLNode *p1 = list->head;
SLLNode *p2 = prev;
int is_palindrome = 1;
while (p2 != NULL) {
if (p1->data != p2->data) {
is_palindrome = 0;
break;
}
p1 = p1->next;
p2 = p2->next;
}
/* Restore list */
current = prev;
prev = NULL;
while (current != NULL) {
SLLNode *next = current->next;
current->next = prev;
prev = current;
current = next;
}
return is_palindrome;
}
void example12_palindrome_check(void) {
printf("=== Example 12: Check if Palindrome ===\n\n");
/* Palindrome list */
SinglyLinkedList *pal = sll_create();
int pal_data[] = {1, 2, 3, 2, 1};
for (int i = 0; i < 5; i++) {
sll_append(pal, pal_data[i]);
}
printf("List: ");
sll_print(pal);
printf("Is palindrome: %s\n\n", sll_is_palindrome(pal) ? "Yes" : "No");
sll_free(pal);
/* Non-palindrome list */
SinglyLinkedList *non_pal = sll_create();
int non_pal_data[] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
sll_append(non_pal, non_pal_data[i]);
}
printf("List: ");
sll_print(non_pal);
printf("Is palindrome: %s\n\n", sll_is_palindrome(non_pal) ? "Yes" : "No");
sll_free(non_pal);
/* Even length palindrome */
SinglyLinkedList *even_pal = sll_create();
int even_data[] = {1, 2, 2, 1};
for (int i = 0; i < 4; i++) {
sll_append(even_pal, even_data[i]);
}
printf("List: ");
sll_print(even_pal);
printf("Is palindrome: %s\n", sll_is_palindrome(even_pal) ? "Yes" : "No");
sll_free(even_pal);
printf("\n");
}
/* ============================================================
* EXAMPLE 13: Merge Sort for Linked List
* ============================================================ */
void split_list(SLLNode *source, SLLNode **front, SLLNode **back) {
SLLNode *fast = source->next;
SLLNode *slow = source;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*front = source;
*back = slow->next;
slow->next = NULL;
}
SLLNode *merge_sort(SLLNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
SLLNode *a;
SLLNode *b;
split_list(head, &a, &b);
a = merge_sort(a);
b = merge_sort(b);
return merge_sorted(a, b);
}
void example13_merge_sort(void) {
printf("=== Example 13: Merge Sort for Linked List ===\n\n");
SinglyLinkedList *list = sll_create();
int data[] = {64, 34, 25, 12, 22, 11, 90, 45};
int n = sizeof(data) / sizeof(data[0]);
for (int i = 0; i < n; i++) {
sll_append(list, data[i]);
}
printf("Unsorted list: ");
sll_print(list);
list->head = merge_sort(list->head);
/* Update tail */
SLLNode *current = list->head;
while (current && current->next) {
current = current->next;
}
list->tail = current;
printf("Sorted list: ");
sll_print(list);
sll_free(list);
printf("\n");
}
/* ============================================================
* EXAMPLE 14: Stack Using Linked List
* ============================================================ */
typedef struct {
SinglyLinkedList *list;
} Stack;
Stack *stack_create(void) {
Stack *stack = malloc(sizeof(Stack));
if (stack == NULL) return NULL;
stack->list = sll_create();
if (stack->list == NULL) {
free(stack);
return NULL;
}
return stack;
}
int stack_push(Stack *stack, int data) {
return sll_prepend(stack->list, data);
}
int stack_pop(Stack *stack, int *data) {
if (stack->list->head == NULL) return -1;
*data = stack->list->head->data;
return sll_delete_first(stack->list);
}
int stack_peek(Stack *stack, int *data) {
if (stack->list->head == NULL) return -1;
*data = stack->list->head->data;
return 0;
}
int stack_is_empty(Stack *stack) {
return stack->list->head == NULL;
}
void stack_free(Stack *stack) {
if (stack) {
sll_free(stack->list);
free(stack);
}
}
void example14_stack_implementation(void) {
printf("=== Example 14: Stack Using Linked List ===\n\n");
Stack *stack = stack_create();
printf("Pushing: 10, 20, 30, 40, 50\n");
stack_push(stack, 10);
stack_push(stack, 20);
stack_push(stack, 30);
stack_push(stack, 40);
stack_push(stack, 50);
int value;
stack_peek(stack, &value);
printf("Top element: %d\n\n", value);
printf("Popping all elements:\n");
while (!stack_is_empty(stack)) {
stack_pop(stack, &value);
printf(" Popped: %d\n", value);
}
stack_free(stack);
printf("\n");
}
/* ============================================================
* EXAMPLE 15: Queue Using Linked List
* ============================================================ */
typedef struct {
SinglyLinkedList *list;
} Queue;
Queue *queue_create(void) {
Queue *queue = malloc(sizeof(Queue));
if (queue == NULL) return NULL;
queue->list = sll_create();
if (queue->list == NULL) {
free(queue);
return NULL;
}
return queue;
}
int queue_enqueue(Queue *queue, int data) {
return sll_append(queue->list, data);
}
int queue_dequeue(Queue *queue, int *data) {
if (queue->list->head == NULL) return -1;
*data = queue->list->head->data;
return sll_delete_first(queue->list);
}
int queue_front(Queue *queue, int *data) {
if (queue->list->head == NULL) return -1;
*data = queue->list->head->data;
return 0;
}
int queue_is_empty(Queue *queue) {
return queue->list->head == NULL;
}
void queue_free(Queue *queue) {
if (queue) {
sll_free(queue->list);
free(queue);
}
}
void example15_queue_implementation(void) {
printf("=== Example 15: Queue Using Linked List ===\n\n");
Queue *queue = queue_create();
printf("Enqueueing: 10, 20, 30, 40, 50\n");
queue_enqueue(queue, 10);
queue_enqueue(queue, 20);
queue_enqueue(queue, 30);
queue_enqueue(queue, 40);
queue_enqueue(queue, 50);
int value;
queue_front(queue, &value);
printf("Front element: %d\n\n", value);
printf("Dequeueing all elements:\n");
while (!queue_is_empty(queue)) {
queue_dequeue(queue, &value);
printf(" Dequeued: %d\n", value);
}
queue_free(queue);
printf("\n");
}
/* ============================================================
* MAIN MENU
* ============================================================ */
void print_menu(void) {
printf("\nLinked Lists in C - Examples Menu\n");
printf("==================================\n\n");
printf("Select an example:\n\n");
printf(" 1. Basic Singly Linked List\n");
printf(" 2. Search and Delete by Value\n");
printf(" 3. Insert at Position\n");
printf(" 4. Reverse a Linked List\n");
printf(" 5. Find Middle Element\n");
printf(" 6. Detect Cycle\n");
printf(" 7. Merge Two Sorted Lists\n");
printf(" 8. Doubly Linked List\n");
printf(" 9. Circular Linked List\n");
printf(" 10. Nth Node from End\n");
printf(" 11. Remove Duplicates\n");
printf(" 12. Check if Palindrome\n");
printf(" 13. Merge Sort\n");
printf(" 14. Stack Implementation\n");
printf(" 15. Queue Implementation\n");
printf(" 0. Run all examples\n\n");
}
int main(int argc, char *argv[]) {
int choice = -1;
if (argc < 2) {
print_menu();
printf("Enter example number: ");
if (scanf("%d", &choice) != 1) {
printf("Invalid input\n");
return 1;
}
printf("\n");
} else {
choice = atoi(argv[1]);
}
switch (choice) {
case 0:
example1_basic_singly_linked_list();
example2_search_and_delete();
example3_insert_at_position();
example4_reverse_list();
example5_find_middle();
example6_detect_cycle();
example7_merge_sorted_lists();
example8_doubly_linked_list();
example9_circular_linked_list();
example10_nth_from_end();
example11_remove_duplicates();
example12_palindrome_check();
example13_merge_sort();
example14_stack_implementation();
example15_queue_implementation();
break;
case 1: example1_basic_singly_linked_list(); break;
case 2: example2_search_and_delete(); break;
case 3: example3_insert_at_position(); break;
case 4: example4_reverse_list(); break;
case 5: example5_find_middle(); break;
case 6: example6_detect_cycle(); break;
case 7: example7_merge_sorted_lists(); break;
case 8: example8_doubly_linked_list(); break;
case 9: example9_circular_linked_list(); break;
case 10: example10_nth_from_end(); break;
case 11: example11_remove_duplicates(); break;
case 12: example12_palindrome_check(); break;
case 13: example13_merge_sort(); break;
case 14: example14_stack_implementation(); break;
case 15: example15_queue_implementation(); break;
default:
printf("Invalid choice. Run without arguments to see menu.\n");
return 1;
}
return 0;
}