Thread: Linked List Process in C

Every node will be a struct that will hold a string and a pointer to next node of the list.
You read one word, you create a node.
You read the 2nd word and you traverse the list until you find where the node with the second node should be placed.
Continue until you read all the words.

That's the approach I would use, assuming that the words come to me in a random order..

Here is a small .h I use for managing a list of integers. It may give you some boost.

Originally Posted by YannB

I want to build a linked list that will print the words i enter alphabetically.

Linked-lists don't print things.
Perhaps you mean you want to produce a program containing a linked-list of words to print those words alphabetically. In that case you want a sorting algorithm that is appropriate for a linked-list. Insertion sort and merge sort are good candidates for that.

You should make a start, doing the bits that you do know how to do, and post that.

I think iMalc's idea is more efficient.

Create the list by inserting every word at the start of the list. Time complexity : O(n)
Sort with merge-sort, heap-sort or even quicksort : O(nlogn)
Print the list : O(n)
Complexity : O(nlogn)

With my approach, the complexity may be a little bigger, so I think iMalc's should be followed. After all, it seems more clear and easy to do.

You can check the link I provided in post number two. It has a demonstration main as well.
You should however use as data member of the struct a string instead of an int.
Also, remember that in C, we use strcmp to compare strings.

For the stirng you have to choices.
1-Use as member of the struct an array of chars with a fixed size.
2-use a char pointer and allocate dynamically (with malloc) the exact space that every word needs. In this case don't forget to first free the string and then the node, when freeing the list.

Oh and remember than in case you need to swap two nodes, in my mind it is easier to swap their contents instead of the pointers.

For example, you have two nodes, 1 and 2.
Assume that every struct has two data members, an integer and a pointer to the next node.
In order to swap them, in my way, just copy number two to the first struct and number one to the second struct. You may use a temp variable to swap, but you can do it without one. But, I recommend you use one.

Originally Posted by std10093

Sort with merge-sort, heap-sort or even quicksort : O(nlogn)

Heap Sort is impractical for a linked-list. It's possible to do, but it's horrid.
Quick Sort is an option, but not an attractive one. It's not ideal for linked-lists, as it suffers from the possibility of becomming O(n*n), which is generally far more likely with most implementations than it is for array sorting. It's a lot more difficult to pick a good splitter, and most implementations tend to pick the worst possible choice much of the time.
Merge Sort for a linked-list OTOH is always O(n*logn) and is done in-place with no extra buffer.

Seldom is it ever worth considering anything other than these three for a linked-list:
Insertion Sort I(n*n), or
Merge Sort O(n*logn), or
Bucket Sort ~ O(n*loglogn) (For large n, the number of balls per bucket should follow a Poisson distribution).

I should also say that if you go the Insertion route, then you can just insert each item as you go, though it makes very little difference overall.

@Barney, I thought of this too, but will it be efficient?
I mean with every word you receive, you need to traverse the list to find out where the node should be placed. So, that yields in worst case scenario, O(n²).
Well if you are planning to use a non-optimum sorting algorithm, then better do it like this. But, most implementations, provide insert at the end or the start of the list, thus you need to make a new method for inserting at i-th position of the list.

@iMalc, I think mergesort is the one that we would use. Also, quicksort, for a random input, will take O(nlogn).

But, wouldn't be easy to put the strings into an array, sort the array and then construct the list? We will increase the space complexity but think of the trade off. Sorting a list can be slow. I will follow this approach and I am going to implement it too! Hopefully I will have some results soon.

//If you need a place to check sorting algorithms, visit iMalc's homepage

Of course not! Remember the proof with the tree.

A sorting algorithm is optimum in terms of time if and only if it has time complexity O(nlogn).