Notes 0005

Perl Data Structures (Continued)

We've already discussed how to use Perl's built in data structures, like arrays/lists and hashes (and to create combinations of them - like arrays of hashes and hashes of arrays). In these notes, we shall do more obscure things like linked lists.

Linked Lists

How exactly do we do a linked list? Well, we have several options. Somehow, we must represent the node, and since we haven't dealt with Object Oriented programming yet, we'll have to compromise and use Perl's simpler types. So lets say our node will be an array.

The first element of this array shall be the data value, and the second element of this array shall be the link to the next 'node'.

Given this, we can easily create a linked list of numbers:

for($i=0;$i<10;$i++){
   $list = [$i,$list];
}

This creates a linked list:

[9]->[8]->[7]->[6]->[5]->[4]->[3]->[2]->[1]->[0]->undef

To see how this works, notice that $list is initially undefined (undef), so the first node that gets created is [0,undef], and $list is a reference to that 'node'. The second node that gets created is [1,$list] where $list is a reference to the first node, and after the assignment, $list points to the second node, and so on until we hit node ten.

To traverse such a list, we simply loop though the 'nodes'.

$iterator = $list;
while($iterator){
   print "$iterator->[0] ";
   $iterator = $iterator->[1];
}
print "\n";

Notice that we could have used the $list reference directly, but then we would have lost the reference to the list; so instead, we create a temporary scalar named $iterator (we could have named it anything we like), and use that inside our loop.

The while loop would terminate as soon as $iterator hits the value of undef (kind of like a NULL in C language).

The $iterator->[1] code is just a shorthand for ${$iterator}[1] where $iterator is a reference to an array.

The output is the expected:

9 8 7 6 5 4 3 2 1 0

More on Linked Lists

What if we don't really feel like using an array for the nodes? What if we don't want to remember that [0] is the data and [1] is the reference to the next array? Well, we could use a hash!

Check out this code:

for($i=0;$i<10;$i++){
   $list = {value=>$i,next=>$list};
}

Notice that this is essentially the same code as above, except that instead of making references to arrays, it makes references to hashes. With each hash, the value name points to the 'value' of the 'node' (which is a hash now), and the next points to the next 'node' in the list.

The traversal of this type of a list is also similar:

$iterator = $list;
while($iterator){
   print "$iterator->{value} ";
   $iterator = $iterator->{next};
}
print "\n";

This is nearly identical code to the array implementation, except it is much easier to read.

More to Come

My original plans included covering recursive data structures (like trees, etc.) as well, but I've decided to do that a bit later in the semester due to the fact that we haven't talked about subroutines yet (and you kind of need those for recursion). [we could do all these things with a stack, but recursion is much simpler]. So we are not done with data structures, and will get back to them as soon as we learn more of the language to proceed further.

© 2006, Particle