#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Posts
    9
    Rep Power
    0

    Question Help needed on Concept of Linked List


    after reading data (of strings and then separate into words) from a file, create a linked list by accepting that initial input. How to build a linked list?? I try to draw a graphical chart, but always get confuse on the part where i should move and put the new input data....

    union salary
    { float fsalary; int isalary; };
    struct emp
    { char lname[20], fname[20], mid_init, title[20];
    int emp_id; union salary pay;};
    struct nodelink
    { struct emp employee; struct nodelink *next;};

    int main(int argc, char *argv[])
    {
    struct nodelink *list, *first, *curr, *last;
    /* data is input and save to list */
    /* list sort alphabetically */


    -- i understand i need to compare the name to sort it, however i don't understand how to move around the list without loosing any data and could save it to a output file at the same time
    (like i have element in "first" (A), element in "curr" (G), element in "last" (W); if the new input of "list" is (B), how can i just add it in between "first" and "curr"? do i need to create a forth pointer?
    please help!! THANK YOU *(^_^!)*
  2. #2
  3. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    ..some of what ur saying is confusing me, but i think what u want to know is how to insert an element into a linked list. you need 2 pointers to do this. one pointer must always stay one node behind the other. you would step thru the list incrementing the frontmost pointer first, that pointer is the one that u use to find the node in front of the node you want to insert. once u find that node, the second pointer should be one node behind that one. then u take the new node u r inserting, and set its next pointer to the first pointer, then u take the pointer behind that one and point it's next pointer at ur new node. kind of confusing in words, but with pictures it/s much easier, try to draw it out if this confuses u.
  4. #3
  5. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,255
    Rep Power
    2222
    Just jumping in, since I read your question a bit differently.

    I assume that the four pointers are:
    list -- pointer to the new node to be inserted
    first -- pointer to the first node, the "head"
    last -- pointer to the last node, the "tail"
    curr -- pointer to the current node; used to move through the list.

    first and last should only change when you insert a new node onto the front or the end of the list, respectively.

    list will be different each time you have a new node to be inserted into the list. The value of list will be set by the malloc (or new if in C++) call when you dynamically allocate memory for the new node.

    curr will change as you move through the list. To step to the next node (which I read as being your first question):
    Code:
    if (curr->next != NULL)
        curr = curr->next;
    else
        // you are at the end of the list; take whatever action you need to in this case
    You can also read any data field that is in the next node. For example, to compare the lname fields of the current and the next nodes:
    Code:
    iResult = strcmp(curr->employee.lname,curr->next->employee.lname);
    That is to say, you can use your next pointer to view the next node, its next pointer to view the node after that, etc for as far as you want to chain the next pointers. Normally, you would only want to look ahead one node and on rare occasion two nodes.

    Whenever you insert or remove a node, you need to make sure that you are pointing to all three nodes involved for almost the entire operation and that you do not lose any of their next values. You should draw a diagram to visualize each of the steps. For example, if you have node C that needs to be inserted between nodes A and B (B follows A and is pointed to by A->next):
    1. have curr pointing to node A.
    2. list->next = curr->next; Now C is pointing to B at the same time that A is pointing to B.
    3. curr->next = list; Now A is pointing to C. Node C has been inserted. Mission completed.

    If you are removing a node, then you reverse the process. For example, given nodes A, B and C in that sequence (ie, A -> B -> C), to remove node B:
    1. have curr pointing to node A (ie, to the node preceding the one we want to remove).
    2. list = A->next; Very Important! We need to keep a pointer pointing to B so that we can free up that memory. Otherwise, you will have a memory leak, an insidious bug that grows until it crashes your computer.
    3. A->next = A->next->next; // link A to C
    or
    A->next = list->next; // same thing, but perhaps easier to visualize.
    Just before we run this step, A is still pointing to B. As soon as we complete this step, A is pointing to C; B has been removed from the list.
    4. free(list); // or delete list; if using C++
    This frees up the memory that had been allocated to that node.

    Warning! The head and tail of the list are special cases that you must handle very carefully. For example, adding to or removing from the head of the list does not involve the curr pointer, but rather the first pointer.

    Also, how do you handle inserting the first node? Or the second one? These are also special cases that you will need to test for and handle. Again, draw diagrams of it to visualize where you need curr (or first) to be pointing and which pointers you need to update and in what order. You should probably handle the special cases with their own code blocks instead of trying to incorporate them in the general-case handlers; eg:
    Code:
    // in pseudo-code
    if (first = NULL) // list is empty
    {
    // handle inserting the first node
    }
    else if (new node to be inserted at head of list)
    {
    // handle this special case
    }
    else (if first->next == NULL) // you already know it needs to be inserted after the first node
    {
    // handle this special case
    }
    else  // the general case
    {
    }
    That's very rough, so feel free to adjust it as needed.

    Be methodical about it and think it through step-by-step, because the least mistake could mess the list up completely.
    Last edited by dwise1_aol; April 18th, 2003 at 03:36 PM.
  6. #4
  7. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Posts
    9
    Rep Power
    0

    Question Help on printing the linked list


    now i am able to read data from file (also split it into words, save it to a new node), but now, when i tries to print it (w/o the while loop in display), it prints some junk at the end of print out... (using C only)
    (output after reading the last person data)>>
    S

    S
    0

    0.00
    -- what is wrong?? also, when i try to get data from the whole file until the EOF (below), and tries to print it... becomes infinite output! what i want to print is like the updated list after each new data....

    (partial) code:
    while(!feof(fpin))
    { /*code for reading file data.... */
    addlist(head, list);} /*while loop in main */

    void addlist(struct nodelink *head, struct nodelink *new)
    {if(head==NULL)
    { head=new;
    curr=new;
    prev=curr;
    curr->next=NULL;} /*if: put the node in the beginning*/
    if(strcmp(curr->employee.lname, new->employee.lname)>0)
    { curr=head;
    head=new;
    head->next=curr;} /*if: put the node in the head */
    else
    {while((curr->next!=NULL)&&
    (strcmp(curr->employee.lname, new->employee.lname)<0))
    { prev=curr;
    curr=curr->next;
    }/* while: switching node until condition meet*/
    if(strcmp(curr->employee.lname, new->employee.lname)>0)
    { new->next=curr;
    curr=new;
    prev->next=curr;
    } /* if: put the list in middle after comparing */
    else
    { new->next=NULL;
    curr->next=new;
    } /* insert the node at the end */
    }
    display(head);} /* end of addlist function */

    void display(struct nodelink *head)
    {while(head)
    { printf("%s\n", head->employee.lname);
    /*printing code */
    head=head->next;}} /* end of display function */

    -- i tried many times, still couldn't figure out where is the "infinite" part.... and did i do the linked list code right?? thanks for help'n~ (^_^!)
  8. #5
  9. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,255
    Rep Power
    2222
    I'm needing to leave shortly, so I haven't had time to go through the code rigorously. I did notice a few things, though.

    You've changed some of the pointer names, so I'm not sure just what you're doing here. It looks like you changed first to head. Is that correct?

    You might want to use a different argument name in the addlist function to make sure you keep them straight. Or else return to using first to always point to the start of the list. It looks to me like head might be getting changed too easily.

    Also, if you want the head pointer being passed in to the addlist to be changed and to keep its change outside of the function, then you will need to pass in a pointer to a pointer (struct nodelink **head) and dereference it when you use it within the function ( *head = new; )

    For the condition of (head == NULL), inserting the first node, once you've taken care of it you should exit (or do your call to display).

    There are two things that I can think of that would cause disply to get caught in an infinite loop:
    1) For some reason the last node does not have NULL in its next field, so it just keeps on going. That could explain getting garbage values, but it should also generate a segmentation fault. Eventually, one of those garbage next values should send you careening out of your own memory space.
    2) One of the next pointers could be pointing back to a previous node. That would trap you in an infinite loop for sure, but the values you print out should be righteous -- unless there's a problem in stuffing the data fields.

    Here's a thought. In display, print out the value of next. %p formats a pointer value:
    printf("%s, %p\n",head->employee.lname,head->next);

    Hope some of that helps.
  10. #6
  11. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Posts
    9
    Rep Power
    0

    Furthermore (^_^!)....


    yes it helps...
    now if i have a sorted linked list in alphab. order of last name, if i want to sort it in ascend order of employee id, or salary with both int and float type, how should i do that? the problem is that when i try to sort it, i will keep loosing my "head" (not me, the ptr head ^_^") and got infinite loop or seg.fault.... i don't know how am i suppose to compare.....
    thx for helping...~
  12. #7
  13. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    well, it depends on what sorting algorithm u will use, but lets say u want to use bubble sort. bubble sort starts at teh top of the list, and compares adjacent values, if the value on the left is larger, it is swapped with the right value. so it would be something like this pseudo(assumes u have the tmp pointers):
    u will need 4 pointers in total, this is because u have to be able to keep track of the 2 nodes being compared + the node behind them + a tmp to do the swap.

    while node next isnt null:

    tmp 1 = head
    tmp 2 = head->next
    tmp 3 = head(this must always stay one behind tmp1, but for this iteration it points at the same thing. next iteration the other 2 pointers move ahead one node, while this one stays 1 behind tmp1.)
    compare teh data in tmp1 and tmp2
    if tmp1 larger, swap(dont forget u need anohter pointer to swap so u dont "lose" the handle to a node)
    tmp1 = tmp2
    tmp2 = tmp2->next
    Loop

    the swap function:

    this is the hard part, and probly where ur messing up. i remember learning this and it was quite mind boggling. the best solution is to draw pictures, i cant stress how important it is to be able to visualize this concept. i wish i could draw for u, but i will try my best 2 explain:

    Lets say u have 4 nodes, i will refer to them as n1,n2,n3,n4. they are in sequential order. lets say u r currently comparing n2 and n3. u must have a pointer for not only n2 and n3, but also n1, this is b/c if u do swap n2 and n3, u will have to reassign what n1 points to, yes? and there is no way to back step to n1(unless u have a different kind of list), so we need to always have 3 pointers all one after the other. so at this point, u have 3 tmp pointers, call them t1, t2, t3, pointing at n1, n2, and n3 respectively. u compare n2 and n3, and indeed they have to be switched b/c n2 is larger. now u must create ANOTHER tmp pointer, call it t4.
    here is where it gets tricky:

    we point t4 at t2(pointer to 2nd node), now he have a handle on t2(second node), so we take t1(which was pointing at n1) and point it's nextPtr(the n1->next) at t3(n3). we then point t4->next (which is pointing to t2) at t3->next(the final node in list). now we point t3->next(n3 ptr) at t4(n2)! and done!

    hope that helps, im not the best teacher, but i tried. my advice if u dont get it, is draw a simple diagram with 4 boxes representing the 4 nodes. and logically think about how u would do this, always keeping in mind that a node always needs to have something pointing to it.
    Last edited by infamous41md; April 22nd, 2003 at 12:43 AM.
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2002
    Posts
    272
    Rep Power
    19
    I think you are over-complicating things a bit. You really only need two temp pointers to do the swap. You need t1 to point to n1 when you start and then do the following:
    Code:
    t2 = t1->next;              // t2 points to n2
    t1->next = t2->next;        // n1 points to n3
    t2->next = t2->next->next;  // n2 points to n4
    t1->next->next = t2;        // n3 points to n2
  16. #9
  17. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    ^^ learn something every day! wow that's much simpler:)

    edit: but would that work when u were comparing nodes further down in the list?...hmm wait i think it would, but u would have to compare data in this manner:

    t1->next->data compared to t2->next->data , correct? b/c u couldnt compare the 2 nodes being pointed to by the temp pointers right, b/c u need to have access to the node behind teh leftmost one being compared?
    Last edited by infamous41md; April 22nd, 2003 at 12:51 PM.
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2002
    Posts
    272
    Rep Power
    19
    Technically, you can compare any two nodes in the list using just the head pointer, e.g. t1->next->next->data == t1->next->next->next->data. In practice, you will probably have a pointer that you are using to traverse the list so you would do most of your comparisons like this, t1->next->data == t1->next->next->data. At that point, you just need one more temp pointer, t2, to do the swap. To do it without so many ->next references, you can use a third pointer that trails behind so that you can get to the one right before the nodes you want to swap. Most of my usage of linked lists involves 2-way or 4-way links so I don't often run into these issues.
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2002
    Location
    Flint, MI
    Posts
    328
    Rep Power
    13
    I'm noticing that you're talking about sorting a linked list after it's been built. The insertions and deletes necessary for sorting a linked list are very expensive.

    You're better off sorting the list from the beggining. If you insert each new node at it's sorted position, generating a sorted list is comparatively inexpensive.

    I'm seeing one gigantic loop for list creation and data reading and everything. I think that a few simpler functions might be better. Try a header file that looks like this:
    Code:
    #ifndef _LLIST_H_
    #define _LLIST_H_
    
    struct employee {
      /* Do your own thing here */
      struct employee* next;
    };
    
    extern struct employee* TOP;
    
    void employee_insert(struct employee*);
    struct employee* employee_read(char*);
    struct employee* employee_create();
    void employee_destroy(struct employee*);
    
    #endif
    The employee_create() function is important. It will allocate memory for a new employee record and do some of the initialization work for you (e.g. point next to NULL).

    The employee_read function takes a line of input, breaks out the components, and inserts it into a freshly created employee record.

    The empoyee_delete function deallocates any memory associated with an employee record. This is important for larger programs that will be sticking around for a while, but probably doesn't deal with your current problems.

    The employee_insert function does the work of building a linked list. If all of the initialization work has been previously handled, then things get pretty easy.
    Code:
    void employee_insert(struct employee* emp) {
      struct employee* cur;
      struct employee* tail = NULL;
    
      if (TOP == NULL) {
        TOP = emp;
        return;
      }
    
      cur = TOP;
      while(cur) {
        /* This assumes an overloaded operator.  you'll probably have to use a comparison function. */
        if (*emp < *cur) {
          tail->next = emp;
          emp->next = cur;
          return;
        }
        tail = cur;
        cur = cur->next;
      }
    
      /* Our item belongs on the end of the list */
      cur->next = emp;
    
    }
    Clay Dowling
    Lazarus Notes
    Articles and commentary on web development
    http://www.lazarusid.com/notes/

IMN logo majestic logo threadwatch logo seochat tools logo