Sorting linked lists

[jdm2104]

Hi,

I'm working with linked lists at the moment and was wondering what is the best way of sorting the list.

I would like to sort the nodes as I'm inserting them. For example, if the new node is better than the third node in the list (based on some evaluation) insert it in position three.


I know there is a template class available but I don't want to use it and would like to know how to do this myself.

Thanks

[raj_cg]

The way you want to sort depends on the data that you store in the list. You can store primitive types or objects in the linked list. If you store objects, these objects should support a means to compare one another.

The places where you will have to sort before doing an operation are
insert and delete. Delete operation is no big deal....so incorporate the logic to find the appropriate node to insert data in the insert function.

[sreehari]

Hi,

I'm working with linked lists at the moment and was wondering what is the best way of sorting the list.

I would like to sort the nodes as I'm inserting them. For example, if the new node is better than the third node in the list (based on some evaluation) insert it in position three.

some tips that you can start with ...

The basic linked list can be a structure containing
- a premitive data type ( say int in this case ) that will contain the data that has to be sorted.
- A pointer to a structure. That will point to the next node.

Sorting the linked list in assending order

- store the First data in the first structure and its corresponding pointer to Null
- Wen the user enters a new value check if that valueis greater than or less than the first value....
- If its greater Store this value in a new node ( structure )
- its corresponding pointer to Null
- make the pointer of the last node to point to this structure. or node

- If its lesser than the first value.
store the value in the node. and the pointer to point to the first node

for the third value and remaining values.
the list will now look like

node1->node2->NULL // where -> are the pointers

- keep searchin the list ( for the correct position )
- when positin found . ( say between node one and two. ) ( call the new node as node 3 that has to be inserted between node1 and node2. )
- store the valueof the pointer of node1 in a temp pointer.
- reassign node1 pointer to point to node3.
- assign the value of node3 pointer to the earlier pointer of node1.. ( that is point it to node 2.

now the list will look like
node1->node3->node2->NULL

follow the same procedure

[exterminator]

Any sorting algorithm that will work for an array will work for a linked list as well (preferably doubly linked list - you dont mention which one you are working with). It is a different matter about efficiency. So, if you know how to sort an array of objects you will be able to deduce how to sort a "list" of objects. So, my question is what sorting algorithms are you familiar with and which ones have you implemented yourself or planning to use here?

[jdm2104]

Thank you for the help.

sreehari - I'll work through your suggestions, I think this is what I wanted to do.

exterminator - I've not done much array sorting so I'll look into that. Sorry I forgot to mention I'm working with singly linked lists.

I want to sort my list based on a value stored in each node.

[DragForce]

If I may, I would strongly advise to chose different datastructure. Lists are not suitable for sorting.

[jdm2104]

Could you recommend one based on what I've said so far. I'm interested in learning a more efficient way.

I was storing an array of values in my list.

Thanks

[DragForce]

The selection of the best data structure rather depends on the operations you are going to do with the resulting "list". In fact, all associative containers can do your sorting themselves if you provide them with a comparison function.

[treuss]

Could you recommend one based on what I've said so far. I'm interested in learning a more efficient way.

If I understand you correctly, you want to sort the items, while you insert them. In that case, you should use a tree as your data structure. There are many kinds of trees: binary trees, AVL-trees, B and B*-trees, red-black trees, ... I'm pretty you'll find something via google.
The standard C++ containers std::set and std::map are (most likely) implemented as trees. So there is usually no good reason for implementing a tree, other than learning how to program algorithms.

[jdm2104]

Never heard of trees before! I'll look them up on google, sounds intersting.

thanks