Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > LinkedList with Nodes

Reply
Thread Tools

LinkedList with Nodes

 
 
mathon@gmx.at
Guest
Posts: n/a
 
      10-18-2006
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

 
Reply With Quote
 
 
 
 
David Harmon
Guest
Posts: n/a
 
      10-18-2006
On 18 Oct 2006 08:30:36 -0700 in comp.lang.c++, http://www.velocityreviews.com/forums/(E-Mail 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...(


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

 
Reply With Quote
 
 
 
 
mathon@gmx.at
Guest
Posts: n/a
 
      10-18-2006

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

 
Reply With Quote
 
David Harmon
Guest
Posts: n/a
 
      10-18-2006
On 18 Oct 2006 09:20:09 -0700 in comp.lang.c++, (E-Mail 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?


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.

 
Reply With Quote
 
mathon@gmx.at
Guest
Posts: n/a
 
      10-18-2006


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++, (E-Mail 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?

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


 
Reply With Quote
 
David Harmon
Guest
Posts: n/a
 
      10-18-2006
On 18 Oct 2006 09:57:34 -0700 in comp.lang.c++, (E-Mail 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...?


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.

 
Reply With Quote
 
mathon@gmx.at
Guest
Posts: n/a
 
      10-18-2006
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

 
Reply With Quote
 
David Harmon
Guest
Posts: n/a
 
      10-18-2006
On 18 Oct 2006 11:11:55 -0700 in comp.lang.c++, (E-Mail Removed) 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.

 
Reply With Quote
 
mathon@gmx.at
Guest
Posts: n/a
 
      10-18-2006

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(4 : 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

 
Reply With Quote
 
David Harmon
Guest
Posts: n/a
 
      10-18-2006
On 18 Oct 2006 13:20:18 -0700 in comp.lang.c++, (E-Mail 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...:


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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Text nodes and element nodes query asd Java 3 05-23-2005 10:01 AM
finding nodes that don't match other nodes mlybarger@gmail.com XML 2 01-27-2005 07:26 PM
Looking A Nodes From Within Nodes Johnny Ooi XML 10 11-14-2004 06:55 PM
selecting nodes between other nodes Timo Nentwig XML 1 06-17-2004 04:54 AM
Reality check: Is it sensible to link XML nodes to other XML nodes in the same file? gavnosis XML 0 08-02-2003 08:22 AM



Advertisments