DoubleLinkedList

[Derek Wyatt]

Hiya folks,

I've been looking into scala.collection.mutable.DoubleLinkedList and I'm having a tough time with it. What I'm looking for is the following:

• Constant time append of a single item
• Constant time removal of a single item (from the other end)
• Constant time remove-from-middle
• Linear time search from front (well, binary search would be better, but it's not crucial)
• As light-weight on memory as possible
• Mutable

All of the work with the structure will be within an (Akka) Actor's receive method.  The structure will be contained in the Actor itself and passed via an implicit to an external function that gets pimped onto an ActorRef (although still being access within the receive context).  The mutability of the structure makes it very easy to manipulate between these two worlds, and the Actor properties make it safe to do so.

A doubly linked list sounds like it fits the bill, but the the one defined in scala.collection.mutable seems really weird to me.

• It supplies a constant time, single element append, but it returns a copy of the list with the item appended.  This doesn't fit my general understanding of mutable and is making it difficult to work between the Actor and the pimp.
• Supplies a remove of the "current" item but how one points at the current item is not clear.  It seems like you have to write your own methods that use next and prev, and can't take advantage of something like 'find' in this case.

There are other things that make it seem "weird" to me, but the bottom appears to be that it won't fit my requirements (unless someone can enlighten me).  At the moment, I'm writing my own data structure to do this… I'm fine with that, but I'm surprised to find myself in this position.

Can someone point me at an existing structure that might fit the bill (something in the standard library is probably a must, in order to ensure the dependency count doesn't go up)?  I can't seem to find anything that matches my requirements and I just want to be sure that's the case before I continue using a home-grown structure.

Thanks,

Derek

[√iktor Ҡlang]

java.util.LinkedList?

--
Viktor Klang

Akka Tech Lead

Typesafe - The software stack for applications that scale

Twitter: @viktorklang

[Derek Wyatt]

On 2012-11-10, at 12:06 PM, √iktor Ҡlang wrote:

java.util.LinkedList?

Hmph.  I never even thought to look back into that old thing… smack my ass, and call me Judy, I think that oughta do the trick.

Thanks √ :)

Derek