LinkedList with Nodes

[mathon]

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:

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.

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

[David Harmon]

On 18 Oct 2006 08:30:36 -0700 in comp.lang.c++, ma****@gmx.at 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!)

[mathon]

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..:-/

[David Harmon]

On 18 Oct 2006 09:20:09 -0700 in comp.lang.c++, ma****@gmx.at 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.

[mathon]

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++, ma****@gmx.at 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]

On 18 Oct 2006 09:57:34 -0700 in comp.lang.c++, ma****@gmx.at 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.

[mathon]

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)

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

[David Harmon]

On 18 Oct 2006 11:11:55 -0700 in comp.lang.c++, ma****@gmx.at wrote,

>[code]
void sequence::start()
{
cursor = head_ptr;
precursor = head_ptr;
}

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;
}

>void sequence::advance()
{
cursor = cursor->link();
precursor = precursor->link();
}

void sequence::advance()
{
precursor = cursor;
cursor = cursor->link();
}

>void sequence::insert(const value_type& entry)
{
list_head_insert(precursor, entry);

precursor->set_link

++many_nodes;
}

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.

[mathon]

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

[David Harmon]

On 18 Oct 2006 13:20:18 -0700 in comp.lang.c++, ma****@gmx.at 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.

[mathon]

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...? :(

[mathon]

hi,

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

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

[Alf P. Steinbach]

* ma****@gmx.at:

hi,

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

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?

[mathon]

hi,

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

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:

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

[mathon]

hi,

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

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:

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

[Alf P. Steinbach]

* ma****@gmx.at:

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?