Please navigate to the bottom of the page for Table of Contents

Monday, October 14, 2013

Linked List create, insert, sort, min, max, find and print complete program

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;
}
}

2 comments: