help with linked lists

[Unregistered]

Ive just began learning about linked lists, and am trying to make a rolodex that holds names, addreses, and phone numbers, all via linked lists. I am in need of any hints anyone could give me on how to enter these items into the rolodex, sort them alphabetically by last name, and then write the rolodex to a file. So far I am clueless, so any hints at all would be greatly appreciated. Thank you.

[Unregistered]

If you add items to the list so that the list always stays in alphabetical order according to last name, you won't need a separate sort function. In other words, when you add an item to the list, traverse the list, testing for the proper spot to make the insertion. You can use strcmp.

[stautze]

The most efficient way I can think of would be to use priority queue implemented by a heap. Heaps are really only suited for contiguous list though.

If you are stuck on the linked list, then you could easily use a binary tree which is easily sorted and is easily traversed many different ways.

[BlackCitan]

We have to create a linked list recursively, and I'm trying to find a way to compare a new node with the prior one and change the pointers around so that if the prior node is greater, the new node will point to the previous and the previous will point to the new. My program either (a) enters a never-ending loop or (b) does absolutely nothing with respect to key order. (The key is int, BTW.) I want it to keep going like that until all the data are read. I've nearly thrown my comp out the window trying to do it with a separate sorting function If anyone has experienced this problem or knows a good way to fix it, any help would be greatly appreciated.

[quzah]

Use a double linked list. These are infinitely easier to work with than single linked lists.

struct node
{
    struct node *prev, *next;
    ...other data here...
};

Make one node which is your root node. I always use a global (most always anyway) simply because it is so much easier to work with this way.

From there:

if( node->prev->key > node->key )
{
    node->prev->next = node->next;
    node->next = node->prev;
    if( node->prev->prev )
    {
        node->prev->prev->next = node;
        node->prev = node->prev->prev;
    }
}

It may be complicated looking, but draw it out on paper, it's very simple.

[n1]<->[n2]<->[n3]<->[n4]

That is how a double linked list works.

Quzah.

[BlackCitan]

Well, extra credit on this project is to create a doubly-linked list and traverse backwards, but I have that later on. Lemme make it doubly-linked when the list is built and see if I can figure it out from there. Thanks!

[Bull]

use the search function to find other posts on linked lists, theres been so many of them it isnt even funny, heres one which includes sorting algorithums, etc.
http://www.cprogramming.com/cboard/s...ht=linked+list

[BlackCitan]

So my teacher emails me back tonight after about 12 hours of working on sorting this linked list, and she tells me: just make sure your input data are in order already. Your program doesn't have to sort them. LoLoL I'm sorry everyone. Thanks for all the help; next time I PROMISE to try searching first.