implementing multi linked list correctly_?

Stefan_Lang

Are you using C or C++? If the latter, simply use two std::map<const char*, Node*>s as a means to directly access a node by first name and last name respectively. std::map does the sorting for you, and you can just add all new nodes to the head instead of scanning the list. You also won't need to copy the add function for every new 'index' you want your list sorted by. If you do C only, you still should try to separate the task of storing a list from the task of sorting a list, so you wouldn't need one set of list functions such as adding/removing for every new sorting criterion you want to introduce.

quartaela

i am using C :) i am just only wondering about am i using only one list which have two headers or two lists which the first one is the copy of the other_? and i am adding a node in ascending order(i am using double pointer for print them in descending order )

Stefan_Lang

Ah, that makes things difficult for me, as I'm not quite sure what is and is not quite possible C. I'd say use three lists: one just for storing the nodes in an arbitrary order, and two to store your individual sortings, with nodes that only store the key you are using, plus a pointer to the appropriate node in your first list. In the case you describe you can define the node like this:

struct keynode {
const char* key;
struct NODE* node;
}

A more general version that could be used for other types of keys could be:

enum EKeytype { SKEY, IKEY, FKEY /*etc.*/ };
struct keynode {
EKeytype keytype;
union {
const char* skey;
int ikey;
float fkey;
// etc. ...
} key;
struct NODE* node;
}

In this case you need to check for the keytype to properly compare and sort the keys. The disadvantage of using multiple lists is that youneed to add/remove multiple nodes. The advantage is that you can easily add more sorting criterias. And the code becomes cleaner, because you can seperate the storing from the sorting.

quartaela

well this is my structures;

typedef struct node {

int count;
int birth\_date;
int zipcode;
int phone\_num;
char first\_name\[50\];
char last\_name\[50\];
char city\[50\];
char address\[50\];
char email\_addr\[50\];

struct node\* fn\_next;
struct node\* fn\_pre;
struct node\* ln\_next;
struct node\* ln\_pre;
struct node\* birdat\_next;
struct node\* birdat\_pre;

} NODE;

typedef struct {

int fn\_count;
int ln\_count;

NODE\* fn\_head;
NODE\* ln\_head;

NODE\* fn\_tail;
NODE\* ln\_tail;

}LIST;

and i am checked with printing the nodes by ascending and descending order wtih this code;

void print_fn_list(LIST* list) {

NODE\* temp = list->fn\_head;
NODE\* reverse = list->fn\_tail;

if( temp == NULL || reverse == NULL ) {

	printf("THE LIST IS EMPTY!\\n");
	return;
}

while( temp != NULL ) {

	printf("%s  %10s\\n", temp->first\_name, temp->last\_name);

	temp = temp->fn\_next;

}

printf("-----------------------------------\\n");

    while( reverse != NULL ) {

	printf("%s  %10s\\n", reverse->first\_name, reverse->last\_name);

	reverse = reverse->fn\_pre;

}

temp = list->ln\_head;
reverse = list->ln\_tail;

printf("-----------------------------------\\n");

if( temp == NULL || reverse == NULL ) {

	printf("THE LIST IS EMPTY!\\n");
	return;
}

while( temp != NULL ) {

	printf("%s %10s\\n", temp->last\_name, temp->first\_name);

	temp = temp->ln\_next;

}

printf("-----------------------------------\\n");

    while( reverse != NULL ) {

	printf("%s %10s\\n", reverse->last\_name, reverse->first\_name);

	reverse = reverse->ln\_pre;

}

}

as you can see i use 2 headers (list->ln_head and list->fn_head). i only want know that are these 2 heads are pointing only one list, or each of them are pointing two same list but sorted in diff. ways.

Stefan_Lang

As you use two different add functions for the two sortings, and each creates new nodes, you'll end up with two separate lists. If that was your intention you need only one next and one pre pointer for each list. If that was not your intention, then you need to create the new node outside the add function, and have the add function(s) just update the links appropriately.

quartaela

well i create the node outside of the add functions and pass the node to these functions. in these add functions i update the links. but the main thing is which confuses me i use two add functions.(which updating the pointer of first name and second one is for last name). so if i wanna use only one list with having two different pointers(firstname pointer and lastname pointer) must i use only one add function_? or two functions. because adding one node for two different sortings in just one function will be very difficult_?. and sorry for inconvenience situtaion of my problem : ): here is the code again of my creating and calling add functions;

while ( !feof(myfile) ) {

    NODE\* pnew\_stu;

    if( !(pnew\_stu = (NODE\*) malloc(sizeof(NODE))) ) {

        printf("ERROR NOT ENOUGH MEMORY!!!\\n");
        exit(100);
    }

    fscanf(myfile,"%s", &(pnew\_stu->first\_name) );
    fscanf(myfile,"%s", &(pnew\_stu->last\_name) );
    fscanf(myfile,"%s", &(pnew\_stu->email\_addr) );
    fscanf(myfile,"%d", &(pnew\_stu->phone\_num) );
    fscanf(myfile,"%s", &(pnew\_stu->address) );
    fscanf(myfile,"%s", &(pnew\_stu->city) );
    fscanf(myfile,"%d", &(pnew\_stu->zipcode) );

    add\_fn\_Node(list,pnew\_stu);
    add\_ln\_Node(list,pnew\_stu);

}

and these are the adding functions

void add_fn_Node(LIST* list, NODE* pnew_stu) {

NODE\* temp = list->fn\_head;

if( !(temp = (NODE\*) malloc(sizeof(NODE))) ) {

        printf("ERROR NOT ENOUGH MEMORY!!!\\n");
        exit(100);
    }

if( list->fn\_head == NULL ) {

        pnew\_stu->fn\_next = list->fn\_head;
        pnew\_stu->fn\_pre = list->fn\_head;


        list->fn\_head = pnew\_stu;

        list->fn\_count = 1;

        return;

    }

    else {

        temp = list->fn\_head;

        if ( (strcmp( pnew\_stu->first\_name, temp->first\_name )) <= 0 ) { // Basa Ekleme Kosulu

            pnew\_stu->fn\_next = temp;
            pnew\_stu->fn\_pre = temp->fn\_pre;
            temp->fn\_pre = pnew\_stu;

            list->fn\_head = pnew\_stu;

            list->fn\_count++;

            return;

        }

        else {


             while ( temp->fn\_next != NULL ) { // Ortaya Ekleme Kosulu

                    if ( (strcmp( pnew\_stu->first\_name, temp->firs

Stefan_Lang

quartaela wrote:
NODE\* temp = list->fn\_head;
if( !(temp = (NODE*) malloc(sizeof(NODE))) ) {

printf("ERROR NOT ENOUGH MEMORY!!!\n");
exit(100);
}
if( list->ln_head == NULL ) {
...
}
    else {

        temp = list->ln\_head;

What do you call malloc for here? I mistook this for the code that creates the node, but apparently it's just a mistake. Especially since temp gets overwritten later anyway. So I was mistaken, there is only one list of nodes that you have. list->fn_head and list-> ln_head just point to different positions in your list.

quartaela

so friend i know you will have a headache cause of my questions. :). but i wanna ask a final question. why there aren't any differences between sending the node or its address like this;

add_fn_Node(list,&pnew_stu);
add_ln_Node(list,&pnew_stu);

and replacing every code

pnew_stu->fn_next
pnew_stu->fn_pre

with

(*pnew_stu)->fn_next
(*pnew_stu)->ln_next

and of course sorry that silly mistake of malloc :)

Stefan_Lang

If you want to make these changes, you will also have to change the prototypes of the add_XY_Node() functions so they correctly reflect the type of the second parameter. If you do that, the suggested changes should indeed work: Instead of passing the pointer you pass the address of the variable that stores the pointer, but inside the function you dereference that address again to get the original pointer. I see no reason to do that, unless you want to modify the pointer and pass that modification back to the caller.

quartaela

thanks for your help stefan :)

David Crow

At first glance, this seems to be overly complicated. I looked back through my archives and found some code I did for a doubly-linked list (that simply held an integer). The data structures were:

struct _node
{
int m_nNumber;
struct _node* m_pNext;
struct _node* m_pPrev;
};

struct _list
{
_list( void )
{
head = NULL;
tail = NULL;
}

struct \_node\* head;
struct \_node\* tail;

};

The function signatures were:

void addToFront( struct _list* pList, int nNumber );
void addToBack( struct _list* pList, int nNumber );
void addBefore( struct _list* pList, struct _node* pNode, int nNumber );
void addAfter( struct _list* pList, struct _node* pNode, int nNumber );
void insertAscending( struct _list* pList, int nNumber );
void insertDescending( struct _list* pList, int nNumber );
struct node* findNode( struct _list* pList, int nNumber );

To create a list of ascending integers, I would simply call insertAscending(), which looked like:

void insertAscending( struct _list* pList, int nNumber )
{
struct _node* pTemp = pList->head;

while (pTemp != NULL && nNumber > pTemp->m\_nNumber)
    pTemp = pTemp->m\_pNext;

addBefore(pList, pTemp, nNumber);

}

void addBefore( struct _list* pList, struct _node* pNode, int nNumber )
{
struct _node* pTemp = new struct _node;
pTemp->m_nNumber = nNumber;
pTemp->m_pNext = pNode;

// if the node we're to precede was the head, adjust the head
if (pNode->m\_pPrev == NULL)
    pList->head = pTemp;
else
    pNode->m\_pPrev->m\_pNext = pTemp;

pTemp->m\_pPrev = pNode->m\_pPrev;

pNode->m\_pPrev = pTemp;

}

Breaking your code down into smaller, more manageable pieces will help you a lot.

"One man's wage rise is another man's price increase." - Harold Wilson

"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons

"Some people are making such thorough preparation for rainy days that they aren't enjoying today's sunshine." - William Feather

quartaela

well mate i know my code is a little bit complicated but its reason is i am just in the beginning level of my project. i will make these operations at the end :). anyway thanks for your suggestions :)