Linked list within a linked list

Discussion in 'C++' started by joshd, Sep 30, 2006.

  1. joshd

    joshd Guest

    Hello,

    Im sorry if this question has been asked before, but I did search
    before posting and couldnt find an answer to my problem. I have two
    classes each with corresponding linked lists, list1 and list2, each
    node within list1 has various data and needs to have a pointer to the
    corresponding node in list2, but I cant figure out how to do this.

    Could someone explain what I might be missing, or maybe point me in the
    direction of a good article which would help me out? Because for
    something that should be so simple, it's really got me stumped.

    Thanks,
    Josh
     
    joshd, Sep 30, 2006
    #1
    1. Advertising

  2. joshd

    John Carson Guest

    "joshd" <> wrote in message
    news:
    > Hello,
    >
    > Im sorry if this question has been asked before, but I did search
    > before posting and couldnt find an answer to my problem. I have two
    > classes each with corresponding linked lists, list1 and list2, each
    > node within list1 has various data and needs to have a pointer to the
    > corresponding node in list2, but I cant figure out how to do this.
    >
    > Could someone explain what I might be missing, or maybe point me in
    > the direction of a good article which would help me out? Because for
    > something that should be so simple, it's really got me stumped.


    I don't see how this question relates to the title of your post. There is
    nothing in your description to suggest a linked list within a linked list.

    More generally, stating the problem clearly would help. Is this a one-off
    synchronisation of the lists or does it have to be done repeatedly as the
    lists are added to? If so, how are the lists added to? Are the two classes
    friends of each other? Is the "corresponding node" the node that occurs in
    the same position in the list?

    Assuming the answer to the last question is yes, for a one-off
    synchronisation, you can do it by iterating over both lists. The address of
    a list item is given by

    &(*iter)

    where iter is the iterator. Iterating over both lists simultaneously means
    you can retrieve the addresses of corresponding items at the same time and
    then store a pointer in each. Obviously the T1 in

    list<T1> list1;

    will need to have a member variable that is a pointer to the T2 type in

    list<T2> list2;

    and vice versa.

    If you want synchronisation on the run, then you will need to add to both
    lists at the same time (or else do a search over each list to find the nodes
    that are "corresponding"). If you add to the end of both lists, then you can
    get the address from

    &(*list1.end()) and &(*list2.end())

    after you have made the addition. Adding at the beginning is analogous.

    If you add in the middle using insert to add a single element, then insert
    returns an iterator pointing to the new element. You retrieve a pointer from
    this iterator following the same pattern as illustrated above.

    --
    John Carson
     
    John Carson, Sep 30, 2006
    #2
    1. Advertising

  3. joshd wrote:
    > Hello,
    >
    > Im sorry if this question has been asked before, but I did search
    > before posting and couldnt find an answer to my problem. I have two
    > classes each with corresponding linked lists, list1 and list2, each
    > node within list1 has various data and needs to have a pointer to the
    > corresponding node in list2, but I cant figure out how to do this.
    >
    > Could someone explain what I might be missing, or maybe point me in the
    > direction of a good article which would help me out? Because for
    > something that should be so simple, it's really got me stumped.


    This is just a proof of concept, i.e. how to do it using std::list.
    These are using iterators to point to one another.

    #include <list>

    // declare 2 structs
    struct A;
    struct B;

    // define the respective list type
    typedef std::list<A> Alist_t;
    typedef std::list<B> Blist_t;

    // define the classes
    struct A
    {
    Blist_t::iterator bitr;

    A( const A & ) {} // no copying bitr
    A() {}
    };

    struct B
    {
    Alist_t::iterator aitr;
    B( const B & ) {} // no copying aitr !
    B() {}
    };

    // some silly example code
    void tst()
    {
    Alist_t al;
    Blist_t bl;

    // make an A element
    al.push_front( A() );

    // make a B element
    bl.push_front( B() );

    // Set up iterators to point to each other
    al.front().bitr = bl.begin();
    bl.front().aitr = al.begin();

    }

    int main()
    {
    tst();
    }
     
    Gianni Mariani, Sep 30, 2006
    #3
  4. joshd

    joshd Guest

    I apologize that I wasnt too clear with my first post, Im still trying
    to grasp the linked list concept. Maybe this visual representation I
    jotted out, with a parent-child scenario, will help you understand my
    needs.

    parent linklist
    |
    parent node -> child linklist + child2 list + child3 list + ....
    parent node -> child linklist + child2 list + ....
    parent node -> child linklist + child2 list + ....

    Can this be done without iterators? or should I study more to wrap my
    mind around STL and iterators?

    Thanks for all your help!

    Josh
     
    joshd, Sep 30, 2006
    #4
  5. joshd

    Kai-Uwe Bux Guest

    Gianni Mariani wrote:

    > joshd wrote:
    >> Hello,
    >>
    >> Im sorry if this question has been asked before, but I did search
    >> before posting and couldnt find an answer to my problem. I have two
    >> classes each with corresponding linked lists, list1 and list2, each
    >> node within list1 has various data and needs to have a pointer to the
    >> corresponding node in list2, but I cant figure out how to do this.
    >>
    >> Could someone explain what I might be missing, or maybe point me in the
    >> direction of a good article which would help me out? Because for
    >> something that should be so simple, it's really got me stumped.

    >
    > This is just a proof of concept, i.e. how to do it using std::list.
    > These are using iterators to point to one another.
    >
    > #include <list>
    >
    > // declare 2 structs
    > struct A;
    > struct B;
    >
    > // define the respective list type
    > typedef std::list<A> Alist_t;
    > typedef std::list<B> Blist_t;



    Formally, this is undefined behavior because A and B are incomplete types
    (see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and stdlibc++
    when g++ is compiled with --enable-concept-check.


    > // define the classes
    > struct A
    > {
    > Blist_t::iterator bitr;
    >
    > A( const A & ) {} // no copying bitr
    > A() {}
    > };
    >
    > struct B
    > {
    > Alist_t::iterator aitr;
    > B( const B & ) {} // no copying aitr !
    > B() {}
    > };
    >
    > // some silly example code
    > void tst()
    > {
    > Alist_t al;
    > Blist_t bl;
    >
    > // make an A element
    > al.push_front( A() );
    >
    > // make a B element
    > bl.push_front( B() );
    >
    > // Set up iterators to point to each other
    > al.front().bitr = bl.begin();
    > bl.front().aitr = al.begin();
    >
    > }
    >
    > int main()
    > {
    > tst();
    > }



    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Oct 1, 2006
    #5
  6. joshd

    John Carson Guest

    "joshd" <> wrote in message
    news:
    > I apologize that I wasnt too clear with my first post, Im still trying
    > to grasp the linked list concept. Maybe this visual representation I
    > jotted out, with a parent-child scenario, will help you understand my
    > needs.
    >
    > parent linklist
    > |
    > parent node -> child linklist + child2 list + child3 list + ....
    > parent node -> child linklist + child2 list + ....
    > parent node -> child linklist + child2 list + ....


    Still not clear. You have used three symbols, | -> and +. I think I have got
    the first two, but what does + denote? And what does the switch from
    "linklist" to "list" signify?

    Is it simply that you have a parent linked list and that each node in the
    parent linked list contains a linked list?

    > Can this be done without iterators? or should I study more to wrap my
    > mind around STL and iterators?


    If you are writing your own linked list, then you can avoid iterators. If
    you are using the standard library linked list, then iterators are
    fundamental. Writing your own linked list can be a useful learning exercise,
    but using the standard library containers is almost always preferable for
    any program that isn't a learning exercise. You should definitely learn the
    standard library containers, along with iterators.

    --
    John Carson
     
    John Carson, Oct 1, 2006
    #6
  7. Kai-Uwe Bux wrote:
    ....
    >
    > Formally, this is undefined behavior because A and B are incomplete types
    > (see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and stdlibc++
    > when g++ is compiled with --enable-concept-check.


    Ah - well, this makes lists much stl containers much less
    interesting...sigh.

    I'd better go back and finish up the Austria containers then.

    Just as a matter of interest, do you know why does the standard need this ?

    BTW - the version of the gcc compiler I have does not support
    --enable-concept-check.
     
    Gianni Mariani, Oct 1, 2006
    #7
  8. Kai-Uwe Bux wrote:
    ....
    >
    > Formally, this is undefined behavior because A and B are incomplete types
    > (see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and stdlibc++
    > when g++ is compiled with --enable-concept-check.
    >



    OK - this should conform now.

    #include <list>

    template <typename T>
    struct Foo
    {
    // declare 2 structs
    struct A;
    struct B;

    // define the respective list type
    typedef std::list<A> Alist_t;
    typedef std::list<B> Blist_t;

    // define the classes
    struct A
    {
    typename Blist_t::iterator bitr;

    A( const A & ) {} // no copying bitr
    A() {}
    };

    struct B
    {
    typename Alist_t::iterator aitr;
    B( const B & ) {} // no copying aitr !
    B() {}
    };
    };

    typedef Foo<int> X;

    // some silly example code
    void tst()
    {
    X::Alist_t al;
    X::Blist_t bl;

    // make an A element
    al.push_front( X::A() );

    // make a B element
    bl.push_front( X::B() );

    // Set up iterators to point to each other
    al.front().bitr = bl.begin();
    bl.front().aitr = al.begin();

    }

    int main()
    {
    tst();
    }
     
    Gianni Mariani, Oct 1, 2006
    #8
  9. joshd

    Kai-Uwe Bux Guest

    Gianni Mariani wrote:

    > Kai-Uwe Bux wrote:
    > ...
    >>
    >> Formally, this is undefined behavior because A and B are incomplete types
    >> (see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and
    >> stdlibc++ when g++ is compiled with --enable-concept-check.

    >
    > Ah - well, this makes lists much stl containers much less
    > interesting...sigh.


    Yeah, it's a real bummer. I once had a nice caching container (generically
    implementing a last recently used drop policy) but it suffers from this
    flaw.

    > I'd better go back and finish up the Austria containers then.


    Huh?


    > Just as a matter of interest, do you know why does the standard need this?


    It does not: most implementation will work just fine and implementors have
    to put in extra code to make it fail :)

    However, the standard just takes the easy wording option: since templates
    like pair need complete types, the standard just put a general requirement.
    Also, at the time they were just careful: you can always lift requirements
    in future version of the standard, but you cannot tighten them. Probably, a
    proposal to replace the general requirement by more finetuned ones could
    pass.


    > BTW - the version of the gcc compiler I have does not support
    > --enable-concept-check.


    --enable-concept-check is a built option, you have to pass it to the
    configure script before you build g++ from the source.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Oct 1, 2006
    #9
  10. joshd

    Kai-Uwe Bux Guest

    Gianni Mariani wrote:

    > Kai-Uwe Bux wrote:
    > ...
    >>
    >> Formally, this is undefined behavior because A and B are incomplete types
    >> (see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and
    >> stdlibc++ when g++ is compiled with --enable-concept-check.
    >>

    >
    >
    > OK - this should conform now.
    >
    > #include <list>
    >
    > template <typename T>
    > struct Foo
    > {
    > // declare 2 structs
    > struct A;
    > struct B;
    >
    > // define the respective list type
    > typedef std::list<A> Alist_t;
    > typedef std::list<B> Blist_t;


    Still incomplete types.

    > // define the classes
    > struct A
    > {
    > typename Blist_t::iterator bitr; // line 17
    >
    > A( const A & ) {} // no copying bitr
    > A() {}
    > };
    >
    > struct B
    > {
    > typename Alist_t::iterator aitr; // line 25
    > B( const B & ) {} // no copying aitr !
    > B() {}
    > };
    > };
    >
    > typedef Foo<int> X;
    >
    > // some silly example code
    > void tst()
    > {
    > X::Alist_t al; // line 36
    > X::Blist_t bl;
    >
    > // make an A element
    > al.push_front( X::A() );
    >
    > // make a B element
    > bl.push_front( X::B() );
    >
    > // Set up iterators to point to each other
    > al.front().bitr = bl.begin();
    > bl.front().aitr = al.begin(); // line 47
    >
    > }
    >
    > int main()
    > {
    > tst();
    > }

    [Line numbers added for reference]

    Still fails using concept checks:

    mariani_002.cc: In instantiation of 'Foo<int>::B':
    /added/pkg/gcc-4.1.1/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++
    /4.1.1/bits/boost_concept_check.h:216: instantiated
    from '__gnu_cxx::_SGIAssig
    nableConcept<Foo<int>::B>'
    /added/pkg/gcc-4.1.1/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++
    /4.1.1/bits/stl_list.h:402: instantiated from 'std::list<Foo<int>::B,
    std::all
    ocator<Foo<int>::B> >'
    mariani_002.cc:17: instantiated from 'Foo<int>::A'
    /added/pkg/gcc-4.1.1/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++
    /4.1.1/bits/boost_concept_check.h:216: instantiated
    from '__gnu_cxx::_SGIAssig
    nableConcept<Foo<int>::A>'
    /added/pkg/gcc-4.1.1/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++
    /4.1.1/bits/stl_list.h:402: instantiated from 'std::list<Foo<int>::A,
    std::all
    ocator<Foo<int>::A> >'
    mariani_002.cc:36: instantiated from here
    mariani_002.cc:25: error: no type named 'iterator' in 'class
    std::list<Foo<int>:
    :A, std::allocator<Foo<int>::A> >'
    mariani_002.cc: In function 'void tst()':
    mariani_002.cc:47: error: 'struct Foo<int>::B' has no member named 'aitr'


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Oct 1, 2006
    #10
  11. joshd

    joshd Guest

    > Still not clear. You have used three symbols, | -> and +. I think I have got
    > the first two, but what does + denote? And what does the switch from
    > "linklist" to "list" signify?


    They have no meaning, I just used those characters to distinguish
    relationships between the linked list, node, and so on.

    >
    > Is it simply that you have a parent linked list and that each node in the
    > parent linked list contains a linked list?


    Yes this is exactley what Im looking for. I just am unable to figure
    out how to do it, maybe Im missing something simple or havent read the
    correct articles. Could you please provide some information on doing
    it this way.

    >
    > > Can this be done without iterators? or should I study more to wrap my
    > > mind around STL and iterators?

    >
    > If you are writing your own linked list, then you can avoid iterators. If
    > you are using the standard library linked list, then iterators are
    > fundamental. Writing your own linked list can be a useful learning exercise,
    > but using the standard library containers is almost always preferable for
    > any program that isn't a learning exercise. You should definitely learn the
    > standard library containers, along with iterators.


    This is a learning exercise, I would really like to fully grasp the
    concepts before moving onto something else. I dont like to 'partially'
    know what Im doing.

    Thanks for all your help! Greatly appreciated!

    Josh
     
    joshd, Oct 1, 2006
    #11
  12. Kai-Uwe Bux wrote:
    > Gianni Mariani wrote:
    >
    >> Kai-Uwe Bux wrote:
    >> ...
    >>> Formally, this is undefined behavior because A and B are incomplete types
    >>> (see [17.4.3.6/1 and 2]). Accordingly, the code fails with g++ and
    >>> stdlibc++ when g++ is compiled with --enable-concept-check.
    >>>

    >>
    >> OK - this should conform now.

    ....
    >
    > Still fails using concept checks:


    I think this is a compiler bug, although I'm not sure. The check in the
    gcc concept check is too aggressive in this case.

    The Comeau compiler failed to compile the first example and succeeded in
    the second example. (not that it's a bug either way but just a data point).
     
    Gianni Mariani, Oct 1, 2006
    #12
  13. joshd

    John Carson Guest

    "joshd" <> wrote in message
    news:
    >>
    >> Is it simply that you have a parent linked list and that each node
    >> in the parent linked list contains a linked list?

    >
    > Yes this is exactley what Im looking for. I just am unable to figure
    > out how to do it, maybe Im missing something simple or havent read the
    > correct articles. Could you please provide some information on doing
    > it this way.
    >
    >>
    >>> Can this be done without iterators? or should I study more to wrap
    >>> my mind around STL and iterators?

    >>
    >> If you are writing your own linked list, then you can avoid
    >> iterators. If you are using the standard library linked list, then
    >> iterators are fundamental. Writing your own linked list can be a
    >> useful learning exercise, but using the standard library containers
    >> is almost always preferable for any program that isn't a learning
    >> exercise. You should definitely learn the standard library
    >> containers, along with iterators.

    >
    > This is a learning exercise, I would really like to fully grasp the
    > concepts before moving onto something else. I dont like to
    > 'partially' know what Im doing.



    If the learning exercise includes writing the code for a linked list, then I
    suggest you do that first, since it is fairly complicated, requiring a good
    grasp of pointer manipulation.

    Once you have a linked list class, then the rest of it isn't that hard, as I
    will illustrate using std::list. The code uses structs with everything
    public in order to keep it simple.

    #include <list>
    #include <iostream>
    #include <string>
    using namespace std;

    // give the child some members for use in testing
    struct ChildCell
    {
    size_t index;
    string name;
    ChildCell *pmatching;
    ChildCell(size_t i, string nme) : index(i), name(nme), pmatching(0)
    {}
    ChildCell() : index(0), pmatching(0)
    {}
    };

    struct ParentCell
    {
    list<ChildCell> childList;
    int a, b;
    };

    int main()
    {
    list<ParentCell> parentList;
    // add two nodes to parentList
    parentList.push_back(ParentCell());
    parentList.push_back(ParentCell());

    // Add four nodes to the child list in each parent node
    // Do it for first parent node
    list<ParentCell>::iterator it = parentList.begin();
    for(size_t i = 0; i<4; ++i)
    it->childList.push_back(ChildCell(i, "First_Child_List_Cell"));
    // for later use, store a reference to the first childList
    list<ChildCell> & firstChildList = it->childList;

    // Increment iterator to move to second parent node
    // then add four nodes to its child list
    ++it;
    for(size_t i = 0; i<4; ++i)
    it->childList.push_back(ChildCell(i, "Second_Child_List_Cell"));
    // for later use, store a reference to the second childList
    list<ChildCell> & secondChildList = it->childList;

    // Now we make each cell in the child list store a pointer to its
    // corresponding cell in the other list
    list<ChildCell>::iterator it1, it2;
    for(it1 = firstChildList.begin(),
    it2 = secondChildList.begin();
    it1!= firstChildList.end()
    && it2!= secondChildList.end();
    ++it1, ++it2)
    {
    it1->pmatching = &(*it2);
    it2->pmatching = &(*it1);
    }

    // test that it worked
    cout << "Iterating over first child list\n";
    for(it1 = firstChildList.begin();
    it1!= firstChildList.end(); ++it1)
    {
    cout << "Name is " << it1->name;
    cout << " and index is " << it1->index << endl;

    cout << "Name of corresponding cell is ";
    cout << it1->pmatching->name;
    cout << " and index is ";
    cout << it1->pmatching->index << endl << endl;
    }

    cout << "\n\nIterating over second child list\n";
    for(it2 = secondChildList.begin();
    it2!= secondChildList.end(); ++it2)
    {
    cout << "Name is " << it2->name;
    cout << " and index is " << it2->index << endl;

    cout << "Name of corresponding cell is ";
    cout << it2->pmatching->name;
    cout << " and index is ";
    cout << it2->pmatching->index << endl << endl;
    }
    return 0;
    }


    --
    John Carson
     
    John Carson, Oct 2, 2006
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    513
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    502
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    544
    Barry Schwarz
    Jul 3, 2006
  4. jawdoc
    Replies:
    9
    Views:
    807
    Chris Thomasson
    Mar 10, 2008
  5. mac
    Replies:
    1
    Views:
    1,573
    Jens Thoms Toerring
    May 27, 2008
Loading...

Share This Page