Weekly Challenge 129
Tags: perl, theweeklychallenge
Published: 2021-09-12 10:57:18

Hi all. I only completed one challenge this week. But at 140 lines, it's the second longest submission. For the record, my longest submission was 156 lines for challenge 118.

I attended [PyConline Australia](https://2021.pycon.org.au/) the past few days, virtually of course thanks to the 'rona. The videos from the conference should be on their [Youtube channel](https://www.youtube.com/c/PyConAU) by the time you read this.

This [weeks challenge](https://theweeklychallenge.org/blog/perl-weekly-challenge-129/) and my [solution](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-129/sgreen).

## TASK #2 › Add Linked Lists

You are given two linked list having single digit positive numbers.

Write a script to add the two linked list and create a new linked representing the sum of the two linked list numbers. The two linked lists may or may not have the same number of elements.

Feel free to come up with your own unique way to deal with the task. I am expecting a class representing linked list. It should have methods to create a linked list given list of single digit positive numbers and a method to add new member. Also have a method that takes 2 linked list objects and returns a new linked list. Finally a method to print the linked list object in a user friendly format.

## My solution

As regularly readers of my blog probably know, I don't like to use non-core modules when solving the challenge. And that is true this time.

It's also the first time I've done a linked list challenge properly. So the main part of the challenge is to write the LinkedList module. Since we need to know the values in reverse, this is a double linked list. That is, each node is linked both the next and previous node. In the real world, I would have used Moo, but see the above paragraph for why I didn't.

My LinkedList module stores an internal value of `_list` that contains the ordered list of LinkedList::Node objects. It has the `first` and `last` method which returns the first and last node respectively. And it has the `as_string` function to display the list as a printable string separated by ` -> `.

Each LinkedList::Node object has the methods `value` (to get the value of the node), and `prev` and `next` to get the previous or next node (or undef if none exists). It also has `set_prev` and `set_next` to set these values.

That's all the boring bits. Now for the fun.

The LinkedList model has the methods `push`, `unshift` which both do the same as the Perl methods of the same name. These methods create a new node object, and creates the prev / next link between the last node and the newly created one (or the first node for the unshift method).

The LinkedList module also has the `_add` method, which [overloads](https://metacpan.org/pod/overload) the addition method. For this method, I get the last value of each linked list and sum them together. The last digit is added to the `$new_list` linked list, and the carry forward is added to the `$carry` variable. I repeat this until both lists are exhausted and there is no carry forward.

Still reading? Well done :-)

## Examples

```
$ ./ch-2.pl 123 321
4 -> 4 -> 4

$ ./ch-2.pl "1 -> 2 -> 3 -> 4 -> 5" "6 -> 5 -> 5"
1 -> 3 -> 0 -> 0 -> 0
```