about multi linked list

[quartaela]

hi there i have discussed my problems about multi linked list thread http://www.codeproject.com/Messages/3876300/implementing-multi-linked-list-correctly\_.aspx but i recognize that it coldn't solved. my problem was about implementing a multi linked list which your list implemented by more than one cases. for example by first name or last name. so it have two header and tail pointers. the adding and building the list operations are succesfully working. and there is not a problem when i delete a node by "first_name" and when i search him again, the output is "not found". but when i search him by his "last_name" (so i using header pointer of last name here) the output becomes "person exist". i hope i explain my problem understandable : ). so i appreciated if you can help me. here is my structures

typedef struct node {

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 here is the block i call adding functions for name and surname;

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 of course my add functions;

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

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

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;

        ret

[Luc Pattyn]

I'm sorry to say but the concept has been fundamentally flawed from the start. What you want is something that behaves like a single collection ("persons"), to which you can add and remove; and which you can iterate in a couple of ways (first name A-Z, last name A-Z, first name Z-A, last name Z-A). So you should implement that as a single list, with the one ADD method and the one REMOVE method, not multiples of them. And your ADD, REMOVE and possible other methods should all take care of all the sort orders and links themselves all the time. So ADD should accept one new node and update all relevant link chains; REMOVE likewise. As long as you don't do it that way, it will be open to abuse; as in your user calling add_fn_Node() and not calling add_ln_Node(). BTW: one more piece of advice. Assuming the nodes are small, I very much prefer not to have a LIST structure at all, I just use one more NODE item. That is, my list is a NODE, its next field points to the first node, and the forward link chain ends on the last node, which has a next value of null); likewise my list NODE's prev field points to the last node, and the backward link chain ends on the first node, which has a prev value of null. Doing it that way takes less code, as there are no special cases, a list never being empty! (it always contains itself, the list NODE, which you obviously have to skip when enumerating the real nodes). :)

Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.

[quartaela]

well mate i guess i will do with your suggested way. one ADD and Remove function. hope i can do it in time. and for your last suggestion it is perfect!! but i have corner cases. :)

[barneyman]

i agree with Luc i'd do it the following way to get it done quickly 1. Maintain a naturally ordered list of all the items 2. Have an ordered list each for surname and firstname; these lists simply reference the index into the ordered list Adding is cheap, iterating is cheap, finding is cheap (b-chop), removal is 'difficult' Add - add item to back of natural order list, qsort the item index into each of the ordered lists Remove - find the item in either sorted list, mark the item in the ordered list as dead - you can't delete it or you'll ruin the indices ie Natural Order (includes ALL item data) Sarah Connor Jack Black Pete Jones Stan Smith Surname Order (just index into Natural Order) 1 0 2 3 Firstname Order (just index into Natural Order) 2 1 0 3

[quartaela]

i don't understand the operation you said "mark the item in the ordered list as dead - you can't delete it or you'll ruin the indices". how can i do this_?. i am using free(nameofptr) function to delete the node_?.

[barneyman]

Missed a step in removal - sorry You can remove references in the ordered lists, but you can't remove the real record in the natural list Have a bool in the struct that signifies if it's a dead record, don't bother free'ing it until the end of the application - unless you're turning records over dramatically, that will be ok