Subj : Re: Looking for a nice data structure for lists... To : comp.programming From : cri Date : Wed Oct 12 2005 03:48 pm On Wed, 12 Oct 2005 09:20:38 +0200, "Michael Jørgensen" wrote: > >"DV" wrote in message >news:1128968328.414511.150270@g49g2000cwa.googlegroups.com... >> Is there a data structure for lists such that a list can be split in >> half in constant time or its middle element found in constant time >> (such as an array pointer + size variable) but also such that two lists >> can be merged in constant time (such as a linked list)? This isn't a >> homework problem. >> >> It seems like if you take the arraylike properties, you are forced to >> forfeit the linkedlistlike properties... it would be extremely nice to >> have some data structure that has both :/ > >How about an ordinary doubly linked list, where you keep *three* pointers >and a length. The third pointer will simply point to the middle of the list. >It should be possible to update this pointer in constant time, given that >you know the length of the list, PROVIDED you additionally know whether the >element you're add/deleting is to the left or the right of the middle >element. All this could be achieved using iterators. GIDW (Good Idea, Doesn't Work). The problem is that the property of "knowing where the middle is" isn't preserved by splitting. In other words, when you split the list you don't know where the middles of the two pieces are. On the other hand concatenating does work nicely. If you have lists S1 = {L1,R1} and S2 = {L2,R2} then we concatenate them by producing the list {L1,L2,R1,R2}. Incidentally, mark each element in the list as being left or right to know which side it is on. This is an interesting problem. The impression I have is that if we insist on finding the exact middle we will need at least O(log n) somewhere. OTOH if we relax the condition to be approximate middle and accept amortized costs then I believe that it can be done with an unbalanced (unsorted) binary tree. Richard Harter, cri@tiac.net http://home.tiac.net/~cri, http://www.varinoma.com I started out in life with nothing. I still have most of it left. .