[Tutorial] Pointers

[lyam_kaskade]

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.

[Tony]

thank you for reposting the tutorial and better yet -- fixing variable names you missed one though :: new bar, temp , I think bar is supposed to be a list..

I'll be restoring your bits now

[riveryu]

I dont see an actual application of pointers from reading your tutorial. Perhaps you should give some examples... Im n00b

[mirhagk]

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.

[Insectoid]

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.

[mirhagk]

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)