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.

18 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