Link List

[Shawn Windle]

----begin node.h--------
#ifndef NODE_H
#define NODE_H

#include <iostream> //NULL

using namespace std;

class node
{
public:
node(int new_data = 0, node *new_link = NULL)
{
data = new_data;
link = new_link;
}
private:
int data;
node *link;

friend class list;
};

#endif

----end node.h-------

----begin list.h------
#ifndef LIST_H
#define LIST_H

#include <iostream> //NULL
#include "node.h"

using namespace std;

class list
{
public:
list() { header = NULL; }
void insert(int new_item);
void print();

private:
node *header;
};

#endif
---end list.h-------

---begin list.cpp-----
#include "list.h"

using namespace std;

void list::insert(in t new_item)
{
int i = 0;
node *itr = header;
if(itr == NULL)
header = new node(new_item,N ULL);
else
{
while(itr->link != NULL)
{
i++;
itr->link = itr->link->link;
}
//cout << i << endl;
itr->link = new node(new_item,N ULL);
}

return;
}

void list::print()
{
node *itr = header;
if(itr == NULL)
cout << "Empty list" << endl;
else
{
while(itr->link != NULL)
{
cout << itr->data << endl;
itr->link = itr->link->link;
}
}

return;
}

----end list.cpp-------

----begin main.cpp-------
#include <iostream>
#include "list.h"

using namespace std;

int main()
{
list a;
a.insert(10);
a.insert(11);
a.insert(123);
a.print();
return 0;
}
----end main.cpp-------

I've been trying to write a Linked List Data Structure and I've run
into some trouble. Could someone please help me out? I can insert one
int, but thats all. I think the problem is in void list::insert(in t
new_item), but I can't figure out what it is. Thanks for the help!

Shawn Windle

[Patrik Stellmann]

Re: Link List


<snip>[color=blue]
> void list::insert(in t new_item)
> {
> int i = 0;
> node *itr = header;
> if(itr == NULL)
> header = new node(new_item,N ULL);
> else
> {
> while(itr->link != NULL)
> {
> i++;
> itr->link = itr->link->link;
> }
> //cout << i << endl;
> itr->link = new node(new_item,N ULL);
> }
>
> return;
> }[/color]
<snip>

didn't test it but I think it should be
itr = itr->link;
in the loop because initially itr is the header and in your loop itr
doesn't change so after the loop you always attach your new item to the
header instead of to the end of the list!

[John Harrison]

Re: Link List


"Shawn Windle" <fearloathing20 01@yahoo.com> wrote in message
news:269ec232.0 402172035.6c2c0 f1e@posting.goo gle.com...[color=blue]
> ----begin node.h--------
> #ifndef NODE_H
> #define NODE_H
>
> #include <iostream> //NULL
>
> using namespace std;
>
> class node
> {
> public:
> node(int new_data = 0, node *new_link = NULL)
> {
> data = new_data;
> link = new_link;
> }
> private:
> int data;
> node *link;
>
> friend class list;
> };
>
> #endif
>
> ----end node.h-------
>
> ----begin list.h------
> #ifndef LIST_H
> #define LIST_H
>
> #include <iostream> //NULL
> #include "node.h"
>
> using namespace std;
>
> class list
> {
> public:
> list() { header = NULL; }
> void insert(int new_item);
> void print();
>
> private:
> node *header;
> };
>
> #endif
> ---end list.h-------
>
> ---begin list.cpp-----
> #include "list.h"
>
> using namespace std;
>
> void list::insert(in t new_item)
> {
> int i = 0;
> node *itr = header;
> if(itr == NULL)
> header = new node(new_item,N ULL);
> else
> {
> while(itr->link != NULL)
> {
> i++;
> itr->link = itr->link->link;
> }
> //cout << i << endl;
> itr->link = new node(new_item,N ULL);
> }
>
> return;
> }
>
> void list::print()
> {
> node *itr = header;
> if(itr == NULL)
> cout << "Empty list" << endl;
> else
> {
> while(itr->link != NULL)
> {
> cout << itr->data << endl;
> itr->link = itr->link->link;
> }
> }
>
> return;
> }
>
> ----end list.cpp-------
>
> ----begin main.cpp-------
> #include <iostream>
> #include "list.h"
>
> using namespace std;
>
> int main()
> {
> list a;
> a.insert(10);
> a.insert(11);
> a.insert(123);
> a.print();
> return 0;
> }
> ----end main.cpp-------
>
> I've been trying to write a Linked List Data Structure and I've run
> into some trouble. Could someone please help me out? I can insert one
> int, but thats all. I think the problem is in void list::insert(in t
> new_item), but I can't figure out what it is. Thanks for the help!
>
> Shawn Windle[/color]

The problem is in the while loop in list::insert. You are trying to loop
though the list but when you do

itr->link = itr->link->link;

you are actually changing the list you are looping though. Same problem in
print, you're going to have to rethink your approach.

Have a think about it, post here if you are still stuck.

Good design by the way, one class for the list and one for the nodes is
exactly what you should do.

john

[Shawn Windle]

Re: Link List

"John Harrison" <john_andronicu s@hotmail.com> wrote in message news:<c0v5rr$1c 9of6$1@ID-196037.news.uni-berlin.de>...[color=blue]
> "Shawn Windle" <fearloathing20 01@yahoo.com> wrote in message
> news:269ec232.0 402172035.6c2c0 f1e@posting.goo gle.com...[/color]
[color=blue][color=green]
> > ---begin list.cpp-----
> > #include "list.h"
> >
> > using namespace std;
> >
> > void list::insert(in t new_item)
> > {
> > int i = 0;
> > node *itr = header;
> > if(itr == NULL)
> > header = new node(new_item,N ULL);
> > else
> > {
> > while(itr->link != NULL)
> > {
> > i++;
> > itr->link = itr->link->link;
> > }
> > //cout << i << endl;
> > itr->link = new node(new_item,N ULL);
> > }
> >
> > return;
> > }
> >
> > void list::print()
> > {
> > node *itr = header;
> > if(itr == NULL)
> > cout << "Empty list" << endl;
> > else
> > {
> > while(itr->link != NULL)
> > {
> > cout << itr->data << endl;
> > itr->link = itr->link->link;
> > }
> > }
> >
> > return;
> > }
> >[/color][/color]
[color=blue][color=green]
> >
> > I've been trying to write a Linked List Data Structure and I've run
> > into some trouble. Could someone please help me out? I can insert one
> > int, but thats all. I think the problem is in void list::insert(in t
> > new_item), but I can't figure out what it is. Thanks for the help!
> >
> > Shawn Windle[/color]
>
> The problem is in the while loop in list::insert. You are trying to loop
> though the list but when you do
>
> itr->link = itr->link->link;
>
> you are actually changing the list you are looping though. Same problem in
> print, you're going to have to rethink your approach.
>
> Have a think about it, post here if you are still stuck.
>
> Good design by the way, one class for the list and one for the nodes is
> exactly what you should do.
>
> john[/color]

Thanks for the help! How else could I loop through the list? I didn't
know that I was chaning it. Sorry.

[Shawn Windle]

Re: Link List

> The problem is in the while loop in list::insert. You are trying to loop[color=blue]
> though the list but when you do
>
> itr->link = itr->link->link;
>
> you are actually changing the list you are looping though. Same problem in
> print, you're going to have to rethink your approach.
>
> Have a think about it, post here if you are still stuck.
>
> Good design by the way, one class for the list and one for the nodes is
> exactly what you should do.
>
> john[/color]

Thanks for the help! I figured it out. Sorry for posting the follow-up
message earlier.

Shawn Windle

[Thomas Matthews]

Re: Link List

Shawn Windle wrote:

[code snipped]
[color=blue]
>
> I've been trying to write a Linked List Data Structure and I've run
> into some trouble. Could someone please help me out? I can insert one
> int, but thats all. I think the problem is in void list::insert(in t
> new_item), but I can't figure out what it is. Thanks for the help!
>
> Shawn Windle[/color]

Is there any reason you are not using the list container in
the STL? It is already working and has been tested, removing
a lot of time and effort from your project's schedule.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.c om/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:
http://www.raos.demon. uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.co m -- C++ STL Library book

[red floyd]

Re: Link List

Thomas Matthews wrote:[color=blue]
> Shawn Windle wrote:
>
> [linked list problem redacted]
>
> Is there any reason you are not using the list container in
> the STL? It is already working and has been tested, removing
> a lot of time and effort from your project's schedule.
>[/color]

I've often been tempted to respond like you. However, often it looks
like the poster is trying to understand the basic data structure (as in
this case). The best way to do that is to learn by doing. Once he
understands the structure, then yeah, go ahead and use the STL std::list.

[Shawn Windle]

Re: Link List

red floyd <no.spam@here.d ude> wrote in message news:<QeNYb.273 44$hB4.21424@ne wssvr25.news.pr odigy.com>...[color=blue]
> Thomas Matthews wrote:[color=green]
> > Shawn Windle wrote:
> >
> > [linked list problem redacted]
> >
> > Is there any reason you are not using the list container in
> > the STL? It is already working and has been tested, removing
> > a lot of time and effort from your project's schedule.
> >[/color]
>
> I've often been tempted to respond like you. However, often it looks
> like the poster is trying to understand the basic data structure (as in
> this case). The best way to do that is to learn by doing. Once he
> understands the structure, then yeah, go ahead and use the STL std::list.[/color]

Exactly! I find I learn better by acutally doing it myself. I finally
finished the linked list data structure (as a template). Next I'll
might do a tree. I've been reading and teaching myself about Data
Structures using Data Structures & Algorithm Analysis in C++ by Mark
Allen Weiss (Ch. 3 was on Linked Lists, Stacks and Queue--Ch.4 is on
Trees). :)

Shawn Windle
Homepage-http://www.geocities.c om/fearloathing200 1 (Work in Progress)