LinkedList::Single - singly linked list manager.
# 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->node_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 unshift and shift; for a queue # 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 # shift and unshift manipulate the $listh root node # directly. This leaves $listh in the same location, # which may be at the end of a list for more efficient # handling of a FIFO queue. $listh->unshift( @new_head_node_data ); my @data = $listh->shift; # unshift + relocate. $listh->unshift( @new_head_node_data )->head; # sequences of pushes are efficient for adding # longer lists. this leaves $queue at the tail: my $queue = LinkedList::Single->new; $queue->push( @$_ ) for @preloaded_data; # in this case $queue itself stays at the end, # with next_out entries coming from the root. my $queue = LinkedList::Single->new; sub next_in { $queue->push( @_ ) }; sub next_out { $queue->shift }; # as are unshifts. a LIFO queue does not require # updating $listh: $listh->unshift( @new_item ); $listh->shift( @next_item ); # reset to the start-of-list. $listh->head; # hide extra data in the head node. $listh->set_meta( @whatever_you_like ); # extra data can come back as a list # or arrayref. my ( $value ) = $wcurve->get_meta; my $stuff = $wcurve->get_meta; # walk down the list examining a value from # each node. # # this assumes that none of the internal # nodes on the list are empty. For cases # where that might happen see below. # # various ways to handle the empty return: for( $listh->head ;;) { # examine one value without the # overhead of an array. my ( $value ) = $listh->each; $value // last; ... } for( $listh->head ;;) { my @data = $listh->each or last; my $value = shift @data; ... } for( $listh->head ;; ) { my $data = $listh->each or last; my $value = $data->[0]; ... } # dealing with possibly empty internal nodes. # (see also t/04-each.t). for( $listh->head ;; ) { $listh->has_next or last; # skip empty nodes. my @data = $listh->each or next; } # duplicate a list handler, reset it to the # start-of-list. note that clone produces a # new list handler, not an entirely new 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->node_data; ... } # for those do-it-yourselfers in the crowd: my $node = $listh->head_node; while( @$node ) { # advance the node and extract the data. # the final step will leave $node on the # sentinel, which has no next pointer, # which leaves @$node false above. ( $node, @data ) = @$node; # process @data... } # or, by moving the list handle to the # root node, you can splice off the head. my $head_node = $listh->root->splice( 1 ); # note that $listh->next->node_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.
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.
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).
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.
Note that this leaves two root nodes referencing the head node, with no way to determine which one to weaken. At that point cleaning up the clone is necessary for garbage collecting the list.
This clones the entire list or a subset of it.
If "tail" has a true value then the list will be cloned with the current node as the head; if count is provided then tail is assumed to be true and up to count nodes will be copied (or up to the tail in any case).
my $whole_clone = $listh->clone_list;
Clones are relatively quick and can handle large subets of data if the nodes' data are small lists or references. This makes a reasonable way to analyze a subset of the list in a loop.
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 is true if the list has any nodes at all; has_next is true if the current node has a next link; is_empty is true if the current node has no data.
Empty nodes can happen if the node contents are directly manipulated or a new node is added with no data in the first place.
The boolean operator returns true if the node has a next pointer, which will be true for all nodes other than the tail.
The tail node is_empty it's also false. If nodes may contain empty data then using the boolean or has_next are a better way to check for the end of a list:
sub walk_the_list { my $listh = shift; $listh->has_nodes or return; $listh->head; while( $listh ) { my @data = $list->node_data; ... } continue { $listh->next; } }
or just
for ( $listh->head ; $listh : $listh->next ) { ... }
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->node_data( undef )
for cleaning the node leaves no way to store an explicit undef in the 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.
The head node is the first one containing user data; the root node references the head and contains any metadata stored with set_meta.
head_node is useful for anyone that 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_node is mainly useful for intenal code or derived classes. This is used by all methods other than the construction and teardown methods to access the list's root node. Derived classes can override these methods to use another form of storage for the list root.
For example, unshift has to insert a node before the current head. It uses $lish->root to get a root node and then:
my $root = $listh->root_node; $root->[0] = [ $root->[0], @_ ];
to create the new head node.
If you want to splice off the head node then you need to start from the root node:
$listh->root; my $old_head = $listh->splice( 10 );
head and next start the list at the top and walk the list.
each is like Perl's each in that it returns data until the end-of-list is reached, at which point it returns nothing. 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 }
if all of the data nodes are always populated then checking for a false return in a list context will be sufficient:
$listh->head; my @data = (); while( @data = $listh->each ) { # play with @data }
map( $handler ) map( $handler, tail => 1 ) map( $handler, count => N )
Similar to the map builtin, map on the linked list takes a coderef and returns a new list of results produced by passing each node's values to the handler. The optional second argument "tail" then the list is processed from the current node (vs. the head); Given "count" the list at most N nodes are returned.
# produce a new list with each node having data of # the sum, min, max, average of values in each node # of the current list. my $summarize = sub { # expanded content of each node is passed on the stack. [ sum( @_ ), min( @_ ), max( @_ ), avg( @_ ) ] }; my $new_listh = $listh->map( $summarize ); # each node's data is an arrayref of the corresponding # input node in sorted order. the existing list has node # data of an array ref. # # the new list is suitable for replacing the existing # one with "new_root" for multi-pass processing. my $sorter = sub { my $data = shift; [ sort { $a <=> $b } @$data ] }; my $new_list = $listh->map( $sorter ); $listh->new_root( $new_list ); # at this point the list has been replaced with a new one # with each node's data in sorted order. # setting the optional second argument to true # processes from the current node to the end of # the list. # # in this case, get the average of # values in each node from the current node to # the end of the list. my $avg = sub { avg @_ }; my @subset_avg = $listh->map( $avg, 1 );
reduce( $handler ) reduce( $handler, tail => 1 ) reduce( $handler, count => N )
Similar to List::Util::reduce, but with a linked list as input rather than a perly list. The handler is assigned the result of calling
$handler( $curr_val, @node_data )
for each node on the list. Note that this requires calling the handler once with the first node and an undef $curr_val.
my $handler = sub { shift + sum @_ }; my $total = $listh->reduce( $handler );
or the smallest total value in any node data:
my $handler = sub { my $curr = shift; my $total = sum @_; $curr < $total ? $total : $curr }; my $max_total = $listh->reduce( $handler );
See "map", above, for use of "tail" and "count" parameters.
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. Using them is probably the best way to handle a stack (rather than trying to write your own 'pop' to work with push).
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 = get_new_data; $listh->push( @data ); my $job = $listh->shift or next; # now process $job }
This works well becuase shift and unshift do not modify the list handle's current node (i.e., $$listh is not touched). This means that each push leaves the list handle at the end-of-list node, where the push is cheap.
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. If you need to walk the list to scan the contents between push and shift op's then clone the list handle and use one copy to walk the list and the other one to manage the queue.
my $jobz = LinkedList::Single->new; my $queue = $jobz->clone; # use $queue->push, $queue->shift for # managing the queue, $jobs->head and # $jobs->each to scan the list, say for # stale or high-priority jobs.
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.
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, where push is cheap. $listh->push( @$new ); }
add appends a node after the current one, cut removes the next node, returning its data if not called in a void context.
Note that empty nodes and cutting off the end-of-list will both return empty in a list context. In a scalar context one returns an empty arrayref the other undef.
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.
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.
To zero out an existing list use
$list->root->truncate.
which leaves the set_meta/add_meta contents untouched but removes all nodes.
There are times when it is useful to retain the current list handler but replace the contents.
This is equivalent to:
$listh->head->truncate; $listh->initialize( @new_contents );
Adds a pre-existing linked below the root. The difference between this and replace is that the new list must already exist; the similarity is that any existing list is cleaned up.
The main use of this is adding skip chains to an existing linked list. One example would be adding skip chains for each letter of the alphabet in an alphabetically- sorted list:
my $node = $listh->head; $node = $node->[0] while $node->[1] lt $letter; my $skip = $listh->new; $skip->new_head( $node ); $skip_chainz{ $letter } = $skip;
The advantage to this approach is being able to maintain a single list and avoid traversing all of it in order to locate known starting points.
A similar result can be had by storing $node and calling $listh->node( $node ) later on to reset the position. The downside here is that any state in the list handler object is lost, where the separate lists can be manipulated seprately with things like $listh->head.
Steven Lembark <lembark@wrkhors.com>
Copyright (C) 2009-2021 Steven Lembark.
This code can be used under the same terms as v5.28 or any later version of Perl.
To install LinkedList::Single, copy and paste the appropriate command in to your terminal.
cpanm
cpanm LinkedList::Single
CPAN shell
perl -MCPAN -e shell install LinkedList::Single
For more information on module installation, please visit the detailed CPAN module installation guide.