NAME

LinkedList::Single - singly linked list manager.

SYNOPSIS

# generate the list with one value from @_ per node
# in a single pass.

my $listh   = LinkedList::Single->new( @one_datum_per_node );

# generate an empty list.

my $listh   = LinkedList::Single->new;

# each node can have multiple data values.

$listh->push( @multiple_data_in_a_single_node );

# extract the data from the current node.

my @data    = $listh->data;

# save and restore a node position

my $curr    = $listh->node;

# do something and restore the node.

$list->node( $curr );

# note the lack of "pop", it is simply too
# expensive with singly linked lists. for 
# a stack use unsift and shift; for a que
# use push and shift (or seriously consider
# using arrays, which are a helluva lot more
# effective for the purpose).


$list->push( @node_data );

my @node_data   = $list->shift; # array of values
my $node_data   = $list->shift; # arrayref

# these manipulate the head node directly
# and to not modify the current list.

$listh->unshift( @new_head_node_data );

my @data    = $listh->shift;

# sequences of pushes are effecient for adding
# longer lists.

my $wcurve  = LinkedList::Single->new;

while( my $base = substr $dna, 0, 1, '' )
{
    ...

    $wcurve->push( $r, $a, ++$z );
}

# reset to the start-of-list.

$wcurve->head;

# hide extra data in the head node.

$wcurve->set_meta( $z, $species );

# extra data can come back as a list
# or arrayref.

my ( $size )    = $wcurve->get_meta;


# walk down the list examining each item until 
# the tail is reached.
#
# unlike Perl's each there is no internal
# mechanism for re-setting the current node,
# if you don't call head $listh->each returns
# immediatley. 

$listh->head;

while( my @data = $listh->each )
{
    # play with the data
}

# duplicate a list handler, reset it to the 
# start-of-list.

if( $some_test )
{
    # $altlist starts out with the same node 
    # as $listh, call to next does not affect
    # $listh.

    my $altlist = $listh->clone;

    my @data    = $altlist->next->data;

    ...
}


# for those do-it-yourselfers in the crowd:

my $node    = $listh->root;

while( @$node )
{
    # advance the node and extract the data
    # in one step.

    ( $node, @data )    = @$node;

    # process @data...
}

# if you prefer OO...
# $listh->each returns each value in order then
# returns false. one catch: in a list context
# this will return equally false for an empty
# node as the end-of-list.
#
# in a scalar context each returns false for the
# end-of-list and an empty arrayref for a node.

$listh->head;

while( my $data = $listh->each )
{
    # deal with @$data
}

# if you *know* the nodes are never empty

while( my @data = $listh->each )
{
    # deal with @data
}

# note that $listh->next->data may be empty
# even if there are mode nodes due to a node
# having no data.

$listh->add( @new_data );

my @old_data    = $listh->cut;

# $listh->head->cut is slower version of shift.

DESCRIPTION

Singly-linked list managed via ref-to-scalar.

Nodes on the list are ref-to-next followed by arbitrary -- and possibly empty -- user data:

my $node    = [ $next, @user_data ].

The list handler can reference the list contents via double-dollar. For example, walking the list uses:

$$listh = $$list->[0]

this allows $listh to be blessed without having to bless every node on the list.

Methods

new construct initialize

New is the constructor, which simply calls construct, passes the remaining stack to initialize, and returns the constructed object.

initialize is fodder for overloading, the default simply adds each item on the stack to one node as data.

construct should not be replaced since it installs local data for the list (its head).

clone

Produce a new $listh that shares a head with the existing one. This is useful to walk a list when the existing node's state has to be kept.

my $clone   = $listh->clone->head;

while( my @valz = $clone->each )
{
    # play with the data
}

# note that $listh is unaffected by the 
# head or walking via each.

set_meta add_meta get_meta

These allow storing list-wide data in the head. get_meta returns whatever set_meta has stored there, add_meta simply pushes more onto the list. These can be helpful for keeping track of separate lists or in derived classes can use these to provide data for overloading.

has_nodes has_next is_empty 'bool'

has_nodes is true if the list has any nodes at all; has_next is true if the current node has a next link.

The boolean overload is true if the current node has a next link (i.e., if calling $listh->next will go anywhere).

sub walk_the_list
{
    my $listh   = shift;

    $listh->has_nodes
    or return;

    $listh->head;

    while( $listh )
    {
        # deal with the data in this node
    }
    continue
    {
        $listh->next;
    }
}

data set_data clear_data

These return or set the data. They cannot be combined into a single method because there isn't any clean way to determine if the node needs to be emptied or left unmodified due to an empty stack. The option of using

$listh->data( undef )

for cleaning the node leaves no way to store an explicit undef in the node.

node

Set/get the current node on the list.

This can be used for tell/seek positioning on the list.

my $old = $listh->node;

$listh->head;

...


$listh->node( $old );

Note that setting a new position returns the new position, not the old one. This simplifies re-set logic which can simply return the result of setting the new node.

This is also the place to get nodes for processing by functional code or derived classes.

root head_node

These return the internal data (root) or first data node (head_node).

head_node is useful for anyone whthat wants to walk the list using functional code:

my $node    = $listh->head_node;
my @data    = ();

for(;;)
{
    @$node  or last;

    ( $node, @data ) = @$node;

    # play with @data.
}

moves the least amount of data to walk the entire list.

root is mainly useful for intenal code or derived classes. This is used by all methods other than construct, DESTROY, clone, and root to access the list's head. Derived classes can override these methods to use another form of storage for the list root.

head next each

head and next start the list at the top and walk the list.

each is kinda like Perl's each: it returns data until the end-of-list is reached. It makes no attempt, however, to initialize or reset the list, only walk it.

Called in a scalar context this returns an arrayref with copies of the data (i.e., modifying the returned data will not modify the node's data). This is a feature.

When the data is exhausted an empty list or undef are returned. If your list has empty nodes then you want to get the data back in a scalar context:

# if the list has valid empty nodes, use
# a scalar return to check for end-of-list.

$listh->head;

my $data    = '';

while( $data = $listh->each )
{
    # play with @$data
}

or

# otherwise simply checking for an empty list
# is sufficient has has lower overhead on long
# lists.

$listh->head;

my @data    = ();

while( @data = $listh->each )
{
    # play with @data
}

unshift shift push

Notice the lack of "pop": it is quite expensive to maitain a node-before-the-last-data-node entry in order to guarantee removing the last node.

shift and unshift are cheap since they can access the root node in one step.

push can be quite inexpensive if the current node is at the end-of-list when it is called:

This is the cheap way to do it: leaving $$listh at the end-of-list after each push:

my $listh   = LinkedList::Single->new;

for(;;)
{
    my @data    = generate_some_data
    or last;

    $listh->push( @data );
}

If $listh is not already at the end-of-list then push gets expensive since the list has to be traversed in order to find the end and perform the push.

Note that walking the list can still be done between pushes by cloning the list handler and moving the clone or saving the final node and re-setting the list before each push.

For an insertion sort, each will leave the list handler on the last node:

my $listh   = LinkedList::Single->new;

my $new     = '';
my $old     = '';

DATA:
while( my $new = next_data_to_insert )
{
    $listh->head;

    while( $old = $listh->each ) 
    {
        # decide if the new data is a duplicate
        # or not. this requires examining
        # the entire list.

        is_duplicate_data $new, $old
        and next DATA;
    }

    # at this point $listh is at the end-of-list.

    $listh->push( @$new );
}

add cut splice

add appends a node after the current one, cut removes the next node, returning its data if not called in a void context.

splice is like Perl's splice: it takes a number of items to remove, optionally replacing them with the rest of the stack, one value per node:

my @new_nodz    = ( 1 .. 5 );

my $old_count   = 5;

my $old_list    = $listh->splice( $old_count, @new_nodz );

If called in a non-void context, the old nodes have a terminator added and are returned to the caller as an array of arrayrefs with the old data. This can be used to re-order portions of the list.

truncate

Chops the list off after the current node.

Note that doing this to the head node will not empty the list: it leaves the top node dangling.

AUTHOR

Steven Lembark <lembark@wrkhors.com>

COPYRIGHT

Copyright (C) 2009, 2010 Steven Lembark.

LICENSE

This code can be used under the same terms as Perl-5.10.1 itself.