Ordering a singly linked list | Member | | Join Date: Sep 2007
Posts: 55
| |
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. -
struct block
-
{
-
struct block *next;
-
int number;
-
};
-
typedef struct block block;
-
|  | Moderator | | Join Date: Nov 2006 Location: USA
Posts: 3,929
| | | re: Ordering a singly linked list
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?
| | Member | | Join Date: Sep 2007
Posts: 55
| | | re: Ordering a singly linked list
Quote:
Originally Posted by sicarie 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.
| | Moderator | | Join Date: Mar 2007 Location: North Bend Washington USA
Posts: 5,375
| | | re: Ordering a singly linked list
Quote:
Originally Posted by Alien 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.
| | Moderator | | Join Date: Nov 2006 Location: USA
Posts: 3,929
| | | re: Ordering a singly linked list
Quote:
Originally Posted by weaknessforcats 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.
| | Member | | Join Date: Sep 2007
Posts: 55
| | | re: Ordering a singly linked list
Quote:
Originally Posted by sicarie 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?
| | Moderator | | Join Date: Nov 2006 Location: USA
Posts: 3,929
| | | re: Ordering a singly linked list
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.
|  |
| | |  /bytes/about
We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights.
Get the best answers to your questions from over 226,471 network members.
|
