By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,406 Members | 888 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,406 IT Pros & Developers. It's quick & easy.

SImple question about structure and linked list

P: n/a
Hi all,

Can a linked list be a member of a structure?
If so, when I add or remove an element from the linked list, the size
of the structure will change. Will it cause any problem?

Thanks a lot.

John
Jul 22 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
jo*********@yahoo.com (John) wrote in
news:c3**************************@posting.google.c om:
Hi all,

Can a linked list be a member of a structure?
Yes, e.g.

struct S {
std::list<int> intList;
};
If so, when I add or remove an element from the linked list, the size
of the structure will change.
No it won't. The elements added to the list are not stored directly in
the list object. They are stored in dynamically allocated memory that is
referred to by the list object.
Will it cause any problem?


See above.

Gregg
Jul 22 '05 #2

P: n/a
John wrote:
Can a linked list be a member of a structure?
No. But a structure may contain a reference (pointer)
to the head of a linked list.
If so, when I add or remove an element from the linked list,
the size of the structure will change.
No. The size of a struct[ure] is fixed.
Will it cause any problem?


A C++ struct (class) does not necessarily *contain* an object.
It may contain references (pointers) to sub objects which are considered
part of the object but *not* part of the struct (class).
Jul 22 '05 #3

P: n/a
John wrote:
Hi all,

Can a linked list be a member of a structure?
Whenever you refer to a list, you refer to the head of the list. So
it is perfectly valid to have a list as a member of the structure.
If so, when I add or remove an element from the linked list, the size
of the structure will change. Will it cause any problem?


Assume you have a struct linked_list already defined.

typedef struct Node {
int info;
struct Node * next;
} NODE;

typedef struct {
NODE * head;
} MyDataStructure;
The size of a variable of type 'MyDataStructure' is fixed, as you could
see. It does not depend on the list at all. ( It is equal to the size of
a single pointer - depending on your implementation - compiler / arch ).

HTH
--
Karthik.
Humans please 'removeme_' for my real email.
Jul 22 '05 #4

P: n/a
John wrote:
Hi all,

Can a linked list be a member of a structure?
If so, when I add or remove an element from the linked list, the size
of the structure will change. Will it cause any problem?

Thanks a lot.

John


Consider the following structure:

struct EXAMPLE
{
char *s ;
} ;

What is the size of this structure? It depends on your implementation,
of course, but for sake of argument let's say that pointers require 4
bytes of memory, and the compiler doesn't introduce any sort of overhead
for structs (a reasonable assumption for a standard PC/compiler).

So, in that case, we have that sizeof(EXAMPLE) == 4.

Now, let's allocate a big chunk of memory.

EXAMPLE e ;
e.s = new char [1024] ;

Now, what is the size of 'e'? Well, we didn't actually do anything to
change the size of e. We allocated 1024 characters *somewhere*, and we
saved the memory address at which we allocated them in e.s, but we block
of memory that represents 'e' didn't change size. So sizeof(e) ==
sizeof(EXAMPLE) == 4.

strings, lists, vectors, and in fact any other sort of container you
could find or dream up will do essentially this same thing. As it needs
more memory, it will allocate it dynamically *somewhere*, but all it
will keep is a pointer to where it allocated that memory. In fact,
there isn't actually anything you CAN do to change the size of a
structure. It turns out that sizeof() really isn't even a function at
all, but instead gets evaluated by the compiler at compile time.

Now consider a second structure:
struct EXAMPLE2
{
int i ;
std::vector<int> v ;
std::string s ;
std::list<int> l ;
} ;

How big is this structure? Well, that depends on what exactly the
members of a vector, string, and list are. On my particular compiler
that structure requires 24 bytes. Now I can add and remove things from
the vector, string, and list as much as I like and still be safe in the
knowledge that the size of the structure is 24 bytes. That doesn't mean
that more memory isn't getting allocated and deallocated somewhere. It
is, and part of the 24 bytes that make up my structure are pointers to
all that memory, but it will never change the fact that my structure is
only 24 bytes.

Alan
Jul 22 '05 #5

P: n/a
Thanks Alan. I understand now.

John

Alan Johnson <al****@mailandnews.com> wrote in message news:<40********@news.ua.edu>...
John wrote:
Hi all,

Can a linked list be a member of a structure?
If so, when I add or remove an element from the linked list, the size
of the structure will change. Will it cause any problem?

Thanks a lot.

John


Consider the following structure:

struct EXAMPLE
{
char *s ;
} ;

What is the size of this structure? It depends on your implementation,
of course, but for sake of argument let's say that pointers require 4
bytes of memory, and the compiler doesn't introduce any sort of overhead
for structs (a reasonable assumption for a standard PC/compiler).

So, in that case, we have that sizeof(EXAMPLE) == 4.

Now, let's allocate a big chunk of memory.

EXAMPLE e ;
e.s = new char [1024] ;

Now, what is the size of 'e'? Well, we didn't actually do anything to
change the size of e. We allocated 1024 characters *somewhere*, and we
saved the memory address at which we allocated them in e.s, but we block
of memory that represents 'e' didn't change size. So sizeof(e) ==
sizeof(EXAMPLE) == 4.

strings, lists, vectors, and in fact any other sort of container you
could find or dream up will do essentially this same thing. As it needs
more memory, it will allocate it dynamically *somewhere*, but all it
will keep is a pointer to where it allocated that memory. In fact,
there isn't actually anything you CAN do to change the size of a
structure. It turns out that sizeof() really isn't even a function at
all, but instead gets evaluated by the compiler at compile time.

Now consider a second structure:
struct EXAMPLE2
{
int i ;
std::vector<int> v ;
std::string s ;
std::list<int> l ;
} ;

How big is this structure? Well, that depends on what exactly the
members of a vector, string, and list are. On my particular compiler
that structure requires 24 bytes. Now I can add and remove things from
the vector, string, and list as much as I like and still be safe in the
knowledge that the size of the structure is 24 bytes. That doesn't mean
that more memory isn't getting allocated and deallocated somewhere. It
is, and part of the 24 bytes that make up my structure are pointers to
all that memory, but it will never change the fact that my structure is
only 24 bytes.

Alan

Jul 22 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.