Truncate a LinkedList

[Peter Levart]

On 02/19/2013 01:24 PM, Peter Levart wrote:
> On 02/19/2013 11:38 AM, Daniel Fuchs wrote:
>> On 2/19/13 11:27 AM, Weijun Wang wrote:
>>> Hi All
>>>
>>> I'm using LinkedList to maintain a history and the elements are ordered
>>> by their timestamps. Every now and then I would "expunge" the list, 
>>> that
>>> is to say, iterating through the list and when an element is old enough
>>> all elements after (and including) it will be removed. Currently I'm
>>> removing them one by one.
>>>
>>> Is there a way to truncate the list using a single method?
>>>
>>> Thanks
>>> Max
>>
>> Hi Max,
>>
>> You could try to use AbstractList.subList(...)
>>
>> <http://docs.oracle.com/javase/6/docs/api/java/util/AbstractList.html#subList%28int,%20int%29> 
>>
>>
>> Quoting from the doc:
>>
>>> For example, the following idiom removes a range of elements from a 
>>> list:
>>>
>>>       list.subList(from, to).clear();
>>>
> Hi Daniel,
>
> That's not terribly efficient. It does the list.removeRange(from, to) 
> which iterates the list again from the beginning to "from" followed by 
> iterating elements further to "to" while removing elements one-by-one. 
> That's worse than Weijun's original algorithm which iterates the 
> elements from 1st to "from" only once.
>
> I would make my own linked structure for that task, but if you want to 
> stick with LinkedList, your expunging algorithm could "copy" the 
> elements, from the 1st to the one that is the last to be kept, into a 
> new LinkedList and then just exchange the old list with the new...
Hi Weijun,

The above would be efficient if the remaining "head" is small compared 
to the discarded "tail". If it's the other way around, you could iterate 
the LinkedList from the end backwards and remove the elements along the 
way until you reach the one you want to keep...

>
> Regards, Peter
>
>>
>> -- daniel
>>
>>
>