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 b开发者_Go百科e the replacement of vector in Java. In my uses addition and removal is extensively happens.

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

---

Well, Vector class shouldn't be used. There are so many containers available in Java. Few of them:

ArrayList is good for random access, but is bad for inserting or removing from the middle of the list.

LinkedList is bad for random access, but is fair good for iterating and adding/removing elements from the middle of container.

---

You can use ArrayList instead of vector in Java.

---

Check out this article:

http://www.javaworld.com/javaworld/javaqa/2001-06/03-qa-0622-vector.html

LinkedList can add/remove items at O(1)

---

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.

---

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?

---

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.

---

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.

---

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.