May 2012 Archives
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.