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(int new_item)
{
int i = 0;
node *itr = header;
if(itr == NULL)
header = new node(new_item,NULL);
else
{
while(itr->link != NULL)
{
i++;
itr->link = itr->link->link;
}
//cout << i << endl;
itr->link = new node(new_item,NULL);
}

return;
}

void list:rint()
{
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(int
new_item), but I can't figure out what it is. Thanks for the help!

Shawn Windle

 

[Patrik Stellmann]

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

return;
}

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

----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(int new_item)
{
int i = 0;
node *itr = header;
if(itr == NULL)
header = new node(new_item,NULL);
else
{
while(itr->link != NULL)
{
i++;
itr->link = itr->link->link;
}
//cout << i << endl;
itr->link = new node(new_item,NULL);
}

return;
}

void list:rint()
{
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(int
new_item), but I can't figure out what it is. Thanks for the help!

Shawn Windle

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]

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

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

 

[Shawn Windle]

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

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

Shawn Windle

 

[Thomas Matthews]

Shawn Windle wrote:

[code snipped]

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(int
new_item), but I can't figure out what it is. Thanks for the help!

Shawn Windle

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.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[red floyd]

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.

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]

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.

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.

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.com/fearloathing2001 (Work in Progress)