Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Re: OOP/Linked List Question

by Tanktalus (Canon)
on Feb 07, 2005 at 16:31 UTC ( #428727=note: print w/replies, xml ) Need Help??

in reply to OOP/Linked List Question

I've created all sorts of ADTs in C/C++. I've used even more (Standard Template Library was great!). I've never even thought about it in perl. I'm sure someone will come along and tell me why it was such a great thing for what they were doing. That's fine - but AoH, HoA, HoHoHoH, AoAoH, etc., these kinda take the place of those other container types that you need so badly in other languages.

That's not to say it can't be done in Perl, or even that, as an excersise in learning how references work, it's not worth doing in perl. Just that I've never had a reason to use it.

Perl has great data structures internally which seem to solve the problems: hashes and arrays. And I can choose whichever one makes sense. Iterating over them is easy, whether that's foreach over an array, over the keys to a hash, or while/each over a hash.

Usually, I think, a linked list is used to make things easy to add/remove from the beginning and the end of the list. That's what shift, unshift, push, and pop are for. Perl is already likely using a linked list as it is. And it's probably got some other abstractions put into its "array" type, too, to give you direct access to an arbitrary scalar (ref's are scalars, too ;->) in the array, to always know the length, etc.

Circular lists - such that instead of falling off the list at the end, you simply wrap around to the beginning - are not something I found a lot of use for in C/C++ anyway, so perhaps you may still find the same use for them in perl. Mind you, if all you want to do is be able to start at an arbitrary point in the list, you can do the same in perl pretty easily: foreach my $s (@list[$n..$#list,0..$n-1]) { ... }.

I guess my point is ... you might be better off learning perl idioms to get your job done faster rather than trying to write C/C++ in perl. ;-)

Replies are listed 'Best First'.
Re^2: OOP/Linked List Question
by hok_si_la (Curate) on Feb 07, 2005 at 16:52 UTC
    I thank all of you for your insight. Each one of you brought something useful to the table.

    One reason I was interested in learning how to create a linked list data type is because of an app I am programming. I am mainly trying to improve the speed of one operation: removing or adding a record into the middle of a list. When done generically, the operation gets expensive as the number of records or nodes increase. Instead of shifting all the list elements up or down, I would prefer to just delete a node an update a pointer. I am probably making it more difficult than it has to be. Once I am able to understand the quickest way to do this I plan on creating another 'good ole ADT classic', the binary search tree.

    I'll post something this weekend for you hardcore coders with nothing better to do so you can see the project I am working on. It is called FACT. It simply translates mono-alphabetic substitution ciphers using an algorithmic/AI approach hybrid. I am attempting to solve cryotoquips quicker than the app located here: . I believe by incorporating his pattern idea along with a group of AI rules, the results could be returned quicker.

    Thanks again for all of your insight,
      Instead of shifting all the list elements up or down, I would prefer to just delete a node an update a pointer.

      How big is your list?

      I ask for two reasons:

      1. If your list is large, using hashes or arrays to create your linked list will cost you lots of memory.
      2. Despite it's O(N) credentials, splice is remarkably adept at inserting things into the middle of even fairly long ( < ~ 20,000 elements ) lists.

      And sometimes, the easy option is good enough. If your list is long enough for the cost of spliceing to become a problem, then you will also be approaching that point at which contructing linked lists from either hashes or arrays starts to consume very large volumes of memory.

      Using a heap, or even a string-based list may prove to be fast enough whilst keeping your memory consumption with the range of sanity.

      Examine what is said, not who speaks.
      Silence betokens consent.
      Love the truth but pardon error.

        The list in my future code would be dynamic in size, and would contain anywhere from 50-1500 elements. I certainly obtained a ton of good advice on the topic. I need to consult my old operation cost charts from school, and play with a few of the ideas to decide which data type would be a best fit for my app. I am really looking forward to getting this running.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://428727]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2018-03-24 01:08 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (297 votes). Check out past polls.