I think DOM will be the best fit for your purpose, and you don't need to reinvent everything by yourself. There is at least one module available for DOM in Perl. Go CPAN check out XML::DOM. You can also do a search, see whether there are other modules.
As for data structure, as long as it is acceptable to the DOM module you choose, it is fine.