LinkedList with Nodes

M

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:
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
 
D

David Harmon

On 18 Oct 2006 08:30:36 -0700 in comp.lang.c++, (e-mail address removed) 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...:((
Click to expand...

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!)
 
M

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

David Harmon

On 18 Oct 2006 09:20:09 -0700 in comp.lang.c++, (e-mail address removed) 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?
Click to expand...

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..:-/
Click to expand...

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.
 
M

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...?
 
D

David Harmon

On 18 Oct 2006 09:57:34 -0700 in comp.lang.c++, (e-mail address removed) 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...?
Click to expand...

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.
 
M

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)

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
 
D

David Harmon

On 18 Oct 2006 11:11:55 -0700 in comp.lang.c++, (e-mail address removed) wrote,
Code: 
void sequence::start()
{
	cursor = head_ptr;
	precursor = head_ptr;
}[/QUOTE]

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;
}
[QUOTE]
void sequence::advance()
{
	cursor = cursor->link();
	precursor = precursor->link();
}[/QUOTE]

void sequence::advance()
{
	precursor = cursor;
	cursor = cursor->link();
}
[QUOTE]
void sequence::insert(const value_type& entry)
{
	list_head_insert(precursor, entry);

	precursor->set_link

	++many_nodes;
}[/QUOTE]

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.
Click to expand...
 
M

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
 
D

David Harmon

On 18 Oct 2006 13:20:18 -0700 in comp.lang.c++, (e-mail address removed) 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...:
Click to expand...

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.
 
M

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

mathon

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
 
A

Alf P. Steinbach

* (e-mail address removed):
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? :(
Click to expand...

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.
 
M

mathon

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
 
M

mathon

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
 
A

Alf P. Steinbach

* (e-mail address removed):
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....? :(
Click to expand...

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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Time analysis 1
Delete a node from a linkedlist 2
C++ Container (Sequence Class) 6
Sequence Class 14
How to workaround this tree implementation that breaks with Sun studio 5
insert a new node in a binary search tree 4
Is there any better approach to private inheriting from the STL containers? 0
what may cause compile error (expected nested-name-specifier before 'Policy-T')? 2

Staff online

Members online

Total: 34 (members: 2, guests: 32)
Robots: 195

Forum statistics

Threads
473,766
Messages
2,569,569
Members
45,045
Latest member
DRCM

Latest Threads

Top