Reputation: 1896

Vector option in Java

I am using vector of object. My issue is the removal from vector is expensive operation( O(n^2)). What would be the replacement of vector in Java. In my uses addition and removal is extensively happens.

i am C++ person don't know much Java

Upvotes: 1

Answers (8)

CrazyC

Reputation: 1896

Thanks to everyone for there contribution which helped me to solve this problem. I used a circular queue which has been written with help of vector.

Upvotes: 0

Stephen C

Reputation: 718758

i think, Vector using System.arrayCopy which complexity is O(n^2)

It is correct that Vector will use System.arrayCopy to move the elements. However the System.arrayCopy() call copies at most Vector.size() elements, and hence is O(N) where N is the vector's size.

Hence O(N^2) is incorrect for a single insertion / removal.

In fact, if you want better than O(N) insertion and deletion, you will need to use some kind of linked list type with a cursor abstraction that allows insertion and deletion at "the current position". Even then you only get better than O(N) if you can do the insertions / deletions in the right order; i.e. not random order.

FWIW, the Java List APIs don't provide such a cursor mechanism ... not least because it would be awkward to use, and only efficient in certain circumstances / implementations.

Upvotes: 0

Thomas

Reputation: 88707

Actually, the difference between Vector and ArrayList is that Vector is synchronized whereas ArrayList is not. Generally, you don't need synchronization and thus you'd use ArrayList (much like StringBuffer <-> StringBuilder).

The replacement mostly depends on how you intend to use the collection.

Adding objects to an ArrayList is quite fast, since if more space is required, it is normally doubled, and if you know the size requirements in advance, even better.

Removing from an ArrayList is O(n) but iteration and random access are fast.

If you have frequent add or remove operations and otherwise iterate over the list, a LinkedList would be fine.

You could even consider using a LinkedHashMap which allows fast access as well as preserves the order of insertion.

Upvotes: 0

tofarr

Reputation: 7851

Maybe a list is not the ideal data structure for your use case - would you be better off using a HashSet if the ordering of elements is not imporant?

Upvotes: 0

Gursel Koca

Reputation: 21300

First of all, Vector removal time complexity is O(n) not O(n^2). If you want more performant class, you should choose LinkedList. Its time complexity is constant.

Upvotes: 0