Thread: Multiple Linked Lists w/HeadNode

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    13

    Question Multiple Linked Lists w/HeadNode

    Here is what I want to do:
    1. Create a linked list
    2. Create a linked list from those deleted in (1)
    3. Create a linked list from those deleted in (2)
    Total of 3 singly-linked lists.

    1-3 have a HeadNode. I have #1 finished. To create a linked list from those deleted in the first linked list, should I use the same HeadNode - use the same structure? Or is it better to create a new HeadNode for linked list #2? If I create a new HeadNode, then I would have to create a new NodePointer.

    I know I'll probably have to alter the generic Delete() node to get those that are deleted to 'go into' the second linked list. - I'm not sure how to do this yet.

    Any ideas on how to approach this? Or if I'm thinking the wrong way?

    Any help greatly appreciated! Little code snippets would be helpful too!
    Last edited by tofugirl; 12-05-2005 at 06:00 PM.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Post your current code. (Especially Delete().)
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    13
    Post your current code. (Especially Delete().)
    That would be too much code. It's your regular generic code of a singly-linked list.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Don't have a 'delete' function. Have a 'remove' function, that removes a node from a list and returns a pointer to it. That way you can do:
    Code:
    ptr = remove( somelist, somevalue );
    add( someotherlist, ptr );
    Really though, if your 'delete' function is "too much code", then you're doing something really really wrong.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    Quote Originally Posted by quzah
    Don't have a 'delete' function. Have a 'remove' function, that removes a node from a list and returns a pointer to it. That way you can do:
    Code:
    ptr = remove( somelist, somevalue );
    add( someotherlist, ptr );
    Really though, if your 'delete' function is "too much code", then you're doing something really really wrong.


    Quzah.
    It's generally not a good idea to name your functions the same as ones defined by ANSI C.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I like to keep things interesting.


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    well, normally if u want to deleten a node what will u do

    1. search for the particular node which u want to delete
    2. on node found u will make the link changes like the following node address is given prev node next.
    3. and u will free the node which u want to delete

    for u'r case dont free that node try to use that node to create one more linked list .

    u will have to use one more headpointer but use the same structure. if u use the same headpointer u will lose old list

    hopefully u might have got an idea

    ssharish2005

  8. #8
    Registered User
    Join Date
    Nov 2005
    Posts
    13

    Arrow reply to quzah

    Code:
    ptr = remove( somelist, somevalue );
    add( someotherlist, ptr1 );
    I'm guessing your add is same as an
    Code:
    insert(someotherlist, ptr1);
    ?

    I was thinking along the terms of ssharish2005's reply. What do the rest of you think?

    Dammit.. I need 3 headpointers... la la la

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well you do need three head pointers if you're creating three seperate lists. So I'm not really sure why you're having problems.
    Code:
    struct node *list1, *list2, *list3, *temp;
    ... do fun stuff ...
    
    temp = extractnode( &list1, somevalue ) /* Pull some node from list1. */
    if( temp )
    {
        addnode( &list2, temp ); /* Put this node on/in list2. */
    }
    temp = extractnode( &list2, someothervalue ); /* Pull some node from list2. */
    if( temp )
    {
        addnode( &list3, temp ); /* Put this node on/in list3. */
    }
    
    freelist( list1 );
    freelist( list2 );
    freelist( list 3 );
    Now all you have to do is write the appropriate functions.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User
    Join Date
    Nov 2005
    Posts
    13
    Well you do need three head pointers if you're creating three seperate lists.
    Since I need 3 head pointers, I need 3 nodes with data & next... hmm.. I get it. Because I'm going to loose everything if I use the same nodes & headnodes.. dammit! Thanks for the mini code quzah.

    must get back to work and my Viennese Chocolate Cafe..... will be back later if i get stuck.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You're not going to lose anything. Simply remove one node from a list, and return a pointer to it. All you're doing it moving pointers around so nothing points to it. Here, let me illustrate:
    Code:
    node1   <-- top of list 1
      |
    node2   <-- Node we want to remove
      |
    node3   <-- top of the rest of this list
      |
     ...
    Given the above, this is how you remove node2, and keep the rest of the list:
    Code:
    temp = node2; <-- get something to keep track of the node we're removing
    node1->next = temp->next; <-- make the node before it, point to the node after it
    temp->next = NULL; <-- fix the node we're removing so it doesn't point to anything
    return temp; <-- return it so we can still use it
    This now gives you the node you've just removed. You haven't deleted it, it's just not in the list. Do this:

    Put three cards or pieces of paper in a stack on your desk. Remove the middle piece and hold it in your hand. There. You have done what I have just illustrated. The next piece from the top piece is now the "third" piece. You still have a handle on the middle piece, which you've removed, so you can still do something with it. Such as, putting it on another pile.

    Now just pretend you have three seperate piles of paper...

    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User
    Join Date
    Nov 2005
    Posts
    13
    Code:
    temp = node2; <-- get something to keep track of the node we're removing
    node1->next = temp->next; <-- make the node before it, point to the node after it
    temp->next = NULL; <-- fix the node we're removing so it doesn't point to anything
    return temp; <-- return it so we can still use it
    How can I get list #2 to point to temp?

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I showed you how two posts prior to this.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Multiple linked lists
    By JFonseka in forum C Programming
    Replies: 8
    Last Post: 04-19-2008, 06:49 AM
  2. multiple linked lists
    By killer in forum C++ Programming
    Replies: 8
    Last Post: 07-06-2006, 01:02 AM
  3. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  4. Can multiple linked lists share the same structure?
    By passy in forum C Programming
    Replies: 10
    Last Post: 08-28-2003, 04:38 PM
  5. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM