开发者

Lower level access to Java LinkedList?

I have a list of elements containing a few particular special elements and I need to find the neighbors of these elements in constant time. This sounds easy using a doubly linked list: simply store references to the nodes containing these particular elements and check their previous and next nodes. (I also prefer using a linked list since I constantly remove and add elements. The list is large and performance is particularly important.)

However, it seems that Java's LinkedList does not allow me to store the node containing an element. Is that right? If so, is there a clean way of doing what I need to do? This shouldn't be hard, but I didn't find a solution.

This needs to work with the list changing constantly and I prefer not having to update anything during the changes (for example, if I used an array, I would have to constantly update their indices whenever they moved in the array). Furthermore, I might need in the future to traverse the list starting from that special node without wasting time to find that node (which would also be easy in a low-level implementation of linked list), so I'd be even more thankful for a solution that also solved that.

Edit: Thanks开发者_JAVA百科 for the answers. I was hoping for a solution that didn't involve implementing my own version of a linked list, though. Is there one?


I think that implementing your own doubly-linked list class is the only way to get optimal performance for your application.

The standard list implementations work by using abstraction / information hiding to maintain the list invariants. As a result, they "just work" ... modulo the application doing the right thing with regards to synchronization if multiple threads are involved.

You want (and maybe need) to drill through the abstraction and get to the implementation details, and then do things that potentially result in the invariants being violated. It is not supported.


You could use ListIterator with its next() and previous() methods. Note: ListIterator becomes invalidated if you change the list any way without using the ListIterator.

Or you could use an index to an ArrayList.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜