dcsimg
Tricky question related to doubly linked lists
0 posts in topic
Flat View  Flat View
TOPIC ACTIONS:
 

Posted By:   Robert_Smith
Posted On:   Thursday, August 26, 2004 12:05 PM

Here’s the basis of the problem: You have one structure (figuring out what kind of structure is part of the problem) that contains a set of objects, let’s call it ALL. You have another that contains a subset of these objects which we’ll call SOME. You want to sort ALL on some criteria, then go through the elements of SOME, and look at the elements just before and after this element in ALL. What’s important is that I’m sorting the big list, and examining previous and next items from that list, but only for elements in the little list. The way I first implemented it is as follows: Both ALL and SOME are ArrayLists. I sort ALL (which is an O(N log(N) operation), then to an index=ALL.indexOf(SOME(j)), and    More>>

Here’s the basis of the problem:

You have one structure (figuring out what kind of structure is part of the problem) that contains a set of objects, let’s call it ALL. You have another that contains a subset of these objects which we’ll call SOME.

You want to sort ALL on some criteria, then go through the elements of SOME, and look at the elements just before and after this element in ALL.

What’s important is that I’m sorting the big list, and examining previous and next items from that list, but only for elements in the little list.

The way I first implemented it is as follows:

Both ALL and SOME are ArrayLists. I sort ALL (which is an O(N log(N) operation), then to an index=ALL.indexOf(SOME(j)), and look at ALL(index-1) and ALL(index+1).

The problem with this is that indexOf in an ArrayList is an order N operation, which I may have to do O(N) times. This is clearly slower than it should be.

A better approach is:

Make a TreeSet called ALLTREE. ALLTREE.add(ALL) automatically sorts ALLTREE, in O(N log(N)) time. Then, I look at the appropriate elements of headSet=ALLTREE.headSet(SOME(j)) and tailSet=ALLTREE tailSet(SOME(j)).

Getting these sets is an O(log(N)) operation, that I have to do O(N) times, getting me back to O(N log(N)).

However, I know it should be faster than that, yet I can’t figure how one can do it under Java’s classes (without writing several new classes, and perhaps a sort routine).

This is how I’d think about doing it from scratch in C:

Imagine ALL as a doubly linked list of elements, with each element containing a pointer to the previous and next elements in the list. Imagine that SOME contains references (pointers) to some of the elements in this list (which implicitly contain their next and previous references). Sort ALL (thus changing the next and previous pointers appropriately). You should be able to do this in O(N log(N)) time.

Then finding the next and previous elements (relative to ALL) for the elements of SOME should be an O(1) operation! I mean, you’ve got the pointer, just go look at the values pointed to by previous and next!

But, because things class in Collections hide the linked list functionality details, I can’t do this (or at least I can’t see how to).

All possibilities appreciated.
R.

   <<Less
About | Sitemap | Contact