Welcome, Guest! Login | Register

Dynamic Data Structures (Part 1): Pointers [Print this Article]
Posted by: rkzad
Date posted: Jun 18 2003
User Rating: 5 out of 5.0
Number of views: 5271
Number of comments: 3
Description: To start out, teaches what pointers are and how to use them.
Introduction
Well I'm hoping to make a series of articles on dynamic data structures, getting more complicated as we go along. The point of these articles is to show you the different types of dynamic data structures you can use that will be applicable to all sorts of programs, and more importantly how to implement them, and when to use which one. To begin with, since we're in part 1, we should start off with a definition of dynamic data structures.

What is a Dynamic Data Strucutre?
A dynamic data structure is a data structure that is not of a set size. In other words, it can grow and shrink over the course of our program. In order to achieve this, the program will dynamically allocate memory as it needs it, and will deallocate (free) it when it's done. The advantage with this over static data structures (such as a simple array) is that you only use up the memory you need, while a simple array will always be N spaces big, even if you're only using 1/100th of them.

Pointers
Now all dynamic data structures require pointers in some way, since we're dynamically allocating and freeing memory. Since pointers take a long time to explain, part 1 will be devoted to pointers.

Okay, here's the first thing you have to know. Your computer has memory. I'm not talking about hard drives, I'm talking about your RAM. When you open a program, it is copied into your RAM and ran from there. RAM is much faster than your hard drive, but much smaller, however of course as the years go on, we're getting more RAM, with the latest motherboards offering the capability for up to 3gb of RAM. Wow. So anyways, back to addresses. To keep it simple, an address is simply a location in memory. For instance, your address could point at the 1024th byte of memory. It's like each house has their own address, and you can give somebody your house address and they can find you. This is all that a pointer stores: the address. That's the only data a pointer can store. However, pointers let you store the address to say an int. The code for this would be:
 CODE (C++) 
int num = 3;
int *ptr = #
Now if you've never worked with pointers before, the second line might blow your mind away. The * simply means it's a pointer. In this case, it's a pointer to an int variable. The next different part is the & symbol. This gets the address of a variable. So "&num" would simply equal the address of "num".

So now that you have the addres of "num" stored in "ptr", what can you do now? Check out this code:
 CODE (C++) 
int num = 3;
int *ptr = #
 
*ptr = 16;
printf("%d", num);
Guess what? This code actually prints the number 16. Crazy, no? Now this new line "*ptr = 16;" can be kind of confusing. You used * on the second line to declare ptr as a pointer, but then you used it again to set num to 16.

After declaration, you can use * to dereference a pointer. What this means is that if you have:
int *ptr = #
then
ptr == &num
and
*ptr == num

In other words, ptr will still equal the address of the variable, since that what a pointer does: stores the address of a variable. However, when you add a * to the beginning of ptr, it will now act as whatever it is pointing too.

 CODE (C++) 
int a = 1;
int b = 2;
int *ptr = &a;
 
*ptr = 2;
ptr = &b;
*ptr = 1;


The above code shows an example of how you would use ptr to change the value of the variable it is pointing to, and how to change which variable it is pointing to. After this code, a=2 and b=1.

At this point in time, pointers may seem pretty useless. But here is one thing that is helpful about pointers: take the following code:
 CODE (C++) 
void Calc1(int b)
{
    ++b;
}
 
void Calc2(int *ptr)
{
    ++(*ptr);
}
 
void main()
{
    int a = 2;
    Calc1(a);
    Calc2(&a);
}
I know, this code is not useful at all, but it is just to show you something. At the end of the main function, a will equal 3. This is because Calc1 does not change the value of a inside the main function. It will change the value of b inside Calc1, but since b is a new variable at a new location, it will not affect a. However, Calc2 takes in the address of a, and sets ptr to the address of a. Now Calc2 knows the address of a, unlike Calc1. So we can dereference ptr and increment the value of a.

Allocating and Freeing Memory
Okay now for the dynamicness (new word). In our dynamic data structures, we want to be able to dynamically create memory for us to use. You would need to do this when we want to insert new data into the data structure, or to resize our data structure.

There are two novel (had to use thesaurus for an alternative to the word new) operators that we'll be using for this: new and delete. new allows you to create an object or an array, while delete gets rid of it, and puts it back in the free store. Beware of this though: Always delete what you make new when you're done with it. Otherwise you're leaking memory, and wasting memory.

So here's an example of using new and delete:
 CODE (C++) 
int *ptr = new int;
*ptr = 1;
printf("%d", *ptr);
delete ptr;
That simply prints "1". Now see we don't have to create an "int a" just to have ptr point to something.

Allocating and freeing an array is essentially the same, just a few brackets here and there.
 CODE (C++) 
int  *pArray = new int[5];
 
// then to delete
delete []ptrArray;


If you want to create an array with two dimensions, you'll have to do this:
 CODE (C++) 
// 'int **' means a pointer to an integer pointer. We need to do this to make a 2-dimensional array
int **ppArray = new *int[5];    // Create an array of integer pointers.
 
// For each integer pointer, create an array of integers.
for (int i = 0; i < 5; ++i)
    ppArray[i] = new int[10];

// We now have a 5x10 array of integers in ppArray.
 
// To delete, we first delete each of our integer arrays
for (int i = 0; i < 5; ++i)
    delete []ppArray[i];
// Wow that line is confusing isn't it? The first [] means we're deleting an array.
// The [i] means which element in ppArray we're deleting.
 
// Then we delete the array of integer pointers.
delete []ppArray;


I'll get into applications of pointers in the next parts. I was originally going to make the first part on dynamic data structures, but I turned out to write too much on pointers I may as well make it a seperate article. If you have questions, please post on the General Programming forum. If you notice any mistakes or things I should change in the article, please e-mail me at rkzad@hotmail.com.

Don't worry, the next part will actually have a dynamic data strucutre user posted image

Rate This Article
This article is currently rated: 5 out of 5.0 (4 Votes)

You have to register to rate this article.
User Comments Showing comments 1-3

Posted By: De KoFfieŠ on Sep 14 2003 at 10:09:44
Thanks a lot for this excellent tutorial!
Cleared a few things up for me!

Posted By: SilentSounD on Nov 04 2004 at 06:22:08
Great Job rkzad! This article has been very informative.

Posted By: anty on Jul 06 2005 at 21:17:10
very good examples, good explenations!
This is, how good tutorials (about basic coding) should be!
thank you very much!


You must register to post a comment. If you have already registered, you must login.

Latest Articles
3rd person View in Multiplayer
Half-Life 2 | Coding | Client Side Tutorials
How to enable it in HL2DM

By: cct | Nov 13 2006

Making a Camera
Half-Life 2 | Level Design
This camera is good for when you join a map, it gives you a view of the map before you join a team

By: slackiller | Mar 05 2006

Making a camera , Part 2
Half-Life 2 | Level Design
these cameras are working monitors that turn on when a button is pushed.

By: slackiller | Mar 04 2006

Storing weapons on ladder
Half-Life 2 | Coding | Snippets
like Raven Sheild or BF2

By: British_Bomber | Dec 24 2005

Implementation of a string lookup table
Half-Life 2 | Coding | Snippets
A string lookup table is a set of functions that is used to convert strings to pre-defined values

By: deathz0rz | Nov 13 2005


Latest Comments
knock knock
General | News
By: omega | Dec 22 2016
 
knock knock
General | News
By: MIFUNE | Oct 10 2015
 
New HL HUD Message System
Half-Life | Coding | Shared Tutorials
By: chbrules | Dec 31 2011
 
knock knock
General | News
By: Whistler | Nov 05 2011
 
Particle Engine tutorial part 4
Half-Life | Coding | Client Side Tutorials
By: darkPhoenix | Feb 18 2010
 
Particle Engine tutorial part 2
Half-Life | Coding | Client Side Tutorials
By: darkPhoenix | Feb 11 2010
 
Particle Engine tutorial part 3
Half-Life | Coding | Client Side Tutorials
By: darkPhoenix | Feb 11 2010
 
Game Movement Series #2: Analog Jumping and Floating
Half-Life 2 | Coding | Shared Tutorials
By: mars3554 | Oct 26 2009
 
Particle Engine tutorial part 5
Half-Life | Coding | Client Side Tutorials
By: Deadpool | Aug 02 2009
 
Particle Engine tutorial part 5
Half-Life | Coding | Client Side Tutorials
By: Persuter | Aug 02 2009
 

Site Info
297 Approved Articless
8 Pending Articles
3940 Registered Members
0 People Online (9 guests)
About - Credits - Contact Us

Wavelength version: 3.0.0.9
Valid XHTML 1.0! Valid CSS!