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;

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

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

ReplyDeleteyes but what if we need to return the value of the location of the Node?

ReplyDeleteyour sort technique is a bit confusing. suppose you have a list 5,3,8,9,2,6.

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

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

Delete@previous

ReplyDeletethere are two loops used

its a bubble sort .. you are running only inner loop

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

ReplyDeletewhy the head is giving an error???

ReplyDeleteWhat error are you seeing?

Deleteidentifier head is undefined

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

DeleteHave you properly initialized the head pointer?

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

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

Deletecouldn't do it :(

ReplyDeleteHi,

ReplyDeleteI 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

Rajan,

DeleteI would love to see what solution you have come up with. Maybe we can work together to optimize it then.

Nikhil

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

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

DeleteHi Hassan,

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

You can find out the cycle or loop in a single linked list by using two pointer approach.

ReplyDeleteBelow 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