Efficient java data structure to delete and retrieve information?

Question

I have a situation where I have need a data structure that I can add strings to. This data structure is very large.

The specific qualities I need it have are:

get(index)
delete a certain number of entries that were added initially when the limit exceeds.(LIFO)

I've tried using an ArrayList but the delete operation is o(n) and for a linkedList the traverse or get() operation will be o(n).

What other options do I have?

I'm not aware of anything pre-existing in Java that can do that. Though I haven't exhaustively searched all of the queue variants. — Hot Licks
– Hot Licks, Commented May 31, 2012 at 0:23
LinkedList has a get(index) operator, plus enqueuing/dequeuing front and rear. — Hot Licks
– Hot Licks, Commented May 31, 2012 at 0:25
Anywhere between 50,000-80,000 strings. It has the potential of increasing too. — 12rad
– 12rad, Commented May 31, 2012 at 0:30

goat · Accepted Answer · 2012-05-31 00:25:21Z

6

circular buffer - one thats implemented with an array under the hood.

answered May 31, 2012 at 0:25

goat

31.9k7 gold badges76 silver badges98 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

12rad Over a year ago

I am not that familiar with a circular buffer.Will it maintain the order in which the elements are inserted?

goat Over a year ago

yes. get(index) is O(1) and so is delete, but, you can only delete the oldest(or newest) entries. you generally specify a maximum size for array backed implementations, and it self deletes the oldest entry when you add a new entry, if the new entry would overflow the buffer.

Community · Accepted Answer · 2017-05-23 11:56:29Z

0

LinkedHashSet might be of interest. It is effectively a HashSet but it also maintains a LinkedList to allow a predictable iteration order - and therefore can also be used as a FIFO queue, with the nice added benefit that it can't contain duplicate entries.

Because it is a HashSet too, searches (as opposed to scans) can be O(1) if they can match on equals()

You can have a look at this question and this too.

edited May 23, 2017 at 11:56

CommunityBot

11 silver badge

answered May 31, 2012 at 0:25

JHS

7,8812 gold badges34 silver badges54 bronze badges

Collectives™ on Stack Overflow

Efficient java data structure to delete and retrieve information?

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related