LinkedList with Nodes

Discussion in 'C++' started by mathon@gmx.at, Oct 18, 2006.

  1. Guest

    Hi,

    i am currently working on creating a LinkedList, for that I using a
    predefined Node-class which offers a LinkedList Toolkit to manipulate
    the Linked List (http://www.cs.colorado.edu/~main/chapter5/node1.h). I
    develop a Squence-Class which should store a sequence of numbers in a
    LinkedList.

    My header file of sequence looks like this, respectively the methods
    and variables:
    Code:
    public:
            // TYPEDEFS and MEMBER CONSTANTS
            typedef double value_type;
            typedef std::size_t size_type;
            // CONSTRUCTORS and DESTRUCTOR
            sequence( );
            sequence(const sequence& source);
            ~sequence( );
            // MODIFICATION MEMBER FUNCTIONS
            void start( );
            void advance( );
            void insert(const value_type& entry);
            void attach(const value_type& entry);
            void operator =(const sequence& source);
            void remove_current( );
            // CONSTANT MEMBER FUNCTIONS
            size_type size( ) const { return many_nodes; }
            bool is_item( ) const { return (cursor != NULL); }
            value_type current( ) const;
        private:
        node *head_ptr;
        node *tail_ptr;
        node *cursor;
        node *precursor;
        size_type many_nodes;
     
    I already implemented the two constructors, the desctructor, the
    advance and start-method.
    Code:
    sequence::sequence()
    {
        head_ptr = NULL;
        tail_ptr = NULL;
        many_nodes = 0;
    }
    
    sequence::sequence(const sequence& source)
    {
        node *tail_ptr;
        list_copy(source.head_ptr, head_ptr, tail_ptr);
        many_nodes = source.many_nodes;
    }
    
    sequence::~sequence()
    {
        list_clear(head_ptr);
        many_nodes = 0;
    }
    
    void sequence::start()
    {
        cursor = head_ptr;
    }
    
    void sequence::advance()
    {
        cursor = cursor->link();
    }
    
    I hope they are right defined.
    Unfortunately I really have problems with the insert-function.
    According to the specification the insert function should insert a node
    before the node which the current cursor points to. So therefore I have
    to point with the precursor to the node before the node the cursor
    points to, but I do not understand how i can find out this
    position...:((

    Does anybody know here how this insert-method could be efficient
    defined?

    matti
     
    , Oct 18, 2006
    #1
    1. Advertising

  2. David Harmon Guest

    On 18 Oct 2006 08:30:36 -0700 in comp.lang.c++, wrote,
    >According to the specification the insert function should insert a node
    >before the node which the current cursor points to. So therefore I have
    >to point with the precursor to the node before the node the cursor
    >points to, but I do not understand how i can find out this
    >position...:((


    You get it from the "precursor" of the existing node that you are
    inserting before (before clobbering that value with the pointer to
    the inserted node!)
     
    David Harmon, Oct 18, 2006
    #2
    1. Advertising

  3. Guest

    Yes I have to let the precursor point to the previous node before the
    one to which the cursor pointer points to.

    but how can I set the precursor pointer to the previous node - the node
    before the node to which the cursor points to?

    matti

    PS: sorry but I don't understand what do you mean with clobbering,
    unfortunately i am not an english native speaker and my dictionary gave
    me some strange translations for that word..:-/
     
    , Oct 18, 2006
    #3
  4. David Harmon Guest

    On 18 Oct 2006 09:20:09 -0700 in comp.lang.c++, wrote,
    >
    >Yes I have to let the precursor point to the previous node before the
    >one to which the cursor pointer points to.
    >
    >but how can I set the precursor pointer to the previous node - the node
    >before the node to which the cursor points to?


    The precursor pointer of the node the cursor points to is what you
    need.

    The precursor pointers in the nodes of the existing list form a back
    pointing chain, that you can follow backwards as far as you need to.

    >PS: sorry but I don't understand what do you mean with clobbering,
    >unfortunately i am not an english native speaker and my dictionary gave
    >me some strange translations for that word..:-/


    Sorry. By that I mean, when you insert the node, you will change
    the precursor pointer of the existing node to point to the new node,
    but you need to save the old value of the pointer before you change
    it. That old value is the one you need to find the previous node.

    Yes, it's a strange word. I could not define it myself.
     
    David Harmon, Oct 18, 2006
    #4
  5. Guest

    thanks for the explanation...but now I am a little bit confused, every
    node in my class has only data field and a pointer to the next node
    (regarding the definition and implementation of my node-class i use).

    so not every node object has an precursor pointer but only a data field
    and a link to the next node....maybe there is some kind of
    misunderstanding...?


    David Harmon wrote:
    > On 18 Oct 2006 09:20:09 -0700 in comp.lang.c++, wrote,
    > >
    > >Yes I have to let the precursor point to the previous node before the
    > >one to which the cursor pointer points to.
    > >
    > >but how can I set the precursor pointer to the previous node - the node
    > >before the node to which the cursor points to?

    >
    > The precursor pointer of the node the cursor points to is what you
    > need.
    >
    > The precursor pointers in the nodes of the existing list form a back
    > pointing chain, that you can follow backwards as far as you need to.
    >
    > >PS: sorry but I don't understand what do you mean with clobbering,
    > >unfortunately i am not an english native speaker and my dictionary gave
    > >me some strange translations for that word..:-/

    >
    > Sorry. By that I mean, when you insert the node, you will change
    > the precursor pointer of the existing node to point to the new node,
    > but you need to save the old value of the pointer before you change
    > it. That old value is the one you need to find the previous node.
    >
    > Yes, it's a strange word. I could not define it myself.
     
    , Oct 18, 2006
    #5
  6. David Harmon Guest

    On 18 Oct 2006 09:57:34 -0700 in comp.lang.c++, wrote,
    >
    >thanks for the explanation...but now I am a little bit confused, every
    >node in my class has only data field and a pointer to the next node
    >(regarding the definition and implementation of my node-class i use).
    >
    >so not every node object has an precursor pointer but only a data field
    >and a link to the next node....maybe there is some kind of
    >misunderstanding...?


    Yes, my misunderstanding. I was thinking that you had a
    double-linked list, but really you have a single linked list.

    In that case, it would be the precursor field of the list head.
    Make sure that you keep the condition that the precursor always
    points to the node before the cursor.
     
    David Harmon, Oct 18, 2006
    #6
  7. Guest

    ah okay, so i think i have to set the precursor also in the start and
    advance method. but i still do not know exactly how i should set the
    several pointers when i insert a new node (cursor, precursor, tail_ptr,
    head_ptr)

    Code:
    void sequence::start()
    {
    	cursor = head_ptr;
    	precursor = head_ptr;
    }
    
    void sequence::advance()
    {
    	cursor = cursor->link();
    	precursor = precursor->link();
    }
    
    void sequence::insert(const value_type& entry)
    {
    	list_head_insert(precursor, entry);
    
    	precursor->set_link
    
    	++many_nodes;
    }
    
    I hope start and advance is right, i tried it in insert that he should
    insert a new node and the precursor points than to this new node but
    actually the cursor should then point to the new node. I simple don't
    get really through it...? :((

    matti
     
    , Oct 18, 2006
    #7
  8. David Harmon Guest

    On 18 Oct 2006 11:11:55 -0700 in comp.lang.c++, wrote,
    >
    Code:
    >void sequence::start()
    >{
    >	cursor = head_ptr;
    >	precursor = head_ptr;
    >}[/color]
    
    Do not expect the following examples to be exactly right, but
    something generally like the way I would go.
    
    void sequence::start()
    {
    	cursor = head_ptr;
    	precursor = 0;
    }
    [color=blue]
    >void sequence::advance()
    >{
    >	cursor = cursor->link();
    >	precursor = precursor->link();
    >}[/color]
    
    void sequence::advance()
    {
    	precursor = cursor;
    	cursor = cursor->link();
    }
    [color=blue]
    >void sequence::insert(const value_type& entry)
    >{
    >	list_head_insert(precursor, entry);
    >
    >	precursor->set_link
    >
    >	++many_nodes;
    >}[/color]
    
    void sequence::insert(const value_type& entry)
    {
        entry.link = cursor;
        if (precursor) 
            precursor->link = &entry;
        else 
    	    head_ptr = tail_ptr = &entry;
    
        cursor = &entry;
    	++many_nodes;
    }
    
    Write a function that goes through the list and prints all the link
    values.  Call it after every operation to help see what is actually
    happening.
     
    David Harmon, Oct 18, 2006
    #8
  9. Guest

    Unfortunately i got a lot of error because of the code lines in the
    insert-method. entry is of type double so i cannot call entry.link and
    errorso occur for the following lines...:

    error C2228: left of '.link' must have class/struct/union
    sequenceimpl.cpp(48) : error C2659: '=' : function as left operand
    sequenceimpl.cpp(50) : error C2440: '=' : cannot convert from 'const
    main_savitch_5::sequence::value_type *__w64 ' to 'main_savitch_5::node
    *'
    Types pointed to are unrelated; conversion requires
    reinterpret_cast, C-style cast or function-style cast
    sequenceimpl.cpp(52) : error C2440: '=' : cannot convert from 'const
    main_savitch_5::sequence::value_type *__w64 ' to 'main_savitch_5::node
    *'
    Types pointed to are unrelated; conversion requires
    reinterpret_cast, C-style cast or function-style cast

    maybe you know why these problems occur...?

    matti
     
    , Oct 18, 2006
    #9
  10. David Harmon Guest

    On 18 Oct 2006 13:20:18 -0700 in comp.lang.c++, wrote,
    >
    >Unfortunately i got a lot of error because of the code lines in the
    >insert-method. entry is of type double so i cannot call entry.link and
    >errorso occur for the following lines...:


    Well, I did say you would have to fix it up into actual code.
    Instead of entry.link, set the link field of the new node you are
    inserting, whatever it is called.
     
    David Harmon, Oct 18, 2006
    #10
  11. Guest

    yes that is my real problem...i don't know how to use the certain node,
    because I call test.insert(getNumber());

    and then I am in within the insert-method with the corresponding
    parameter, so how i do not really know how i can assign the pointer to
    the real node...? :(
     
    , Oct 18, 2006
    #11
  12. Guest

    hi,

    I implemented insert and attach now and gernally the two functions
    work:

    Code:
    void sequence::start()
    {
            cursor = head_ptr;
            precursor = 0;
    
    }
    
    void sequence::advance()
    {
            precursor = cursor;
    		cursor = cursor->link();
    
    }
    
    void sequence::insert(const value_type& entry)
    {
    	if(precursor == NULL)
    	{
    		list_head_insert(head_ptr, entry);
    		cursor = head_ptr;
    		tail_ptr = head_ptr;
    	}
    	else
    	{
    		list_insert(precursor, entry);
    		cursor = precursor->link();
    	}
    
        ++many_nodes;
    }
    
    void sequence::attach(const value_type& entry)
    {
    	if(cursor == NULL)
    	{
    		list_head_insert(head_ptr, entry);
    		cursor = head_ptr;
    		tail_ptr = head_ptr;
    	}
    	else
    	{
    		list_insert(cursor, entry);
    		cursor = cursor->link();
    	}
    
        ++many_nodes;
    
    }
    
    However there are still errors when I use the testprogram which tests
    the boundaries. Does anybody eventually know what is still wrong at
    these functions? :(

    matti
     
    , Oct 19, 2006
    #12
  13. * :
    > hi,
    >
    > I implemented insert and attach now and gernally the two functions
    > work:
    >
    >
    Code:
    > void sequence::start()
    > {
    >         cursor = head_ptr;
    >         precursor = 0;
    > 
    > }
    > 
    > void sequence::advance()
    > {
    >         precursor = cursor;
    > 		cursor = cursor->link();
    > 
    > }
    > 
    > void sequence::insert(const value_type& entry)
    > {
    > 	if(precursor == NULL)
    > 	{
    > 		list_head_insert(head_ptr, entry);
    > 		cursor = head_ptr;
    > 		tail_ptr = head_ptr;
    > 	}
    > 	else
    > 	{
    > 		list_insert(precursor, entry);
    > 		cursor = precursor->link();
    > 	}
    > 
    >     ++many_nodes;
    > }
    > 
    > void sequence::attach(const value_type& entry)
    > {
    > 	if(cursor == NULL)
    > 	{
    > 		list_head_insert(head_ptr, entry);
    > 		cursor = head_ptr;
    > 		tail_ptr = head_ptr;
    > 	}
    > 	else
    > 	{
    > 		list_insert(cursor, entry);
    > 		cursor = cursor->link();
    > 	}
    > 
    >     ++many_nodes;
    > 
    > }
    > 
    >
    > However there are still errors when I use the testprogram which tests
    > the boundaries. Does anybody eventually know what is still wrong at
    > these functions? :(


    Without having looked at earlier code, it seems that you have two member
    variables 'tail_ptr' and 'precursor' that are being confused.

    I'd drop one of them.

    When you get this to work (which is recommended if you haven't done this
    before), you'll be amazed at the simplicifation a circular list brings.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Oct 19, 2006
    #13
  14. Guest

    hi,

    I did this all and my methods now look like this:

    Code:
    void sequence::start()
    {
            cursor = head_ptr;
            precursor = 0;
    
    }
    
    void sequence::advance()
    {
    		if(is_item())
    		{
    			precursor = cursor;
    			cursor = cursor->link();
    		}
    
    }
    
    void sequence::insert(const value_type& entry)
    {
    	if(!(is_item()))
    		cursor = head_ptr;
    
    	if(precursor == NULL)
    	{
    		list_head_insert(head_ptr, entry);
    		cursor = head_ptr;
    		tail_ptr = head_ptr;
    	}
    	else
    	{
    		list_insert(precursor, entry);
    		cursor = precursor->link();
    	}
    
        ++many_nodes;
    
    	node* cursor1;
    	node * precursor1;
    	for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
    	{
    		precursor1 = cursor1;
    	}
    	tail_ptr = precursor1;
    }
    
    void sequence::attach(const value_type& entry)
    {
    	if(cursor == NULL)
    	{
    		list_head_insert(head_ptr, entry);
    		cursor = head_ptr;
    		tail_ptr = head_ptr;
    	}
    	else
    	{
    		list_insert(cursor, entry);
    		cursor = cursor->link();
    		precursor = cursor;
    	}
    
        ++many_nodes;
    
    	node* cursor1;
    	node* precursor1;
    	for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
    	{
    		precursor1 = cursor1;
    	}
    	tail_ptr = precursor1;
    }
    void sequence::operator =(const sequence& source)
    {
    	if(this == &source)
    		return;
    
    	list_clear(head_ptr);
    	many_nodes=0;
    	list_copy(source.head_ptr, head_ptr, tail_ptr);
    	many_nodes = source.many_nodes;
    }
    
    If have added a for-loop in the insert and attach-method so that the
    tail_ptr points definitely everytime to the last node, when i test this
    function interactiv it works without problems but when i use this
    testprogramm:

    Code:
    int test1( )
    {
        sequence empty;                            // An empty sequence
        sequence test;                             // A sequence to add
    items to
        double items1[4] = { 5, 10, 20, 30 };  // These 4 items are put in
    a sequence
        double items2[4] = { 10, 15, 20, 30 }; // These are put in another
    sequence
    
        // Test that the empty sequence is really empty
        cout << "Starting with an empty sequence." << endl;
        if (!correct(empty, 0, 0, items1)) return 0;
    
        // Test the attach function to add something to an empty sequence
        cout << "I am now using attach to put 10 into an empty sequence."
    << endl;
        test.attach(10);
        if (!correct(test, 1, 0, items2)) return 0;
    
        // Test the insert function to add something to an empty sequence
        cout << "I am now using insert to put 10 into an empty sequence."
    << endl;
        test = empty;
    
        test.insert(10);
    
        if (!correct(test, 1, 0, items2)) return 0;
    
        // Test the insert function to add an item at the front of a
    sequence
        cout << "I am now using attach to put 10,20,30 in an empty
    sequence.\n";
        cout << "Then I move the cursor to the start and insert 5." <<
    endl;
        test = empty;
        test.attach(10);
        test.attach(20);
        test.attach(30);
        test.start( );
        test.insert(5);
        if (!correct(test, 4, 0, items1)) return 0;
    
        // Test the insert function to add an item in the middle of a
    sequence
        cout << "I am now using attach to put 10,20,30 in an empty
    sequence.\n";
        cout << "Then I move the cursor to the start, advance once, ";
        cout << "and insert 15." << endl;
        test = empty;
        test.attach(10);
        test.attach(20);
        test.attach(30);
        test.start( );
        test.advance( );
        test.insert(15);
        if (!correct(test, 4, 1, items2)) return 0;
    
        // Test the attach function to add an item in the middle of a
    sequence
        cout << "I am now using attach to put 10,20,30 in an empty
    sequence.\n";
        cout << "Then I move the cursor to the start and attach 15 ";
        cout << "after the 10." << endl;
        test = empty;
        test.attach(10);
        test.attach(20);
        test.attach(30);
        test.start( );
        test.attach(15);
        if (!correct(test, 4, 1, items2)) return 0;
    
        // All tests have been passed
        cout << "All tests of this first function have been passed." <<
    endl;
    }
    
    the programm stops the line test.insert(10); in the section "I am now
    using insert to put 10 in an empty sequence". A popup-window opens and
    it shows a message that the program has detected an error and has to be
    closed. I also tried to debug the program, but i didn't find the
    error....? :(

    matti
     
    , Oct 19, 2006
    #14
  15. Guest

    hi,

    I did this all and my methods now look like this:

    Code:
    void sequence::start()
    {
            cursor = head_ptr;
            precursor = 0;
    
    }
    
    void sequence::advance()
    {
    		if(is_item())
    		{
    			precursor = cursor;
    			cursor = cursor->link();
    		}
    
    }
    
    void sequence::insert(const value_type& entry)
    {
    	if(!(is_item()))
    		cursor = head_ptr;
    
    	if(precursor == NULL)
    	{
    		list_head_insert(head_ptr, entry);
    		cursor = head_ptr;
    		tail_ptr = head_ptr;
    	}
    	else
    	{
    		list_insert(precursor, entry);
    		cursor = precursor->link();
    	}
    
        ++many_nodes;
    
    	node* cursor1;
    	node * precursor1;
    	for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
    	{
    		precursor1 = cursor1;
    	}
    	tail_ptr = precursor1;
    }
    
    void sequence::attach(const value_type& entry)
    {
    	if(cursor == NULL)
    	{
    		list_head_insert(head_ptr, entry);
    		cursor = head_ptr;
    		tail_ptr = head_ptr;
    	}
    	else
    	{
    		list_insert(cursor, entry);
    		cursor = cursor->link();
    		precursor = cursor;
    	}
    
        ++many_nodes;
    
    	node* cursor1;
    	node* precursor1;
    	for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
    	{
    		precursor1 = cursor1;
    	}
    	tail_ptr = precursor1;
    }
    void sequence::operator =(const sequence& source)
    {
    	if(this == &source)
    		return;
    
    	list_clear(head_ptr);
    	many_nodes=0;
    	list_copy(source.head_ptr, head_ptr, tail_ptr);
    	many_nodes = source.many_nodes;
    }
    
    If have added a for-loop in the insert and attach-method so that the
    tail_ptr points definitely everytime to the last node, when i test this
    function interactiv it works without problems but when i use this
    testprogramm:

    Code:
    int test1( )
    {
        sequence empty;                            // An empty sequence
        sequence test;                             // A sequence to add
    items to
        double items1[4] = { 5, 10, 20, 30 };  // These 4 items are put in
    a sequence
        double items2[4] = { 10, 15, 20, 30 }; // These are put in another
    sequence
    
        // Test that the empty sequence is really empty
        cout << "Starting with an empty sequence." << endl;
        if (!correct(empty, 0, 0, items1)) return 0;
    
        // Test the attach function to add something to an empty sequence
        cout << "I am now using attach to put 10 into an empty sequence."
    << endl;
        test.attach(10);
        if (!correct(test, 1, 0, items2)) return 0;
    
        // Test the insert function to add something to an empty sequence
        cout << "I am now using insert to put 10 into an empty sequence."
    << endl;
        test = empty;
    
        test.insert(10);
    
        if (!correct(test, 1, 0, items2)) return 0;
    
        // Test the insert function to add an item at the front of a
    sequence
        cout << "I am now using attach to put 10,20,30 in an empty
    sequence.\n";
        cout << "Then I move the cursor to the start and insert 5." <<
    endl;
        test = empty;
        test.attach(10);
        test.attach(20);
        test.attach(30);
        test.start( );
        test.insert(5);
        if (!correct(test, 4, 0, items1)) return 0;
    
        // Test the insert function to add an item in the middle of a
    sequence
        cout << "I am now using attach to put 10,20,30 in an empty
    sequence.\n";
        cout << "Then I move the cursor to the start, advance once, ";
        cout << "and insert 15." << endl;
        test = empty;
        test.attach(10);
        test.attach(20);
        test.attach(30);
        test.start( );
        test.advance( );
        test.insert(15);
        if (!correct(test, 4, 1, items2)) return 0;
    
        // Test the attach function to add an item in the middle of a
    sequence
        cout << "I am now using attach to put 10,20,30 in an empty
    sequence.\n";
        cout << "Then I move the cursor to the start and attach 15 ";
        cout << "after the 10." << endl;
        test = empty;
        test.attach(10);
        test.attach(20);
        test.attach(30);
        test.start( );
        test.attach(15);
        if (!correct(test, 4, 1, items2)) return 0;
    
        // All tests have been passed
        cout << "All tests of this first function have been passed." <<
    endl;
    }
    
    the programm stops the line test.insert(10); in the section "I am now
    using insert to put 10 in an empty sequence". A popup-window opens and
    it shows a message that the program has detected an error and has to be
    closed. I also tried to debug the program, but i didn't find the
    error....? :(

    matti
     
    , Oct 19, 2006
    #15
  16. * :
    > hi,
    >
    > I did this all and

    [...]
    >
    > the programm stops the line test.insert(10); in the section "I am now
    > using insert to put 10 in an empty sequence". A popup-window opens and
    > it shows a message that the program has detected an error and has to be
    > closed. I also tried to debug the program, but i didn't find the
    > error....? :(


    Sorry, perhaps I gave bad advice.

    Good advice: start /as simple as possible/. Test all the way. Add a
    little bit of functionality at a time and test thoroughly.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Oct 19, 2006
    #16
    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. asd
    Replies:
    3
    Views:
    452
    Arnaud Berger
    May 23, 2005
  2. gavnosis
    Replies:
    0
    Views:
    538
    gavnosis
    Aug 2, 2003
  3. Timo Nentwig

    selecting nodes between other nodes

    Timo Nentwig, Jun 16, 2004, in forum: XML
    Replies:
    1
    Views:
    428
    Patrick TJ McPhee
    Jun 17, 2004
  4. Johnny Ooi

    Looking A Nodes From Within Nodes

    Johnny Ooi, Nov 13, 2004, in forum: XML
    Replies:
    10
    Views:
    667
    Johnny Ooi
    Nov 14, 2004
  5. Replies:
    2
    Views:
    405
Loading...

Share This Page