I am new to C and have written this code just to teach myself how to work with linked lists and was hoping someone could review it and give me any comments or tips for efficiency, etc. The code just creates a list, adds and removes nodes from the list, and can reverse the list.
/* Creates a linked list, adds and removes nodes and reverses list */
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
typedef bool;
#define false 0
#define true 1
typedef struct node {
int value;
struct node *next;
} node;
node *head = NULL; //Contains entire list
node *current = NULL; //Last item currently in the list
// Initialize list with input value
struct node* create_list(int input)
{
node* ptr;
printf("Creating a LinkedList with head node = %d\n", input);
ptr = (node*)malloc(sizeof(node)); // Allocating 8 bytes of memory for type node pointer
if (ptr == NULL) // Would occur is malloc can't allocate enough memory
{
printf("Node creation failed \n");
return NULL;
}
ptr->value = input;
ptr->next = NULL;
head = current = ptr;
return ptr;
}
// Add input value to the end of the list
struct node* add_to_end(int input)
{
node* ptr;
if (head == NULL)
{
return create_list(input);
}
ptr = (struct node*)malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("Node creation failed \n");
return NULL;
}
else
{
ptr->value = input;
ptr->next = NULL; // End value in list should have NULL next pointer
current -> next = ptr; // Current node contains last value information
current = ptr;
}
printf("%d Added to END of the LinkedList.\n", input);
return head;
}
// Add input value to the head of the list
struct node* add_to_front(int input)
{
node* ptr;
if (head == NULL)
{
return create_list(input);
}
ptr = (struct node*)malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("Node creation failed \n");
return NULL;
}
else
{
ptr->value = input;
ptr->next = head; // Point next value to the previous head
head = ptr;
}
printf("%d Added to HEAD of the LinkedList.\n", input);
return head;
}
// Return the number of items contained in a list
int size_list(node* ptr)
{
int index_count = 0;
while (ptr != NULL)
{
++index_count;
ptr = ptr->next;
}
return index_count;
}
// Add an input value at a user-specified index location in the list (starting from 0 index)
struct node* add_to_list(int input, int index)
{
node* ptr_prev = head;
node* ptr_new;
int index_count; // Used to count size of list
int index_track = 1; // Used to track current index
ptr_new = (struct node*)malloc(sizeof(struct node));
// Check that list exists before adding it in
if (head == NULL)
{
if (index == 0) // Create new list if 0 index is specified
{
add_to_front(input);
}
else
{
printf("Could not insert '%d' at index '%d' in the LinkedList because the list has not been initialized yet.\n", input, index);
return NULL;
}
}
// Count items in list to check whether item can added at specified location
if ((index_count = size_list(head)) < index)
{
printf("Could not insert '%d' at index '%d' in the LinkedList because there are only '%d' nodes in the LinkedList.\n", input, index, index_count);
return NULL;
}
//Go through list -- stop at item before insertion point
while (ptr_prev != NULL)
{
if (index == 0) // Use add_to_front function if user-specified index is 0 (the head of the list)
{
add_to_front(input);
return head;
}
if ((index_track) == index)
{
break;
}
ptr_prev = ptr_prev ->next;
++index_track;
}
ptr_new ->next = ptr_prev ->next; // Change the new node to point to the original's next pointer
ptr_new->value = input;
ptr_prev ->next = ptr_new; // Change the original node to point to the new node
return head;
}
// Verify if the list contains an input value and return the pointer to the value if it exists
struct node* search_list(int input, struct node **prev)
{
node* ptr = head;
node* temp = (node*)malloc(sizeof(node));
bool found = false;
// Search if value to be deleted exists in the list
while (ptr != NULL)
{
if(ptr->value == input)
{
found = true;
break;
}
else
{
temp = ptr;
ptr = ptr ->next;
}
}
// If the value is found in the list return the ptr to it
if(found == true)
{
if(prev)
*prev = temp;
return ptr;
}
else
{
return NULL;
}
}
// Remove an input value from the list
struct node* remove_from_list(int input)
{
node* prev = NULL; // list starting from one item before value to be deleted
node* del = NULL; // pointer to deleted value
// Obtain pointer to the list value to be deleted
del = search_list(input, &prev);
if(del == NULL)
{
printf("Error: '%d' could not be deleted from the LinkedList because it could not be found\n");
return NULL;
}
else
{
if (prev != NULL)
{
prev->next = del->next;
}
if (del == current) // If item to be deleted is last in list, set the current last item as the item before deleted one
{
current = prev;
}
else if (del == head) // If item to be deleted is the head of the list, set the new head as the item following the deleted one
{
head = del ->next;
}
return head;
}
}
// Reverse the order of the list
struct node* reverse_list()
{
node* reverse = NULL;
node* next = NULL;
node* ptr = head;
if (head == NULL)
{
printf("Error: There is no LinkedList to reverse.\n");
return NULL;
}
printf("Reversing order of the LinkedList.\n");
while (ptr != NULL)
{
next = ptr ->next; // Holds the remaining items in the original list
ptr ->next = reverse; // List now points to items in reversed list
reverse = ptr; // Reversed list set equal to the List
ptr = next; // List re-pointed back to hold list
}
head = reverse;
}
// Print the list to the console
void print_list()
{
node* ptr = head;
printf("------------------------------\n");
printf("PRINTING LINKED LIST\n");
while (ptr != NULL)
{
printf("%d\n", ptr->value);
ptr = ptr->next;
}
printf("------------------------------\n");
}
int main()
{
int i;
reverse_list(); //test function error message
for (i = 3; i > 0; --i)
{
add_to_front(i);
}
for (i= 4; i < 7; ++i)
{
add_to_end(i);
}
add_to_list(4,9); //test function error message
add_to_list(4,1);
print_list();
remove_from_list(3);
print_list();
reverse_list();
print_list();
add_to_list(10,0);
print_list();
getchar();
}
Also, I'm trying to make a function which takes the list and randomizes the node order. Any suggestions for how this can be done?
Thanks!
**EDIT: code revision with some additional functionality**
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
typedef bool;
#define false 0
#define true 1
typedef struct node {
int value;
struct node *next;
} node;
// Initialize list with input value
node* create_list(int input)
{
node* ptr = malloc(sizeof(*ptr));
if (ptr == NULL)
return NULL;
ptr -> value = input;
ptr -> next = NULL;
return ptr;
free(ptr);
}
// Add input value to the end of the list
node* add_to_end(node* head, int input)
{
node* ptr = malloc(sizeof(*ptr));
node* temp = head;
// If there is not yet a list, initialize the list with the input value
if (head == NULL)
return create_list(input);
if (ptr == NULL)
return NULL;
else
{
ptr -> value = input;
ptr -> next = NULL;
// Find the last element of the list
while (temp->next != NULL)
temp = temp->next;
// Add new node to the end of the list
temp->next = ptr;
ptr = head;
return ptr;
}
free(ptr);
free(temp);
}
// Add input value to the head of the list
node* add_to_front(node* head, int input)
{
node* ptr = malloc(sizeof(*ptr));
// If there is not yet a list, initialize the list with the input value
if (head == NULL)
return create_list(input);
if (ptr == NULL)
return NULL;
else
{
ptr -> value = input;
ptr -> next = head; // Point next value to the previous head
head = ptr;
return ptr;
}
free(ptr);
}
// Add an input value at a user-specified index location in the list (starting from 0 index)
node* add_to_list(node* head, int input, int index)
{
node* ptr_prev = head;
node* temp = NULL; // Temperary node to hold leading values
int index_track = 0; // Used to track current index
// Check that list exists before adding it in
if (head == NULL)
{
if (index == 0) // Create new list if 0 index is specified
{
ptr_prev = add_to_front(ptr_prev, input);
return ptr_prev;
}
else
return NULL;
}
//Go through list -- stop at item before insertion point
while (ptr_prev != NULL)
{
if (index == 0) // Use add_to_front function if user-specified index is 0 (the head of the list)
{
ptr_prev = add_to_front(ptr_prev, input);
return ptr_prev;
break;
}
if ((index_track + 1) == index)
{
temp = add_to_end(temp, ptr_prev->value);
ptr_prev = ptr_prev ->next;
temp = add_to_end(temp, input); // Temporary node now contains all leading + new input value
// Join leading + following nodes remaining in ptr_prev
while (ptr_prev != NULL)
{
temp = add_to_end(temp, ptr_prev->value);
ptr_prev = ptr_prev ->next;
}
ptr_prev = temp;
return ptr_prev;
break;
}
temp = add_to_end(temp, ptr_prev->value);
ptr_prev = ptr_prev ->next;
++index_track;
}
free(ptr_prev);
free(temp);
}
// Verify if the list contains an input value and return a true/false value
bool search_list(node* head, int input)
{
node* ptr = head;
node* temp = malloc(sizeof(*temp));
bool found = false;
// Search if value exists in the list
while (ptr != NULL)
{
if(ptr->value == input)
{
found = true;
break;
}
else
{
temp = ptr;
ptr = ptr ->next;
}
}
return found;
free(ptr);
free(temp);
}
// Remove the an input value from the list (either first instance of the value or every instance of value)
node* remove_from_list(node* head, int input, bool single_instance)
{
bool instance = true; // Determines whether to remove one or every instance of value
node* ptr = head;
node* prev = NULL;
node* temp = NULL;
if (ptr == NULL)
return NULL;
while (instance)
{
// Remove single instance of value
while (ptr != NULL)
{
// Delete the input value
if (ptr->value == input)
{
// Case 1: Remove head value
if (prev == NULL)
{
head = ptr->next;
ptr = head;
}
// Case 2: Remove end value
else if (ptr->next == NULL)
ptr = temp;
// Case 3: Remove middle value
else
{
ptr = ptr->next;
while(ptr != NULL)
{
temp = add_to_end(temp, ptr->value);
ptr = ptr->next;
}
ptr = temp;
}
break;
}
prev = ptr; // previous list starting from one item before value to be deleted
temp = add_to_end(temp, prev->value);
ptr = ptr ->next;
}
if (single_instance) // Only remove single instance if specified true in input
instance = false;
else
instance = search_list(ptr, input); // Check if there are more instances of value to be removed
prev = NULL;
temp = NULL;
}
return ptr;
free(ptr);
free(temp);
free(prev);
}
// Remove a specific index from the list
node* remove_index(node* head, int index)
{
int count = 0; // Iteration count
node* ptr = head;
node* prev = NULL;
node* temp = NULL;
if (ptr == NULL)
return NULL;
while (ptr != NULL)
{
// Delete the index value
if (count == index)
{
// Case 1: Remove head value
if (prev == NULL)
{
head = ptr->next;
ptr = head;
}
// Case 2: Remove end value
else if (ptr->next == NULL)
ptr = temp;
// Case 3: Remove middle value
else
{
ptr = ptr->next;
while(ptr != NULL)
{
temp = add_to_end(temp, ptr->value);
ptr = ptr->next;
}
ptr = temp;
}
break;
}
prev = ptr; // previous list starting from one item before value to be deleted
temp = add_to_end(temp, prev->value);
ptr = ptr ->next;
++count;
}
return ptr;
free(ptr);
free(temp);
free(prev);
}
// Reverse the order of the list
node* reverse_list(node* head)
{
node* reverse = NULL;
node* next = NULL;
node* ptr = head;
if (head == NULL)
return NULL;
while (ptr != NULL)
{
next = ptr ->next; // Holds the remaining items in the original list
ptr ->next = reverse; // List now points to items in reversed list
reverse = ptr; // Reversed list set equal to the List
ptr = next; // List re-pointed back to hold list
}
ptr = reverse;
return ptr;
free(reverse);
free(next);
free(ptr);
}
// Change the value of a node
node* changeValue(node* head, int index, int newValue)
{
node* ptr = head;
node* temp = NULL;
int index_track = 0;
while (ptr != NULL)
{
if (index == 0)
{
ptr->value = newValue;
break;
}
if (index_track + 1 == index)
{
temp = add_to_end(temp, ptr->value);
ptr = ptr ->next;
ptr->value = newValue;
while(ptr != NULL)
{
temp = add_to_end(temp, ptr->value);
ptr = ptr->next;
}
ptr = temp;
break;
}
temp = add_to_end(temp, ptr->value);
ptr = ptr->next;
++index_track;
}
return ptr;
free(temp);
free(ptr);
}
// Find the value of a node
int nodeValue(node* head, int index)
{
node* ptr = head;
int index_track = 0;
while (ptr != NULL)
{
if (index_track == index)
return ptr->value;
ptr = ptr->next;
++ index_track;
}
return NULL; // Return NULL if there is no value at specified index
free(ptr);
}
// Swap two nodes
node* swap(node* head, int index1, int index2)
{
node* ptr = head;
int val1, val2;
// Obtain values at each index
val1 = nodeValue(ptr, index1);
val2 = nodeValue(ptr, index2);
// Change the values of each node
ptr = changeValue(ptr, index1, val2);
ptr = changeValue(ptr, index2, val1);
return ptr;
free(ptr);
}
// Print the list to the console
void print_list(node* head)
{
node* ptr = head;
printf("------------------------------\n");
printf("PRINTING LINKED LIST\n");
while (ptr != NULL)
{
printf("%d\n", ptr->value);
ptr = ptr->next;
}
printf("------------------------------\n");
free(ptr);
}
I would appreciate if anyone could look at my new code. Also, now that I've created these functions, how do I call them from other files in my program (using Visual Studio 2010)?