SImple question about structure and linked list

[John]

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

 

[Gregg]

(e-mail address removed) (John) wrote in

Hi all,

Can a linked list be a member of a structure?

Yes, e.g.

struct S {

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

 

[E. Robert Tisdale]

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

 

[Karthik]

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

 

[Alan Johnson]

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

 

[John]

Thanks Alan. I understand now.

John

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