![]() |
|||
![]() ![]() |
![]() |
![]()
|
![]() |
VectorsA Vector is Javas basic list class. A list is an ordered collection of items. The fundamental operations on a list are
The main difference between a list and an array is that a list generally doesnt have a fixed size. It can grow or shrink as needed. Furthermore, a list doesnt have empty spaces. If you remove a component from the middle of an array, you leave an empty space. All the other components stay where they are. On the other hand, if you remove an item from a list, all the items above it in the list are moved down to fill the space left. Implementation There are many different data structures that you can use to implement these operations. The very word list suggests a linked list data structure to many programmers. However, the Vector class is not a linked list, although you can do with a Vector anything you can do with a linked list. Instead, a Vector is a growable array. If that sounds funny to you, it should. Java arrays are not growable. You cannot take an array that was initialized with space for ten doubles and expand it so that it has space for twenty doubles. Once an array is created, its size is fixed. However, you can, memory permitting, create a new array with space for 20 doubles. Then you can copy the components of the original array into the new array. If you then adjust all references to the old array to point to the new array instead, its as if you grew the old array. The hard part of this procedure is finding all the references to the old array. Java solves this problem by making the array you want to grow a protected field in a public class: Vector. Only the Vector class ever holds any references to the array, and it has only one reference to the array. Other objects have references only to Vector objects. Therefore, when the array needs to be grown, you need to adjust only a single reference in the Vector class. This sort of data encapsulation is one of the primary advantages of object-oriented programming. You should recall that this is almost exactly what the StringBuffer class does when it needs to expand. StringBuffers use an array of chars instead of an array of objects like Vectors, but otherwise the logic is the same. Object[] elementData; ... // double the vector's capacity Obj ect[] newData = new Object[2*elementData.length]; System.arraycopy(elementData, 0, newData, 0, elementData.length); elementData= newData; The array that grows is a protected field of the Vector class called elementData; the number of elements currently stored in the array is a protected int field called elementCount. The elementCount, the number of elements in the array right now, should not be confused with the capacity of the array, which is the number of elements that can be stored in elementData before you need to grow it. In other words, the capacity is elementData.length. The fact that vectors are really just arrays behind the scenes has many implications for the performance and efficiency of the fundamental list operations. It means that insertions at the end of the list are quick, unless the vector has run out of space, in which case they can be quite slow. Insertions into the middle of the list are always slow. Finding the item at a given position in the list is fast. The array implementation of the Vector class also sets an upper limit on how many items you can place in a Vector. A Vector can hold up to 2,147,483,647 objects because an array is indexed with a signed int. In practice, youd run out of memory before you ever stuffed that many objects into a Vector. Creating a new Vector There are three constructors that create a new Vector: public Vector() public Vector(int initialCapacity) public Vector(int initialCapacity, int capacityIncrement); Every Vector has a capacity that is, the number of objects it can hold before it must be expanded. Because it takes time to expand a Vector, you generally want to have some empty space in a Vector so you dont need to expand it every time you add an element to it. However you dont want to waste space if you can avoid it. The noargs Vector() constructor creates a new Vector with an initial capacity of ten. When that capacity is exceeded, the Vector doubles in size. That is, when you add the eleventh element to the Vector, it expands itself to a capacity for 20 elements. When you add the 21st element, the Vector expands itself to a capacity for 40 elements, and so on. If you know how many elements that the Vector will probably need to hold when you construct it, you can speed up your program by using the Vector(int initialCapacity) constructor. For example, if you know youre going to put about 30 elements in a Vector, give or take five, then you should construct it like this: Vector myVector = new Vector(35); Unless the maximum number of elements youll place in the Vector is substantially greater than the average number of elements youll put there, you should always construct a Vector with the maximum number of elements you expect. Each empty space in a Vector only takes up four bytes. Therefore, unless youre really pressed for space, its much more important to avoid unnecessary resizing than to worry about the space wasted by a few empty slots. If you dont want a Vectors capacity to double every time it needs to be expanded, you can also pass a capacity increment to the constructor. For example, to create a Vector whose capacity increases in blocks of ten at a time and has an initial capacity of 35, you would write: Vector tenVector = new Vector(35, 10); Its rather unusual to do this, however. Most of the time the disadvantage of the CPU time youll lose to the extra resizing outweighs the small intermediate space savings youll achieve.
|
![]() |
|