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

9 comments:

  1. Can anyone check this website and let me know how to code like this. They are amazingly done their coding and I wanted to get my website done like this.

    ReplyDelete
  2. This process can only be done after the property have been registered following the link of Banglarbhumi.gov.in

    ReplyDelete
  3. Ukrainian is spoken in Ukraine. The linguistic diversity of Ukraine is diverse in terms of the fragmentation scale, which for Ukraine is 0.4741. Followers of Christianity make up the religious majority in the country. 68.9% of the Ukrainian population lives in cities. This percentage is the urban population of Ukraine. The level of urbanization in Ukraine is -0.7. The negative rates of urbanization in Ukraine indicate a lack of economic strength and stability in the cities of this country. This may indicate that investing in this country's industry is a gamble; declining urbanization can lead to labor shortages for large business projects. According to the data on tourists entering Ukraine, 24,671,000 tourists arrive in the country annually. http://www.confiduss.com/en/jurisdictions/ukraine/politics/

    ReplyDelete
  4. I truly get pleasure from while I read your blogs and its content.
    UI company

    ReplyDelete
  5. In the world of automation testing, knowledge and expertise are the keys to success. APTRON Solution Noida, with its commitment to excellence, experienced trainers, industry-relevant curriculum, and practical approach to learning, is your ideal partner in your journey to becoming a proficient automation tester. If you're looking for an Automation Testing Training Institute in Noida that can shape your future in the IT industry, APTRON Solution Noida is your destination of choice. Join us today and unlock a world of career opportunities in automation testing.

    ReplyDelete