perl实现链表

chriszg

　　perl数组的push,pop,shift,unshift操作可以实现栈，队列及双端队列，但是却不能支持链表的操作，所以创建链表要另寻他法。

创建链表



sub test {
    # Create list
    my $list = undef;
    foreach (reverse 1..5) {
        $list = [$list, $_ * $_] ;
    }      
}
　　上面的代码创建一个简单的单向链表，它的过程如下



[undef, 25]
[[undef, 25], 16]
[[[undef, 25], 16], 9]
[[[[undef, 25], 16], 9], 4]
[[[[[undef, 25], 16], 9], 4], 1]
　　对于$list中每个元素var，var[0]是元素的值，var[1]是指向下一个元素的引用。
　　比如$list[0] = 1, $list[1] = [[[[undef, 25], 16], 9], 4]
　　而$list[1][0] = 4， $list[1][1] = [[[undef, 25], 16], 9]
　　依次类推。。。

打印链表



# Print list
my $head = $list ;
while ($head->[0]) {
    print $head->[1], "\n" ;
    $head = $head->[0] ;
}
　　一个更好的方法，模拟C/C++中的方法来创建链表。



# The perl version of linklist
#
# Define a node, since perl does not have anything like 'struct' in C/C++
# So we use function to define and return a node
sub node {
    my ($value, $next) = @_ ;
    my $self = {
        'value' => $value,
        'next' => $next,
    } ;
    return $self ;
}
# Print the linklist, iterate from head to tail and print value for each node
sub print_list {
    my $head = shift ;
    while ($head) {
        print $head->{value}, "\n" ;
        $head = $head->{next} ;
    }
}
# Create a linklist, create a head first, then insert node one by one
sub create_list {
    my $head= &node(1, undef) ;
    my $temp = $head ;
    for my $i (2..10) {
        $temp->{next} = &node($i, undef) ;
        $temp = $temp->{next} ;
    }
    return $head ;
}
sub main {
    my $head = &create_list() ;
    &print_list($head) ;
}
&main() ;
1 ;
　　==