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

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.

Sort 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
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 elsewhere
int 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.

26 comments:

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

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

    ReplyDelete
  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.

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

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

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

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

    ReplyDelete
  7. identifier head is undefined

    ReplyDelete
    Replies
    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?

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

    ReplyDelete
    Replies
    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.

      Delete
  9. couldn't do it :(

    ReplyDelete
  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

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

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

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

      Delete
    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

      Delete
  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

    ReplyDelete
  13. Hi can you help with this two questions?

    http://stackoverflow.com/questions/27681544/c-programming-linked-list-sort-etc

    ReplyDelete
  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

    ReplyDelete
  15. I'm happy to read this article.Thanks for your information! Keep sharing..
    erp in chennai | cloud erp software in chennai

    ReplyDelete
  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

    ReplyDelete
  17. 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.

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

    ReplyDelete