By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,630 Members | 1,174 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,630 IT Pros & Developers. It's quick & easy.

Ordering a singly linked list

P: 61
Hi,

I am having problem with ordering a singly linked list. Since a singly linked list goes only one way, is it possible to order them?

If my structs look like the one below.

Expand|Select|Wrap|Line Numbers
  1. struct block
  2. {
  3.    struct block *next;
  4.    int number;
  5. };
  6. typedef struct block block;
  7.  
Oct 31 '07 #1
Share this Question
Share on Google+
6 Replies


sicarie
Expert Mod 2.5K+
P: 4,677
Just out of curiosity, why not use the linked list in the STL (The one with a built-in sort() function) ?

Ordering a singly linked list is possible. You have to have a pointer to both of the (using your example) blocks - prev_block and next_block respectively (though you have prev_block->next, so you can use that...), create your new_block and assign it a value, point new_block's next to next_block, and then prev_block->next to new_block. Then you need to put your pointer on pre_del_block and get the block_to_delete->next, and move block_to_delete->next to pre_del_block->next (assuming there was a block being moved from one position to another inside the list.

Not really an algorithm, but does that give you a general idea?
Oct 31 '07 #2

P: 61
Just out of curiosity, why not use the linked list in the STL (The one with a built-in sort() function) ?

Ordering a singly linked list is possible. You have to have a pointer to both of the (using your example) blocks - prev_block and next_block respectively (though you have prev_block->next, so you can use that...), create your new_block and assign it a value, point new_block's next to next_block, and then prev_block->next to new_block. Then you need to put your pointer on pre_del_block and get the block_to_delete->next, and move block_to_delete->next to pre_del_block->next (assuming there was a block being moved from one position to another inside the list.

Not really an algorithm, but does that give you a general idea?
Yes it does, I was thinking along the same lines.

Never heard of the STL one coz I am rather new to C and link list altogether.

Cheers.
Oct 31 '07 #3

weaknessforcats
Expert Mod 5K+
P: 9,197
Never heard of the STL
The STL is the C++ Standard Template Library. There is code in there for variable sized arrays, linked lists, trees, sorting, etc. All the necessary plumbing you use in software development. You can use it or, you an re-invent the wheel and rewrite in your own image making your code much harder to understand by the next person.
Oct 31 '07 #4

sicarie
Expert Mod 2.5K+
P: 4,677
The STL is the C++ Standard Template Library. There is code in there for variable sized arrays, linked lists, trees, sorting, etc. All the necessary plumbing you use in software development. You can use it or, you an re-invent the wheel and rewrite in your own image making your code much harder to understand by the next person.
He did mention (and I ignored the first code tag thinking it might be a typo), that he was using C. Still, it would be a good reference for the OP on linked list setup and manipulation.
Oct 31 '07 #5

P: 61
He did mention (and I ignored the first code tag thinking it might be a typo), that he was using C. Still, it would be a good reference for the OP on linked list setup and manipulation.

Yes I am using C not C++.

So if there is no built in function or libary i can use to order linked list? Just have to do it manually?
Oct 31 '07 #6

sicarie
Expert Mod 2.5K+
P: 4,677
If you're in the US, remember those commercials from yesteryear - "Behold, the power of cheese."? Same concept, different product.

Behold the power of Google.

Also, as I mentioned, you can look at the implementation of the STL as a reference.
Oct 31 '07 #7

Post your reply

Sign in to post your reply or Sign up for a free account.