Computer Science Canada

[Tutorial] Pointers
Author:  lyam_kaskade [ Mon Jun 20, 2005 12:32 am ]
Post subject:  [Tutorial] Pointers
Looking through the Turing Walkthrough, I noticed at the end Cervantes mentioned something about not having one about pointers. So here goes.

Quote:

Description: A variable declared as a pointer type is used to locate an element of a collection or class or a value of a type. The new statement creates a new element (or value) and places the element's location in a pointer variable. The free statement destroys an element located by a pointer variable.


Now, you may be thinking the same thing i did at first. Just wth does that mean? A pointer is a reference to an element of a class/collection. Let's start with an example.

code:

var list : collection of
    record
        num : int
        next : ^list
    end record

var root : ^list
new list, root
var temp : ^list
var ref : ^list %reference

ref := root
for i : 1 .. 100

    new list, temp
    ref -> next := temp
    ref -> num := i
    ref := temp

end for

ref := root
for i : 1 .. 100
    put ref -> num
    ref := ref -> next
end for


This code creates a linked list. What's a linked list? Well, I'm glad you asked. A linked list is a collection of variables where each variable is linked to the next variable through the use of a pointer.
Let's go through the code.

code:

var list : collection of
    record
        num : int
        next : ^list
    end record


This creates a collection called list. Each element in the collection contains an integer called num, and a pointer called next (next can also be typed as next: pointer to bar).

code:

var root : ^list
new list, root


This creates a reference (link) called root to the first element in our linked list. We use this to start off the list.

code:

var temp : ^list
var ref : ^list %reference


These two are variable pointers to be used later.

code:

ref := root
for i : 1 .. 100
    new list, temp
    ref -> next := temp
    ref -> num := i
    ref := temp
end for


ref starts as root, the first element in our linked list. To create a new element in the list, we use the new command.
We set ref to point to our new element, temp.
Then we assign the integer value of i to num in ref.
Finally, ref is assigned to the next value in the list, which is now temp. The loop repeats to 100.

It is important to keep in mind that root, ref, and temp are NOT variables of type list. They are references to different elements in the collection. When ref is assigned to temp it does NOT change the value of that part of the collection, it changes the value of ref, which simply points to a new part of the list.

code:

ref := root
for i : 1 .. 100
    put ref -> list
    ref := ref -> next
end for


Now, to show that it works, we display the list in order, starting at root. ref is displayed and then assigned to the next value.

You may be wondering what the value of a linked list really is. Why not just use an array?
Well, there are plenty of reasons.

Linked lists can be resized. Okay so you can use a flexible array for that, but in any case it's done like this:

code:

var DEL:^list %element in the list to be deleted
var foo:^list:=DEL->prev
var bar:^list:=DEL->next

foo->next:=bar
bar->prev:=foo


or simply
code:

DEL->prev->next:=DEL->next
DEL->next->prev:=DEL->prev

ANd that's it. The element is gone from the list.

Linked lists can (as shown above) have more than one pointer. This means flexible, two dimensional lists. Here's an adaptation of the first program to demonstrate:

code:

var bar : collection of
    record
        foo : int
        next : ^bar
        out : ^bar
    end record

var root : ^bar
new bar, root

var temp, temp2 : ^bar
var X : ^bar
var Y : ^bar

X := root
for i : 1 .. 100
    Y := X
    for j : 1 .. 10
        new bar, temp2
        Y -> out := temp2
        Y -> foo := j * i
        Y := temp2
    end for
    new bar, temp
    X -> next := temp
    X := temp
end for

X := root
for i : 1 .. 100
    delay (100)
    put X -> foo
    Y := X
    for j : 1 .. 9
        delay (100)
        Y := Y -> out
        put Y -> foo : 10
    end for
    X := X -> next
end for


With a linked list, you can also create something called a binary tree:

code:

var bar : collection of
    record
        foo : int
        left : ^bar
        right : ^bar
        parent : ^bar
    end record


Every element in the collection will have a pointer to two other elements below it, and it's parent element above it. There are numerous uses of binary trees, but I've used too much space here as it is, so I will finish this.

This is my first tutorial, so if you hate it, then please explain why as opposed to simply flaming. If I should go into more depth somewhere then I will. And that's all. Feel free to add anything.
Author:  Tony [ Mon Jun 20, 2005 1:20 am ]
Post subject: 
thank you for reposting the tutorial and better yet -- fixing variable names Smile you missed one though :: new bar, temp , I think bar is supposed to be a list..

I'll be restoring your bits now
Author:  riveryu [ Fri Mar 07, 2008 7:30 pm ]
Post subject:  RE:[Tutorial] Pointers
I dont see an actual application of pointers from reading your tutorial. Perhaps you should give some examples... Im n00b
Author:  mirhagk [ Tue Jul 03, 2012 8:11 am ]
Post subject:  RE:[Tutorial] Pointers
Linked lists are one of the few actual applications of pointers. Modern languages try to shy away from pointers as much as they can, as the applications for pointers are usually replaced by other things (OOP, delegates/lambdas/anonymous functions/code blocks).

Linked lists could also be done with objects, but in turing they are pretty much the same thing, because turing's oop is terrible.
Author:  Insectoid [ Tue Jul 03, 2012 5:06 pm ]
Post subject:  RE:[Tutorial] Pointers
mirhagk, how do you think delegates, lambdas, and anonymous functions are implemented? Pointers! A linked list that uses objects still uses pointers. It just puts them inside the object. Pointers/references are essential in assembly (x86 assembly anyway), so really, every language uses them. If a particular language has chosen to abstract pointers away from the user, that doesn't mean they're gone.

If you choose to use C or C++ you'll find pointers indispensable, and absolutely not limited to linked lists. I rarely write a program without plenty of pointers.
Author:  mirhagk [ Tue Jul 03, 2012 10:41 pm ]
Post subject:  RE:[Tutorial] Pointers
My point wasn't that pointers can't be used, just that higher level languages replace them with higher level abstractions of pointers.

I used C++ for a long time, and I was glad to get rid of pointers. Pointers are ugly, unsafe, prone to memory violations, and hard to understand. A language that allows you to have pointers, but avoids them in every scenario is best. That way naive programmers who don't know the better high level way, or who care about reducing the k value in a kn^2 algorithm can use them, while not forcing anyone else to use them (C# does this, I believe java does as well)

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy