A Look at Arrays

Welcome to my blog on Perl. I'm starting it by reposting an article I wrote from blogs.perl.org: 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.