Printable View
Hi there,
I'm new in C programming and i need help with Linked List.
I want to build a linked list that will print the words i enter alphabetically.
Can someone give me full steps on how to do it?
I don't need the code.
I don't know what to put in my main or if i need my main at all.
Can someone help please?
I would really appreciate it
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. :)
Linked-lists don't print things.Quote:
Originally Posted by YannB
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.
Yes sorry for being unclear I wanted to know how to build a linked list basted on char instead of int.
Then sort every word i enter in alphabetical order
i just need to know the steps after my structure.
What needs to be in my main.
Sorry if i'm not clear again
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.
Probably easier just to insert each element in order as you're building the list. Then if you find it's slow for the inputs you want to handle, try doing the same thing with a binary tree instead. Less work for you, in either case. You could handle collisions by storing an unsigned int that keeps track of how many times a single word occurred.
Heap Sort is impractical for a linked-list. It's possible to do, but it's horrid.Quote:
Originally Posted by std10093
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
Sorting a list with mergesort is O(nlogn) in the worst case, and I don't think comparison sorts can go faster than that.Quote:
Sorting a list can be slow
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).