## Sunday, May 15, 2011

### Linked Lists – Sorting, Searching, Finding Maximum and Minimum

In one of the previous posts, we discussed in depth the concepts behind linked lists. In this post, we will explore some more programs and applications built on linked lists. Remember that the data structure that we are using is quite simple:

{
int data;
} Node;

We define a data element and a pointer to the next node. Let’s first start with sorting a linked list.

void Sort()
{
// traverse the entire list
for (Node *list = head; list->next != NULL; list = list->next)
{
// compare to the list ahead
for (Node *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;
}
}
}
}

As you see above, sorting a linked list is not very different that sorting an array.

#### Search an element in linked list

// finds the first node with the specified value
// assumes that head pointer is defined elsewhere
Node* Find(int value)
{
// start at the root

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

#### Find maximum and minimum in a linked list

// finds the maximum and minimum in the list
// assumes that head pointer is defined elsewhere
int MaxMinInList(int *max, int *min)
{
// start at the root

if (currentNode == NULL)
return 0; // list is empty

// initialize the max and min values to the first node
*max = *min = currentNode->data;

// loop through the list
for (currentNode = currentNode->next; currentNode != NULL; currentNode = currentNode->next)
{
if (currentNode->data > *max)
*max = currentNode->data;
else if (currentNode->data < *min)
*min = currentNode->data;
}

return 1;
}

At this point, you should be very comfortable with linked lists and ready to tackle some more complex operations and structures.

1. Yes, it is true. linked lists aren't rocket science as I used to think :D

2. yes but what if we need to return the value of the location of the Node?

3. your sort technique is a bit confusing. suppose you have a list 5,3,8,9,2,6.
it will only loop through the entire list once and won't sort it completely.After 1st iteration the list will be: 3,5,8,2,6,9. Which is not sorted. Correct me if I am wrong.

1. Ya... You are correct... It's true... He is finishing in o(n).. Possibly its not possible

4. @previous
there are two loops used
its a bubble sort .. you are running only inner loop

5. How many nodes does a shortest linked list have???

6. why the head is giving an error???

1. What error are you seeing?

1. Is this a compile time error or a runtime error? Can you post the relevant error details from the VS output window?

Have you properly initialized the head pointer?

8. I copied the minimum and sorting part together in a file but im getting so many errors that many semi commas are missing

1. Aha. You of course need to fill in the other parts of the program. You need to write the main method, declare structures, etc. I would recommend picking a basic book and try from it.

9. couldn't do it :(

10. Hi,
I need a help with a question. There are two list-L1 and L2 of words, compare the two list and put the uncommon word into a new list called Result.
I need the simplified soln for this, so that the nested looping will not occur and time taken by system is less.

My Email id: rajan_raj31@rediffmail.com

Thanks.
Rajan

1. Rajan,
I would love to see what solution you have come up with. Maybe we can work together to optimize it then.
Nikhil

11. can u give the full code for the maximum and minimum linked list, i mean the main section

1. Sure. Keep an eye on the blog for a new blog post that will give you the complete solution.

2. Hi Hassan,
Take a look at my latest post - http://www.programminginterviews.info/2013/10/linked-list-create-insert-sort-min-max-find-print-complete-program.html

12. You can find out the cycle or loop in a single linked list by using two pointer approach.
Below link can be useful to find out the algorithm to find cycle or loop in linked list

find out the cycle or loop in a single linked list in java

13. Hi can you help with this two questions?

14. can you pleases give me the code of making maximum and minimum no of list means 12345678 is the input data of your list the you can convert the list is like that
18273645

erp in chennai | cloud erp software in chennai

16. hello....i need a help...first you need to create circular linked list then do search process and then the element you searched has to be deleted...
lets say i have created a circular linked list, i have inserted elements like 5,10,15,20,25..if i enter the 15, the location of the element is 3 has to be shown and that element 15 has to get deleted..this is problem..can you please help me with that..
Thank you
Aneesh

My email id: aneesh.muthyala8@gmail.com

17. Nice blog to read, Thanks for sharing this valuable article.

Apache Spark Training in Pune
Spark Training Institute in Pune

18. After going through your contents I realize that this is the best of my knowledge as it provides the best information and suggestions. This is very helpful and share worthy. If you are looking for the best alteryx then visit Analytics Fun. Keep sharing more.

19. Thankfulness to my dad who informed me relating to this blog, this website is really amazing.
logo designer company