Shulou(Shulou.com)06/02 Report--

This article mainly introduces "what is the difference between ArrayList,Vector and Stack". In daily operation, I believe many people have doubts about the difference between ArrayList,Vector and Stack. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the doubts of "what is the difference between ArrayList,Vector and Stack?" Next, please follow the editor to study!

ArrayList

Overview of ArrayList

ArrayList is a dynamic array that implements the List interface. Dynamic means that its size is variable. All optional list operations are implemented and all elements, including null, are allowed. In addition to implementing the List interface, this class also provides methods to manipulate the size of the array used internally to store the list.

Each ArrayList instance has a capacity, which is the size of the array used to store list elements. The default initial capacity is 10. With the increase of elements in ArrayList, its capacity will continue to increase automatically.

Each time a new element is added, ArrayList will check whether a capacity expansion operation is required, and the expansion operation results in re-copying of data to the new array. Therefore, if we know the specific amount of business data, we can specify an initial capacity for the ArrayList when constructing the ArrayList, which will reduce the data copy problem during capacity expansion. Of course, before adding a large number of elements, applications can also use ensureCapacity operations to increase the capacity of ArrayList instances, which can reduce the number of incremental redistributions.

Note that the ArrayList implementation is not synchronous. If multiple threads access an ArrayList instance at the same time, and at least one of them modifies the list structurally, it must maintain external synchronization. So to ensure synchronization, the best way is to do it at creation time to prevent accidental asynchronous access to the list:

List list = Collections.synchronizedList (new ArrayList (...)); underlying data structure

At the bottom of ArrayList is an array of object and decorated by trasient.

/ / transient Object [] elementData; / /

The non-private to simplify nested class access / / ArrayList underlying array does not participate in serialization, but uses a different serialization method.

/ / use the writeobject method for serialization. Why, please check out my previous article on serialization.

/ / to sum up, only the positions with values in the array are copied, and other unassigned locations are not serialized, which saves space.

/ / private void writeObject (java.io.ObjectOutputStream s) / / throws java.io.IOException {/ Write out element count, and any hidden stuff// int expectedModCount = modCount;// s.defaultWriteObject (); / Write out size as capacity for behavioural compatibility with clone () / / s.writeInt (size) / Write out all elements in the proper order.// for (int iTuno; I 0) / / System.arraycopy (elementData, index+1, elementData, index,// numMoved); / / elementData [--size] = null; / / clear to let GC do its work//// return oldValue;//}

ArrayList provides a way to empty the array by setting all elements to null so that GC can automatically recycle elements that are not referenced.

/ Removes all of the elements from this list. The list will// * be empty after this call returns.// * / / public void clear () {/ / modCount++;//// clear to let GC do its work// for (int I = 0; I

< size; i++)// elementData[i] = null;//// size = 0;// } 修改元素时，只需要检查下标即可进行修改操作。 // public E set(int index, E element) {// rangeCheck(index);//// E oldValue = elementData(index);// elementData[index] = element;// return oldValue;// }//// public E get(int index) {// rangeCheck(index);//// return elementData(index);// }// 上述方法都使用了rangeCheck方法，其实就是简单地检查下标而已。 // private void rangeCheck(int index) {// if (index >

= size) / / throw new IndexOutOfBoundsException (outOfBoundsMsg (index)); / /} modCount// protected transient int modCount = 0

As you can see from the above code, when an iterator initially gives it the mCount of the object that calls the iterator, how to throw an exception once it is found that the mcount of this object is different from the mcount stored in the iterator during the iterator traversal?

Okay, here's a complete explanation of the Fail-Fast mechanism. We know that java.util.ArrayList is not thread-safe, ArrayList, so we will throw ConcurrentModificationException, which is called fail-fast policy.

This strategy is implemented in the source code through the modCount domain. ModCount, as its name implies, means the number of modifications. Any modification to the ArrayList content will increase this value, so this value will be assigned to the iterator's expectedModCount during the initialization of the iterator.

During the iteration, it is determined whether modCount is equal to expectedModCount, and if not, it means that another thread has modified the ArrayList.

So I suggest here that when you traverse non-thread-safe data structures, use iterators as much as possible.

Initial capacity and expansion mode

The initial capacity is 10. Here is how to expand the capacity. First, take first.

/ / private static final int DEFAULT_CAPACITY = 10; when the expansion occurs in the add element, pass the current element capacity plus one public boolean add (E e) {ensureCapacityInternal (size + 1); / / Increments modCounting! ElementData [size++] = e; return true;} here gives the initialization array private static final Object [] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; this means that if the array is still the initial array, then the minimum expansion size is size+1 and the larger of the initial capacity, with an initial capacity of 10. Because the addall method also calls this function, you need to make a judgment at this point. Private void ensureCapacityInternal (int minCapacity) {if (elementData = = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max (DEFAULT_CAPACITY, minCapacity);} ensureExplicitCapacity (minCapacity);} / / start precise capacity expansion private void ensureExplicitCapacity (int minCapacity) {modCount++; / / overflow-conscious code if the capacity expansion is greater than the array length at this time, execute grow, otherwise it will not be executed. If (minCapacity-elementData.length > 0) grow (minCapacity);}

The method grow that actually executes capacity expansion

The way to expand the capacity is to make the new capacity equal to 1.5 of the old capacity.

When the new capacity is greater than the maximum array capacity, large expansion is performed.

/ / private void grow (int minCapacity) {/ overflow-conscious code// int oldCapacity = elementData.length;// int newCapacity = oldCapacity + (oldCapacity > > 1); / / if (newCapacity-minCapacity)

< 0)// newCapacity = minCapacity;// if (newCapacity - MAX_ARRAY_SIZE >

0) / / newCapacity = hugeCapacity (minCapacity); / minCapacity is usually close to size, so this is a win:// elementData = Arrays.copyOf (elementData, newCapacity); / /}

When the new capacity is greater than the maximum array length, there are two cases, one is overflow, throwing an exception, and the other is no overflow, returning the maximum value of the integer.

Private static int hugeCapacity (int minCapacity) {if (minCapacity)

< 0) // overflow throw new OutOfMemoryError(); return (minCapacity >

MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE;}

There is a question here: why is it that each expansion is 1.5 times instead of 2.5, 3 or 4 times? Through google search, it is found that the expansion of 1.5 times is the best multiple. Because an one-time expansion (for example, 2.5 times) may waste more memory (1.5 times will waste 33% at most, while 2.5 times will waste up to 60%, 3.5 times will waste 71%.) . However, the one-time expansion is too small, and the memory needs to be reallocated to the array many times, which consumes a lot of performance. So 1.5 times is just right, which can not only meet the performance requirements, but also will not cause a lot of memory consumption.

In addition to dealing with the ensureCapacity () expanded array, ArrayList also provides us with the ability to resize the underlying array to the size of the actual elements saved in the current list. It can be achieved through the trimToSize () method. This method minimizes the storage of ArrayList instances.

Public void trimToSize () {modCount++; int oldCapacity = elementData.length; if (size

< oldCapacity) { elementData = Arrays.copyOf(elementData, size); }}线程安全 ArrayList是线程不安全的。在其迭代器iteator中，如果有多线程操作导致modcount改变，会执行fastfail。抛出异常。 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }Vector Vector简介 Vector可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。不过，Vector的大小是可以增加或者减小的，以便适应创建Vector后进行添加或者删除操作。 Vector实现List接口，继承AbstractList类，所以我们可以将其看做队列，支持相关的添加、删除、修改、遍历等功能。 Vector实现RandmoAccess接口，即提供了随机访问功能，提供提供快速访问功能。在Vector我们可以直接访问元素。 Vector 实现了Cloneable接口，支持clone()方法，可以被克隆。 vector底层数组不加transient，序列化时会全部复制 protected Object[] elementData;// private void writeObject(java.io.ObjectOutputStream s)// throws java.io.IOException {// final java.io.ObjectOutputStream.PutField fields = s.putFields();// final Object[] data;// synchronized (this) {// fields.put("capacityIncrement", capacityIncrement);// fields.put("elementCount", elementCount);// data = elementData.clone();// }// fields.put("elementData", data);// s.writeFields();// } Vector除了iterator外还提供Enumeration枚举方法，不过现在比较过时。 // public Enumeration elements() {// return new Enumeration() {// int count = 0;//// public boolean hasMoreElements() {// return count < elementCount;// }//// public E nextElement() {// synchronized (Vector.this) {// if (count < elementCount) {// return elementData(count++);// }// }// throw new NoSuchElementException("Vector Enumeration");// }// };// }//增删改查 vector的增删改查既提供了自己的实现，也继承了abstractList抽象类的部分方法。 下面的方法是vector自己实现的。 //// public synchronized E elementAt(int index) {// if (index >

= elementCount) {/ / throw new ArrayIndexOutOfBoundsException (index + "> =" + elementCount); / /} / return elementData (index); / /} / public synchronized void setElementAt (E obj, int index) {/ / if (index > = elementCount) {/ / throw new ArrayIndexOutOfBoundsException (index + "> =" + / / elementCount) / / elementData [index] = obj;//} / public synchronized void removeElementAt (int index) {/ / modCount++;// if (index > = elementCount) {/ / throw new ArrayIndexOutOfBoundsException (index + "> =" + / / elementCount); / /} / / else if (index

< 0) {// throw new ArrayIndexOutOfBoundsException(index);// }// int j = elementCount - index - 1;// if (j >

0) {/ / System.arraycopy (elementData, index + 1, elementData, index, j); / /} / / elementCount--;// elementData [elementCount] = null; / * to let gc do its work * / /} / / public synchronized void insertElementAt (E obj, int index) {/ / modCount++ / / if (index > elementCount) {/ / throw new ArrayIndexOutOfBoundsException (index// + ">" + elementCount); / /} / / ensureCapacityHelper (elementCount+ 1); / / System.arraycopy (elementData, index, elementData, index + 1, elementCount-index); / / elementData [index] = obj;// elementCount++ / /} / public synchronized void addElement (E obj) {/ / modCount++;// ensureCapacityHelper (elementCount+ 1); / / elementData [elementCount++] = obj;//} initial capacity and expansion

The method of capacity expansion is basically the same as that of ArrayList, but there is a capacity expansion increment instead of 1.5x.

/ / protected int elementCount;// protected int capacityIncrement;/} / / public Vector () {/ / this (10) / /}

CapacityIncrement: the amount by which the capacity automatically increases when the size of a vector is greater than its capacity. If you specify the size of the capacityIncrement when you create the Vector, each time the capacity of the dynamic array in the Vector increases >, the increased size is capacityIncrement. If the increment of the capacity is less than or equal to zero, the capacity of the vector will double each time the capacity needs to be increased.

/ / public synchronized void ensureCapacity (int minCapacity) {/ / if (minCapacity > 0) {/ / modCount++;// ensureCapacityHelper (minCapacity) / /} / private void ensureCapacityHelper (int minCapacity) {/ overflow-conscious code// if (minCapacity-elementData.length > 0) / / grow (minCapacity); / /} / private void grow (int minCapacity) {/ overflow-conscious code// int oldCapacity = elementData.length / / int newCapacity = oldCapacity + ((capacityIncrement > 0)? / / capacityIncrement: oldCapacity); / / if (newCapacity-minCapacity

< 0)// newCapacity = minCapacity;// if (newCapacity - MAX_ARRAY_SIZE >

0) / / newCapacity = hugeCapacity (minCapacity); / / elementData = Arrays.copyOf (elementData, newCapacity); / /} Thread Safety

Vector uses the synchronized modifier for most methods, so it is a line-level safe collection class.

Stack

In Java, the Stack class represents a last-in, first-out (LIFO) object stack. Stack is a very common data structure, which is completed by a typical first-in-first-out operation. Each stack contains a top of the stack, and the data at the top of the stack is taken out each time, as follows:

Cdn.xitu.io/2019/4/13/16a15e61b3069057?w=835&h=354&f=jpeg&s=35312 ">

Stack extends Vector through five operations, allowing vectors to be treated as stacks. The five operations are as follows:

Empty ()

Test whether the stack is empty.

Peek ()

Look at the object at the top of the stack without removing it from the stack.

Pop ()

Removes the object at the top of the stack and returns it as the value of this function.

Push (E item)

Press the item on top of the stack.

Search (Object o)

Returns the position of the object in the stack, with a base of 1.

Stack inherits Vector, and he makes a simple extension to Vector:

The implementation of public class Stack extends Vector Stack is very simple, there is only one construction method, five implementation methods (the method inherited from Vector is not among them), and the source code of its implementation is very simple.

/ * Constructor * / public Stack () {} / * push function: store elements on top of stack * / public E push (E item) {/ / store elements on top of stack. / / implementation of addElement () in Vector.java addElement (item); return item;} / * pop function: returns the top element of the stack and removes it from the stack * / public synchronized E pop () {E obj; int len = size (); obj = peek (); / / deletes the top element of the stack, and the implementation of removeElementAt () is removeElementAt (len-1) in Vector.java; return obj } / * peek function: returns the top element of the stack without performing the delete operation * / public synchronized E peek () {int len = size (); if (len = = 0) throw new EmptyStackException (); / / returns the top element of the stack. ElementAt () implements return elementAt (len-1) in Vector.java;} / * * whether the stack is empty * / public boolean empty () {return size () = = 0 } / * find the position of "element o" in the stack: the number of directions from the bottom of the stack to the top of the stack * / public synchronized int search (Object o) {/ / get the element index. ElementAt () is implemented in Vector.java int I = lastIndexOf (o); if (I > = 0) {return size ()-I;} return-1;}

Much of the source code of Stack is based on Vector, so I won't repeat it here.

Difference

Advantages and disadvantages of ArrayList

Summarize the advantages and disadvantages of ArrayList from the above processes. The advantages of ArrayList are as follows:

1. The underlying ArrayList is implemented in an array, which is a random access mode. In addition, it implements the RandomAccess interface, so it is very fast to find get.

2. ArrayList is very convenient when adding an element sequentially, just adding an element to the array

However, the shortcomings of ArrayList are also obvious:

1. When deleting elements, one element copy is involved. If there are many elements to be copied, it will cost more performance.

2. When inserting elements, one element copy is involved. If there are many elements to be copied, it will cost more performance.

Therefore, ArrayList is more suitable for sequentially added, random access scenarios.

The difference between ArrayList and Vector

ArrayList is thread-unsafe, which is obvious, because none of the methods in ArrayList are synchronous, and thread-safety problems are bound to occur in concurrency. So what if we want to use ArrayList and make it thread-safe? One way is to turn your ArrayList into a thread-safe List using the Collections.synchronizedList method, such as:

List synchronizedList = Collections.synchronizedList (list); synchronizedList.add ("aaa"); synchronizedList.add ("bbb"); for (int I = 0; I

< synchronizedList.size(); i++){ System.out.println(synchronizedList.get(i));} 另一个方法就是Vector，它是ArrayList的线程安全版本，其实现90%和ArrayList都完全一样，区别在于： 1、Vector是线程安全的，ArrayList是线程非安全的 2、Vector可以指定增长因子，如果该增长因子指定了，那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子；如果不指定增长因子，那么就给原数组大小*2，源代码是这样的： int newCapacity = oldCapacity + ((capacityIncrement >

0)? CapacityIncrement: oldCapacity); at this point, the study on "what's the difference between ArrayList,Vector and Stack" is over. I hope I can solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.