// =============================================================================
// ACTIVITY 4: PERFORMANCE COMPARISON - ARRAYS VS LINKED LISTS
// Introduction to Data Structures in C
// =============================================================================
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Test configuration
#define PERFORMANCE_TEST_SIZE 10000
#define SEARCH_ITERATIONS 100
// =============================================================================
// BASIC LINKED LIST STRUCTURE (Required for comparison)
// =============================================================================
typedef struct Node {
int data;
struct Node* next;
} Node;
// Simple node creation function
Node* create_node(int data) {
Node* new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) return NULL;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
// Simple insert at end function for linked list
Node* insert_at_end(Node* head, int data) {
Node* new_node = create_node(data);
if (new_node == NULL) return head;
if (head == NULL) return new_node;
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = new_node;
return head;
}
// Simple search function for linked list
int search_in_list(Node* head, int target) {
Node* current = head;
int position = 0;
while (current != NULL) {
if (current->data == target) {
return position;
}
current = current->next;
position++;
}
return -1; // Not found
}
// Free linked list memory
void free_list(Node* head) {
Node* current = head;
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
}
// =============================================================================
// PERFORMANCE TEST FUNCTIONS
// =============================================================================
/**
* Test array performance for various operations
* @return: Time taken in seconds
*/
double test_array_performance() {
printf(" Creating array of %d elements...\n", PERFORMANCE_TEST_SIZE);
clock_t start = clock();
// Step 1: Create and populate array
int* arr = (int*)malloc(PERFORMANCE_TEST_SIZE * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed for array!\n");
return -1;
}
// Insert elements (O(1) for each insertion)
for (int i = 0; i < PERFORMANCE_TEST_SIZE; i++) {
arr[i] = i;
}
printf(" Array population completed\n");
// Step 2: Random access test (Arrays excel here - O(1))
printf(" Performing random access test...\n");
long long sum = 0;
for (int i = 0; i < PERFORMANCE_TEST_SIZE; i++) {
sum += arr[i]; // Direct access by index
}
// Step 3: Search test (Linear search - O(n))
printf(" Performing %d search operations...\n", SEARCH_ITERATIONS);
int found_count = 0;
for (int i = 0; i < SEARCH_ITERATIONS; i++) {
int target = rand() % PERFORMANCE_TEST_SIZE;
// Linear search in array
for (int j = 0; j < PERFORMANCE_TEST_SIZE; j++) {
if (arr[j] == target) {
found_count++;
break;
}
}
}
// Clean up
free(arr);
clock_t end = clock();
printf(" Array test completed. Found %d/%d elements\n", found_count,
SEARCH_ITERATIONS);
return ((double)(end - start)) / CLOCKS_PER_SEC;
}
/**
* Test linked list performance for various operations
* @return: Time taken in seconds
*/
double test_linkedlist_performance() {
printf(" Creating linked list of %d elements...\n", PERFORMANCE_TEST_SIZE);
clock_t start = clock();
// Step 1: Create and populate linked list
Node* head = NULL;
// Insert elements at end (O(n) for each insertion due to traversal)
for (int i = 0; i < PERFORMANCE_TEST_SIZE; i++) {
head = insert_at_end(head, i);
}
printf(" Linked list population completed\n");
// Step 2: Sequential traversal test (O(n))
printf(" Performing sequential traversal test...\n");
long long sum = 0;
Node* current = head;
while (current != NULL) {
sum += current->data;
current = current->next;
}
// Step 3: Search test (Linear search - O(n))
printf(" Performing %d search operations...\n", SEARCH_ITERATIONS);
int found_count = 0;
for (int i = 0; i < SEARCH_ITERATIONS; i++) {
int target = rand() % PERFORMANCE_TEST_SIZE;
if (search_in_list(head, target) != -1) {
found_count++;
}
}
// Clean up
free_list(head);
clock_t end = clock();
printf(" Linked list test completed. Found %d/%d elements\n", found_count,
SEARCH_ITERATIONS);
return ((double)(end - start)) / CLOCKS_PER_SEC;
}
// =============================================================================
// ANALYSIS AND COMPARISON FUNCTIONS
// =============================================================================
/**
* Analyze and display the performance comparison results
* @param array_time: Time taken by array operations
* @param linkedlist_time: Time taken by linked list operations
*/
void analyze_performance(double array_time, double linkedlist_time) {
printf("\n=== PERFORMANCE ANALYSIS ===\n");
printf("Array operations time: %.4f seconds\n", array_time);
printf("Linked List operations time: %.4f seconds\n", linkedlist_time);
if (array_time < linkedlist_time) {
printf("Result: Arrays are %.2fx FASTER for this test\n",
linkedlist_time / array_time);
} else {
printf("Result: Linked Lists are %.2fx FASTER for this test\n",
array_time / linkedlist_time);
}
printf("\n=== THEORETICAL COMPLEXITY COMPARISON ===\n");
printf("Operation | Array Time | Linked List Time\n");
printf("--------------------+------------+-----------------\n");
printf("Access by index | O(1) | O(n)\n");
printf("Insert at beginning | O(n) | O(1)\n");
printf("Insert at end | O(1)* | O(n)\n");
printf("Insert at middle | O(n) | O(n)\n");
printf("Delete at beginning | O(n) | O(1)\n");
printf("Delete at end | O(1)* | O(n)\n");
printf("Search (unsorted) | O(n) | O(n)\n");
printf("*Assuming dynamic array with available space\n");
printf("\n=== MEMORY USAGE COMPARISON ===\n");
printf("Arrays:\n");
printf(" - Memory per element: %zu bytes\n", sizeof(int));
printf(" - Total for %d elements: %zu bytes\n",
PERFORMANCE_TEST_SIZE, PERFORMANCE_TEST_SIZE * sizeof(int));
printf(" - Memory overhead: Minimal (contiguous allocation)\n");
printf("Linked Lists:\n");
printf(" - Memory per element: %zu bytes (data + pointer)\n", sizeof(Node));
printf(" - Total for %d elements: %zu bytes\n",
PERFORMANCE_TEST_SIZE, PERFORMANCE_TEST_SIZE * sizeof(Node));
printf(" - Memory overhead: High (pointer storage + fragmentation)\n");
printf("\n=== PRACTICAL RECOMMENDATIONS ===\n");
printf("Use Arrays when:\n");
printf(" • You need frequent random access to elements\n");
printf(" • Memory efficiency is important\n");
printf(" • You know the approximate size in advance\n");
printf(" • Cache performance matters\n");
printf("\nUse Linked Lists when:\n");
printf(" • Frequent insertions/deletions at beginning or middle\n");
printf(" • Size varies dramatically during runtime\n");
printf(" • You don't need random access to elements\n");
printf(" • Memory allocation flexibility is needed\n");
}
// =============================================================================
// MAIN DEMONSTRATION FUNCTION
// =============================================================================
/**
* Main performance comparison demonstration
*/
void performance_comparison_demo() {
printf("\n=== PERFORMANCE COMPARISON: ARRAYS VS LINKED LISTS ===\n");
printf("Testing with %d elements and %d search operations...\n",
PERFORMANCE_TEST_SIZE, SEARCH_ITERATIONS);
// Seed random number generator for consistent results
srand((unsigned int)time(NULL));
printf("\n--- Testing Array Performance ---\n");
double array_time = test_array_performance();
printf("\n--- Testing Linked List Performance ---\n");
double linkedlist_time = test_linkedlist_performance();
// Analyze and display results
if (array_time >= 0 && linkedlist_time >= 0) {
analyze_performance(array_time, linkedlist_time);
} else {
printf("Performance test failed due to memory allocation error.\n");
}
}
// =============================================================================
// MAIN FUNCTION FOR STANDALONE TESTING
// =============================================================================
int main() {
printf("=== PERFORMANCE COMPARISON TOOL ===\n");
performance_comparison_demo();
return 0;
}
