I have been asked a few times to provide a complete working example of different operations on Linked List.
This post is an attempt to do just that.
#include <stdio.h>
#include <stdlib.h> // for malloc
// define your linked list struct
// make sure to typedef to give better name
typedef struct ll
{
int data;
struct ll *next;
} LinkedListNode;
// remember to declare functions that will be used in main but defined after it
LinkedListNode* AddElementsToBeginningOfList(int inputSize, int input[], LinkedListNode *head);
LinkedListNode* AddElementsToEndOfList(int inputSize, int input[], LinkedListNode *head);
LinkedListNode* InsertElementAtBeginning(int input, LinkedListNode *head);
LinkedListNode* InsertElementAtEnd(int input, LinkedListNode *head);
void Sort(LinkedListNode *head);
LinkedListNode* Find(int value, LinkedListNode *head);
void MaxMinInList(int *max, int *min, LinkedListNode *head);
void PrintLinkedList(char* name, LinkedListNode *node);
int main(int argc, char* argv[])
{
// define head node
LinkedListNode* head = NULL;
LinkedListNode* inOrderList = NULL;
int max = 0, min = 0;
LinkedListNode* ele = NULL;
// de fine array
int input[] = { 43, 22, 11, 4, 22, 56, 47, 21, 78, 99, 97 };
// find the array length in C
int inputSize = sizeof(input) / sizeof(input[0]);
// add elements to the beginning of the list
head = AddElementsToBeginningOfList(inputSize, input, head);
// Print list
PrintLinkedList("AddElementsToBeginningOfList", head);
// add elements to the end of the list
inOrderList = AddElementsToEndOfList(inputSize, input, inOrderList);
// Print list
PrintLinkedList("AddElementsToEndOfList", inOrderList);
// insert a single element at beginning
inOrderList = InsertElementAtBeginning(100, inOrderList);
// Print list
PrintLinkedList("InsertElementAtBeginning", inOrderList);
// insert a single element at end
inOrderList = InsertElementAtEnd(200, inOrderList);
// Print list
PrintLinkedList("InsertElementAtEnd", inOrderList);
// Search for an element
ele = Find(56, inOrderList);
if (ele != NULL) {
printf("\r\nElement found: %d", ele->data);
}
// Find max and min in the list
MaxMinInList(&max, &min, inOrderList);
printf("\r\nMax: %d, Min: %d", max, min);
// sort the list
Sort(inOrderList);
// Print list
PrintLinkedList("Sorted list", inOrderList);
return 0;
}
LinkedListNode* AddElementsToBeginningOfList(int inputSize, int input[], LinkedListNode *head)
{
// define loop variable
int i = 0;
// add elements to the linked list
for (i = 0; i < inputSize; i++)
{
// create a temp node
LinkedListNode *temp = (LinkedListNode *)malloc(sizeof(LinkedListNode));
temp->data = input[i];
// add to the beginning of the list
// make this new node point to the current beginning of the list
temp->next = head;
// NOW set the head of the list to this new node
head = temp;
}
return head;
}
LinkedListNode* AddElementsToEndOfList(int inputSize, int input[], LinkedListNode *head)
{
// define loop variable
int i = 0;
// define the end of the list
// here is where new elements will be inserted
LinkedListNode* end = NULL;
// add elements to the linked list
for (i = 0; i < inputSize; i++)
{
// create a temp node
LinkedListNode *temp = (LinkedListNode *)malloc(sizeof(LinkedListNode));
temp->data = input[i];
// make sure to null the pointer to the last element
temp->next = NULL;
// if this is the first element, make head point to it
if (i == 0) {
head = temp;
}
else {
// add to the end of the list
end->next = temp;
}
// NOW set the end of the list to this new node
end = temp;
}
return head;
}
LinkedListNode* InsertElementAtBeginning(int input, LinkedListNode *head)
{
// create a temp node
LinkedListNode *temp = (LinkedListNode *)malloc(sizeof(LinkedListNode));
temp->data = input;
// add to the beginning of the list
// make this new node point to the current beginning of the list
temp->next = head;
// NOW set the head of the list to this new node
head = temp;
return head;
}
LinkedListNode* InsertElementAtEnd(int input, LinkedListNode *head)
{
LinkedListNode* curr = head;
// create a temp node
LinkedListNode *temp = (LinkedListNode *)malloc(sizeof(LinkedListNode));
temp->data = input;
temp->next = NULL;
while (curr->next != NULL)
curr = curr->next;
// add it as the last node
curr->next = temp;
return head;
}
void Sort(LinkedListNode *head)
{
LinkedListNode *list = NULL;
LinkedListNode *pass = NULL;
// traverse the entire list
for (list = head; list->next != NULL; list = list->next)
{
// compare to the list ahead
for (pass = list->next; pass != NULL; pass = pass->next)
{
// compare and swap
if (list->data > pass->data)
{
// swap
int temp = list->data;
list->data = pass->data;
pass->data = temp;
}
}
}
}
// finds the first node with the specified value
LinkedListNode* Find(int value, LinkedListNode *head)
{
// start at the root
LinkedListNode *currentNode = head;
// loop through the entire list
while (currentNode != NULL)
{
// if we have a match
if (currentNode->data == value)
return currentNode;
else // move to the next element
currentNode = currentNode->next;
}
}
// finds the maximum and minimum in the list
void MaxMinInList(int *max, int *min, LinkedListNode *head)
{
// start at the root
LinkedListNode *curr = head;
if (curr == NULL)
return 0; // list is empty
// initialize the max and min values to the first node
*max = *min = curr->data;
// loop through the list
for (curr = curr->next; curr != NULL; curr = curr->next)
{
if (curr->data > *max)
*max = curr->data;
else if (curr->data < *min)
*min = curr->data;
}
}
// print the list
void PrintLinkedList(char* name, LinkedListNode *node)
{
printf("\r\nName: %s", name);
printf("\r\n HEAD");
// loop while we have data
while (node != NULL)
{
printf(" -> %d", node->data);
// move to next node
node = node->next;
}
}
