A Look At Arrays
A Look At Arrays
Perl's built-in datatype, array, is a multi-purpose tool which can be used for many things. It's primary purpose is to preserve the order of data. But it comes with a powerful set of tools to make manipulating it easy. This article is to show how to use these tools by implementing a linked list.
Linked lists were originally created for languages like C which only had simple datatypes. They are a technique for using the system's memory allocation to create a data structure that allows unlimited expansion, that is, until it runs out of memory. They use a simple datatype called a pointer that records a position in memory. Without pointers, linked list would be impossible.
Perl has a datatype similar to pointers, the reference. Like pointers, it records a memory location and it can be used link them. But using references to implement a linked list the same way one would do in C, needlessly complicates the code. Linked lists can be implemented using just arrays. Here's how.
The Difference Between an Array and a List
Perl makes a distinction between an array and a list. An array is a datatype and has permanent storage for its contents. This allows a reference to be made to it. A list is a temporary structure and cannot be referenced. Lists are used both as parameters to a subroutine and their returned values. And lists can be assigned to arrays and hashes to store their values.
Simple Manipulations
Creating a Linked List
Simply declare an array using my
or our
.
my @list = ();
Clearing a Linked List
Clear the array by assigning the empty list to it.
@list = ();
Add an Item to the End of the List
Use the push
command to addend the item to the end of
the array.
push @list, $item;
Add an Item to the Front of the List
The unshift
command will insert the item at the
beginning of the array.
unshift @list, $item;
Remove an Item to the End of the List
The pop
command will remove an item from the end
of the array.
$item = pop @list;
Remove an Item to the Front of the List
The shift
command will remove an item from the
beginning of the array.
$item = shift @list;
Checking for an Item in the List
To check if an item is in a list, use first
from List::Util
. List::Util
is a
standard Perl module and is installed with Perl. For a list of all the
standard modules and pragmatics, see perlmodlib
.
use List::Util qw( first ); $found = defined( first { $_ eq $item } @list );
The test inside the block may be replaced with a match. Any valid pattern may be used.
$found = defined( first { /^$item$/i } @list );
Counting the Occurrences of an Item in the List
To count the occurrences of an item in a list, use grep
.
$count = grep { $_ eq $item } @list;
The test inside the block may be replaced with a match. Any valid pattern may be used.
$count = grep { /^$item$/i } @list;
Reverse the List
A list can be reversed with the reverse
command.
@list = reverse @list;
Rotate the List Forward
An array can be rotated by combining the shift
and
push
commands.
push @list, shift @list;
Rotate the List Backward
An array can be rotated backward by combining the pop
and
unshift
commands.
unshift @list, pop @list;
Extracting the i-th Item
Extracting a single item from a list can be done by indexing the position in the list.
$item = $list[$i];
Replacing the i-th Item
An item can be replacing with indexing.
$list[$i] = $item;
Extracting a List of Items
To extract a list of items from the i-th to j-th position
inclusive, use a slice
.
@items = @list[ $i .. $j ];
Replacing a List of Items
Items can be replaced by assigning them to a slice.
@list[ $i .. $j ] = @items;
The range of items from the i-th to the j-th position
inclusive will be replaced. If @items
is longer than the
range, those left over will be ignored. If it is shorter,
undef
will be place in @list
.
Using
splice
Although slices can be used to replace items in a list, it will not
remove them. Use Perl's splice
command for this.
Removing Items from a List
Removing a number of items starting in the i-th position of list. The list will shrink in size by the number of items removed.
@removed_items = splice( @list, $i, $number );
Inserting Items into a List
Inserting a number of items starting in the i-th position of list. The list will grow in size by the number of items inserted.
splice( @list, $i, 0, @items );
Replacing Items With a List of Others
Replacing a number of items with others starting in the i-th position. The list will grow or shrink to accommodate the new items. The removed items can be saved.
@saved_items = splice( @list, $i, $number, @new_items );
Conclusion
Perl's array datatype has powerful tools that can be used for many tasks.
This is a fantastic article on the basic building blocks you use everyday.
It's very useful for someone like me, without a background in computer science. I had only a vague idea of what a "linked list" was.
Looking forward to more :)
Perl arrays are not implemented using linked lists. See PerlGuts Illustrated.
@Brad: I never said they were. I said a linked list can be implemented using only an array. You got them the wrong way around.