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:

`typedef struct linked_list{    int data;    struct linked_list *next;} 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 elsewhereNode* Find(int value){    // start at the root    Node *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;    }}`

Find maximum and minimum in a linked list

`// finds the maximum and minimum in the list// assumes that head pointer is defined elsewhereint MaxMinInList(int *max, int *min){    // start at the root    Node *currentNode = head;    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;    }    // we found our answer    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

15. The share your really gives us excitement. Thanks for your sharing. If you feel tired at work or study try to participate in our games to bring the most exciting feeling. Thank you!