Sign in to follow this  

Linked list questions in c++

This topic is 2491 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am working on a very simple linear single linked list in c++

My question is how can I make a class that can take either {1,2,3....n+1} data types?

For example
I want to creat a list that takes int as the data type
using the same class but differnt program I want to use the list to take strings and int as data types with out having to make 2 seprate lists.

list<int>
list<string,int>

I am using templates so any data type can be used

Share this post


Link to post
Share on other sites
Just to be sure: you want to be able to create a list where, for example, the first element is a string, the next is an int, the next might be a double, and then a float, and so on?

The usual way of doing this is to first think carefully about the behaviour you expect of each type you want to store in the list. Then create a polymorphic base class with virtual functions that represent the distillation of that behaviour. For example, if all you want to be able to do is display the elements to an ostream, your list's node might be something like this:

[code]
struct node
{
node() : next(0) { }
virtual ~node() { }
virtual std::ostream &display(std::ostream &out) const = 0;
// maybe other virtual functions here, too e.g. clone()

node *next;
};
[/code]

and you'd also have a template class that inherits from 'node' and happens to implement the display() function for the given type:

[code]
template<typename T>
struct typed_node : node
{
typed_node(const T &data) : data(data) { }
virtual std::ostream &display(std::ostream &out) const { return out << data; }

T data;
};
[/code]

Finally, the method that adds a function to your list would be a template method:

[code]
template<typename T>
void list::push_back(const T &data)
{
node *n = new typed_node<T>(data);
// TODO: adjust pointers in list s.t. n is at the end
// ...
}
[/code]

Other alternatives include:

1. not having the 'next' element in the node base class and use an std::list<node*> instead.
2. std::list<boost::any>
3. std::list<boost::variant>
4. use Python or another dynamically typed language (to a certain degree, this is what the above system is simulating anyway)

Share this post


Link to post
Share on other sites
[quote name='CzarKirk' timestamp='1298207008' post='4776652']
Why not make a structure which contains int and string and store that?
[/quote]
That doesn't really fit the OP's requirements (among other thing, the OP wants to use templates).

Share this post


Link to post
Share on other sites
[quote name='jyk' timestamp='1298209879' post='4776663']
[quote name='CzarKirk' timestamp='1298207008' post='4776652']
Why not make a structure which contains int and string and store that?
[/quote]
That doesn't really fit the OP's requirements (among other thing, the OP wants to use templates).
[/quote]

You can still have a template. When you want only int, use only int. But if you want a single list which can store both ints and strings, use a struct as the template parameter that holds both types but only use one of them. There will be a few bytes of wasted space but not the end of the world.

Share this post


Link to post
Share on other sites
not really what I was meaning. the linked list needs a string and a int in the same node. and uses class's not structs. The template is going to allow what verible tpe can be used but how can you use more then one without making more then one list.

Share this post


Link to post
Share on other sites
[quote name='kingpinzs' timestamp='1298227160' post='4776750']
not really what I was meaning. the linked list needs a string and a int in the same node.
[/quote]
So what's the problem? Create a small data type containing both a string and an int.

[quote]
and uses class's not structs.
[/quote]
The difference between a class and a struct is probably smaller than you think. Use 'class' instead of 'struct' if you want. My example code didn't because it would have involved more boilerplate.

[quote]
The template is going to allow what verible tpe can be used but how can you use more then one without making more then one list.
[/quote]
[code]
struct data_pair
{
data_pair() : s(), i(0) { }
std::string s;
int i;
};

std::list<data_pair> mylist;
[/code]

Or use std::pair:

[code]
typedef std::pair<std::string, int> data_pair;
std::list<data_pair> mylist;
[/code]


EDIT: so re-examining your initial question:
[quote]My question is how can I make a class that can take either {1,2,3....n+1} data types?[/quote]
This is tricky without variadic templates (coming to C++ soon, but not quite there yet). You'd have to use something commonly called type-lists or look at some of the stuff in boost::mpl and boost::fusion (which is quite advanced and not for the timid).

But! Why do you want to do this? There might be a better way.

Share this post


Link to post
Share on other sites
is there a way to use

struct user
{
string name;
int id;
};

as the data type for a linked list?

the class for the linked list looks like this

template <class Item>

class node
{
public:
typedef Item value_type;

node(const value_type& init_data = value_type(),const node* init_link = NULL)
{
data_field = init_data; link_field = init_link;
}
void set_data(const value_type& new_data){data_field = new_data;}
void set_link(node* new_link) {link_field = new_link;}

value_type data() const{return data_field;}

const node* link() const{return link_field;}
node* link() {return link_field;}
protected:
private:
value_type data_field;
node *link_field;
};


Share this post


Link to post
Share on other sites
becuase I need to learn the data structures and the best way to do it is create the data structure from scratch first.

Second I did try it and it errors out.

I am just not sure how to call it.

user p ;
p.name = "ted";
p.id =12;
node<user> *head_ptr;
node<user> *tail_ptr;

node<user> r;

head_ptr = NULL;
tail_ptr = NULL;

I have tryed
head_ptr = p;

and
r = new node<user>(p)

and I get error
no match for 'operator=' in 'r = (operator new(12u), (<statement>, ((node<user>*)<anonymous>)))'|
candidate is: node<user>& node<user>::operator=(const node<user>&)|
In constructor 'node<Item>::node(const value_type&, const node<Item>*) [with Item = user, value_type = user, node<Item> = node<user>]':|


so I have no idea ho to make a struct the template data to pass to my linked list class

I kno I can just change the linked list class to take the string and int but I need it to be more genral then that.

Not sure of any other way to do that.

Share this post


Link to post
Share on other sites
[quote name='kingpinzs' timestamp='1298320937' post='4777196']
user p ;
p.name = "ted";
p.id =12;
node<user> *head_ptr;
node<user> *tail_ptr;

node<user> r;

head_ptr = NULL;
tail_ptr = NULL;

I have tryed
head_ptr = p;
[/quote]
head_ptr is of type [b]node<user>*[/b] and p is of type [b]user[/b] so this assignment won't work as the types are really quite unrelated. You need to create a node<user>* in order to initialize head_ptr.

Something like:

[code]
template<typename T>
struct node
{
node(const T &data) : data(data), next(0) { }
T data;
node *next;
};

struct user
{
user(const std::string &name, int id) : name(name), id(id) { }
std::string name;
int id;
};

// ...

node<user> *p = new node<user>(user("ted", 12));
[/code]

This is reasonably elementary-level stuff. If you're struggling with it, it might be worth picking up a beginners C++ text or reading through some tutorials.

Share this post


Link to post
Share on other sites
I am in my second year of collage I already did the c++ calss doing data structures
did the queue and stack assinment. Working on the linked list one but I want to do more then what the min requirements of the assinment is.

So its not that easy to creat what I need from scratch without using the stl.

It has to be all from scratch.

The linked list works as long as I set it to the data I want and I can set it to 2 data types bit to do that I would have to change the class every
time I wanted to make a change which is not what I want. The professor dont care so he wont help with making it better.

[code]
template <class Item> //edit for got this part

class node
{
public:
typedef Item value_type;

node(const Item& init_data = Item(),const node* init_link = NULL)
{
data_field = init_data; link_field = init_link;
}
void set_data(const Item& new_data){data_field = new_data;}
void set_link(node* new_link) {link_field = new_link;}

const Item& data() const{return data_field;}

const node* link() const{return link_field;}
node* link() {return link_field;}
protected:
private:
Item data_field;
node *link_field;
};
[/code]

This is my header file for my linked list class
But as you can see it only takes one data type and I could change it to take two data types but I rather use a struct to contain the data needed then pass it to the list.

Share this post


Link to post
Share on other sites
You should learn about templates. They allow you to make code for any type of data. You can change the data type of Item without having to alter the code, and have lists which can contain only their kind of data to prevent errors.

Share this post


Link to post
Share on other sites
[quote name='CzarKirk' timestamp='1298329399' post='4777279']
You should learn about templates. They allow you to make code for any type of data. You can change the data type of Item without having to alter the code, and have lists which can contain only their kind of data to prevent errors.
[/quote]

the thing is I am trying to use a template but I cant figure out the syntax to make the call
from the noce class using the user struct as the data.

Share this post


Link to post
Share on other sites
[quote name='kingpinzs' timestamp='1298330016' post='4777283']
the thing is I am trying to use a template but I cant figure out the syntax to make the call
from the noce class using the user struct as the data.
[/quote]
Does my previous post not illustrate how you might do that? If not can you be more specific about where you're having trouble?

Share this post


Link to post
Share on other sites

This topic is 2491 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this