Linked Lists

This is a discussion on Linked Lists within the C Programming forums, part of the General Programming Boards category; I have a doubt about linked lists.. Memory for structure variables are allocated only when they are declared.right.... Look at ...

  1. #1
    Registered User linuxlover's Avatar
    Join Date
    Nov 2010
    Location
    INDIA
    Posts
    52

    Smile Linked Lists

    I have a doubt about linked lists..

    Memory for structure variables are allocated only when they are declared.right....
    Look at this

    Code:
    struct stud
               {
                          int a;
                          struct stud* next;
                }s;
    memory is allocated for s as it is declared.But again s contains another structure variable declaration (struct stud* next.This can hold a pointer to a variable of type struct stud..
    so its size is that much to hold that variable...Since it is a structure variable Its memory is allocated when it is declared using that statement.That pointer should point to another variable of struct stud.So Again that variable contains another declaration and this allocates memory again....This process continues..............

    So then what is the size of the variable s.

    Is the memory size of an address is specified by OS.Or is it item specific(ie. memory required to hold address of int variable and char variable are different.Or are they same.?
    If same my doubt is cleared...

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    A pointer is not an entire structure, it is just the address of where that structure would reside and it has a fixed size (something like an int).

    If you want to check you can print (int)sizeof(struct node*) to check how big the pointer is.

    So your struct contains an integer (uninitialized) and a an address of another struct (uninitialized).
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    Quote Originally Posted by linuxlover
    So then what is the size of the variable s.
    The size of an int and a pointer to struct stud, with possible padding (though that is probably not needed here).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User linuxlover's Avatar
    Join Date
    Nov 2010
    Location
    INDIA
    Posts
    52
    Quote Originally Posted by claudiu View Post
    A pointer is not an entire structure, it is just the address of where that structure would reside and it has a fixed size (something like an int).

    If you want to check you can print (int)sizeof(struct node*) to check how big the pointer is.

    So your struct contains an integer (uninitialized) and a an address of another struct (uninitialized).
    Is size of an address is specified byOS.ie is it same for every type of variable.Is it same as the number of address lines of CPU.For ex: if 16 address line ,then address takes two bytes for every type of variable?Am I correct?

  5. #5
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,175
    Pointers to different types have always been the same size in my experience, but I don't think it's guaranteed to be that way by the C standards. There might be an environment out there that doesn't behave that way. Best practice is to check the size of the pointer type you actually need.
    If you understand what you're doing, you're not learning anything.

  6. #6
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by linuxlover View Post
    Is size of an address is specified byOS.ie is it same for every type of variable.Is it same as the number of address lines of CPU.For ex: if 16 address line ,then address takes two bytes for every type of variable?Am I correct?
    I agree with what "itsme" posted.

    Pointers should generally be the same size since the size of the pointer should be relative to the size of the memory on the system, but I am not sure this is specified anywhere in the C standard. In fact, come to think of it, I am pretty sure it isn't.

    The key thing here is to be able to tell the difference between data and a pointer to data, which is just the address of where some of that data resides. Lists are confusing to beginners for the same reason you pointed out: it initially looks like a structure holds another structure, which holds another structure, etc. In fact it only holds an address of another structure, which is of finite determinable size.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Pointer sizes are generally determined by the architecture, not the OS (though I imagine a 32-bit OS on a 64-bit system would produce 32-bit pointers). A 32-bit processor usually has a 32-bit data bus and a 32-bit address bus (this is not always true, but typical in modern desktop processors). Thus, the size of a pointer variable should be 32 bits, or 4 bytes. Like itsme and claudiu, I've never seen 2 different sized pointers, and I'm not sure that that would make sense under most circumstances (anybody have anything to say about far pointers in DOS? I don't remember how they work). Suffice to say, if you use sizeof(some_pointer_variable) instead of hard coding it, you shouldn't care what it is. Let your compiler figure out how much space it needs for this stuff...that's part of it's job.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists?!
    By hwing91 in forum C Programming
    Replies: 32
    Last Post: 11-08-2010, 06:13 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 05:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 09:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 07:25 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21