[prog] C++ - linked list and segmentation fault

[Mary]

On Tue, Apr 08, 2003, Jennifer Davis wrote:
> I am having so much trouble getting my head around pointers in general
> and linked lists in particular.

Other people have posted good advice about linked list, so here's a
general overview of C's pointers. I don't cover a shred of C++ here, but
the ideas are common to both languages.

I'm posting this because I never *really* understood pointers until I
knew about this. (I found learning an assembly language helped with
this, but perhaps that's because I was never taught this explicitly -
assembly languages force you to know this stuff.)

Think of an ordinary variable as a piece of memory with a name.

imagine a piece of code that looks like:

int c = 6;

This allocates a piece of memory, integer-sized, puts the value 6 in it,
and calls it 'c':

-------
|     | < -- a piece of memory that can be refered to by the name 'c'.
|  6  |
-------

Now a pointer is also a space in memory, but instead of having a value
in it, it has a memory address:

int* ptr = &c; // store the memory address of the c variable (&c) in an 
               // integer pointer called ptr

Imagine that the memory we labeled c is at address 0x66F in our system
(memory addresses are normally represented in hex format, hence the
0x66F).

Now we have:

-------
|     | < -- a piece of memory that can be refered to by the name 'c'.
|  6  |
-------

-------
|     | < -- a piece of memory that can be refered to by the name 'ptr',
|0x66F|      and which is storing the memory address 0x66F, which
-------      happens to be where 'c' is.

Now, why bother with this storing of memory addresses? A number of
reasons.

First, an introduction to how memory is managed.

I have a program that looks like this:

int square(int x) {
        return x * x;
}

int main() {
        int a, b;
        a = 6;
        b = square(a);
}
 
Programs are run in the execution stack, which I'll go through line by
line:

int main(){
        int a, b;

*** space is created on the stack for main's a and b variables:

-------
|     | < -- a piece of memory that can be refered to by main using the
|     |      name 'a'
|     |
-------
-------
|     | < -- a piece of memory that can be refered to by main using the
|     |      name 'b'
|     |
-------

        a = 6;

*** store 6 in 'a', now the stack looks like:

-------
|     | < -- a piece of memory that can be refered to by main using the
|  6  |      name 'a'
|     |
-------
-------
|     | < -- a piece of memory that can be refered to by main using the
|     |      name 'b'
|     |
-------

        b = square(a);

int square(int x){

*** a function has been called, so space for its variables is created on
*** top of the stack
-------
|     | < -- a piece of memory that can be refered to by square using the
|     |      name 'x'
|     |
-------
-------
|     | < -- a piece of memory that can be refered to by main using the
|  6  |      name 'a'
|     |
-------
-------
|     | < -- a piece of memory that can be refered to by main using the
|     |      name 'b'
|     |
-------

*** additionally, since we passed 'a' as an argument to the square
*** function, and square's first argument is named 'x', the value of
*** 'a' is *copied* into x

-------
|     | < -- a piece of memory that can be refered to by square using
|  6  |      the name 'x'
|     |
-------
-------
|     | < -- a piece of memory that can be refered to by main using the
|  6  |      name 'a'
|     |
-------
-------
|     | < -- a piece of memory that can be refered to by main using the
|     |      name 'b'
|     |
-------

               return x * x;
               }

               b = square(a);

*** square computes x*x and returns it, and ends. when it ends, its
*** return value (36 in this case) is made available to the calling
*** function main, and its variables are removed from the stack

*** main stores the return value in b, so now our stack looks like:

-------
|     | < -- a piece of memory that can be refered to by main using the
|  6  |      name 'a'
|     |
-------
-------
|     | < -- a piece of memory that can be refered to by main using the
|     |      name 'b'
| 36  |
-------

Now, C can only figure out how much memory to add to the stack if it can
figure out how big the variable is at the time of compilation. Standard
types int, char, float etc have known sizes, and a constant array like
int[300] is just 300 ints all in a row, so these can all be added to
("allocated on") the stack.

IMPORTANT NOTE: the space a pointer takes up is also known, because a
pointer is just a memory address, and the size of memory addresses on a
particular architecture is known to the compiler.

But you'll often encounter situations where, for example, the size of an
array is unknown until the program is actually *run*. What happens then?

Well, in this case, the program doesn't know in advance how much memory
to add to the stack. But there is a second place where you can get
memory, and it's called the 'heap'. Your program gets memory from the
'heap' when it calls 'malloc' 'calloc' 'realloc' and their cousins.

In this situation, you take advantage of the fact that pointers have
known sizes, so a pointer gets allocated on the stack, and you call
malloc/calloc etc and use that pointer to point off into the heap.
(C++'s 'new' operator doesn't behave quite like this, it not only
allocates memory in the heap, it also runs constructors and so on).

Compare:

int main(){
        int[100] a;

}

with:

# include <malloc.h>

int main(){
        int* a = (int*) malloc (sizeof(int)*100);
}

the first main makes 100 ints, all on the stack. the second calls malloc
to make 100 ints all on the heap (and in sequential bits of memory too,
say addresses 0x10, 0x11, 0x12, 0x13 etc etc...), and malloc returns the
memory address of the first of the 100 ints (address 0x10, say).

So the first function has stack with 100 ints in it, the second has a
stack that looks like:

-------
|     | < -- a piece of memory that can be refered to by main using the
|     |      name 'ptr', that contains a memory address of something in
|0x10 |      the heap
-------

And if your program wants to access those 100 ints, it can get the
address from ptr.

Some messiness: Anything in the stack also has a memory address, and
pointers can point to other places in the stack, as well as in the heap.
Also, if you don't know how many *pointers* there are going to be (as in
a linked list, where every node has its own pointer, and you don't know
the size of the linked list at compile time), you can also allocate
space for pointers themselves from the heap. However, if you want to be
able to find something, ultimately the stack needs to contain it, or
point to it, somehow.

A note on the heap: It's memory from the heap that needs to be freed
using 'free' or C++'s 'delete'. If you do not free it, and your stack
eventually doesn't contain any pointers to it, the operating system will
keep it marked as belonging to your process, rather than allowing other
processes to use it. This is how "memory leaks" happen in longrunning
processes. The rule is "anything that got malloced must be freed", and
"anything that got new-ed (in C++) must be deleted".

Finally, most programming languages (Basic, Java, Python, Perl etc etc)
hide this detail from you, which is why there's no pointers in Basic.
This normally costs either some memory, or some processing time where
the program runs around cleaning up memory (a process known as "garbage
collection") whenever it thinks it should. For many programming
purposes, this is sufficient. For the ultimate in speed, the fine-grained
control that C and C++ offer can be worth it - although both have longer
development cycles and a whole slew of pointer related bugs and crashes
that other programming languages spare you.

-Mary