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

This article introduces the relevant knowledge of "the comparison of ArrayList, LinkedList, Vector and Stack in Java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

I. introduction

Let's review the frame diagram of List.

From the inheritance relationship in the diagram, you can see that ArrayList, LinkedList, Vector, and Stack are all four implementation classes of List.

AbstractList is an abstract class that inherits from AbstractCollection. AbstractList implements functions in the List interface except size () and get (int location).

AbstractSequentialList is an abstract class that inherits from AbstractList. AbstractSequentialList implements "all functions in the linked list that manipulate the linked list according to the index index value".

ArrayList is an array queue, equivalent to a dynamic array. It is implemented by array and has high efficiency of random access and low efficiency of random insertion and random deletion.

LinkedList is a two-way linked list. It can also be operated as a stack, queue, or double-ended queue. The efficiency of LinkedList random access is low, but the efficiency of random insertion and random deletion is low.

Vector is a vector queue, and like ArrayList, it is a dynamic array implemented by an array. But ArrayList is not thread-safe, while Vector is thread-safe.

Stack is a stack, which inherits from Vector. Its features are: first in, then out (FILO, First In Last Out)

Second, performance testing

Before comparing ArrayList, LinkedList, Vector and Stack, let's test their performance and analyze ArrayList, LinkedList, Vector and Stack in detail with the source code and test results.

The results are as follows

According to the results, it is obvious that the performance of ArrayList, LinkedList, Vector and Stack is very different.

Read: ArrayList > Vector > Stack > LinkedList

Insert: LinkedList > Vector > ArrayList > Stack

Delete: LinkedList > Vector > ArrayList > Stack

III. Analysis of insertion

LinkedList

From this, we can see that when inserting elements into LinkedList through add (int index, E element). First find the location in the two-way linked list where you want to insert the node index; found, and then insert a new node.

When a two-way linked list looks for a node at index location, there is an accelerated action: if index

There is a very time-consuming operation in this.

System.arraycopy (elementData, index, elementData, index + 1, size-index)

This method is marked native and calls the system's Cmax Candle + code, which is not visible in JDK, but its source code can be seen in openJDK.

This function actually calls the memmove () function of C language finally, so it can guarantee the correct copy and movement of elements in the same array, which is much more efficient than the general copy method, and is very suitable for batch processing of arrays. Java strongly recommends this method when copying a large number of array elements to achieve higher efficiency.

Vector

You can see that Vector and ArrayList are the same, both calling System.arraycopy. Because of Stack and inheritance and Vector, it is not carefully analyzed.

IV. Analysis of search

LinkedList

From this, we can see that when we get the index element of LinkedList through get (int index). First, find the element in the two-way linked list that you want to index; find it and then return.

When a bi-directional linked list looks for a node in an index location, there is an accelerated action: if index < 1 prime 2 of the length of the bi-directional linked list, it looks forward and backward; otherwise, it looks back and forward.

ArrayList

We can see that ArrayList directly returns the elements of the index position in the array without having to look up like LinkedList.

Through the source code, it is found that Vector and Stack operate in the same way as ArrayList, so I won't analyze them in detail here.

5. Analysis of deletion

LinkedList

Since a node has been deleted, the front and back pointer information of the corresponding node is adjusted as follows:

E.previous.next = e.nextram / the back pointer of the previous node of the pre-deleted node points to the latter node of the pre-deleted node. E.next.previous = e.previousrandom / the front pointer of the second node of the pre-deleted node points to the previous node of the pre-deleted node.

Clear the pre-deleted nodes:

E.next = e.previous = null; e.element = null

Send it to gc to complete the resource recovery, and the deletion operation ends.

Compared with ArrayList, the delete action of LinkedList does not need to "move" a lot of data, so it is more efficient.

ArrayList

Well, System.arraycopy is called again.

VI. Conclusion

Operate ArrayListLinkedListVectorStack to read O (1) O (n) O (1) O (1) insert O (n) O (1) O (n) O (n) delete O (n) O (1) O (n) O (n)

ArrayList (dynamic array), fast query (random access or sequential access), slow addition and deletion. The overall emptying is fast, and the thread is out of sync (non-thread safe). The length of the array is variable by 50%

LinkedList (implement linked list), slow query, fast addition and deletion.

Vector (implementing dynamic arrays), both slow, is replaced by ArrayList. The length is arbitrarily extended. Thread safety (synchronized classes, functions are all synchronized)

Stack (implementation stack) inherits from Vector and comes in first and then out.

Therefore, quick access to ArrayList and quick addition and deletion of LinkedList can be used by single thread, while multi-thread can only use synchronous class Vector.

This is the end of the introduction to the comparison of ArrayList, LinkedList, Vector and Stack in Java. Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.