This is the 8th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Then an article on the Java collections framework | ArrayList, Vector, LinkedList (a), compared the ArrayList and Vector, this article is to compare the ArrayList, and LinkedList.

ArrayList and LinkedList compare

The previous article discussed the difference between ArrayList and Vector. The reason for this comparison is that the underlying implementations of both are dynamic arrays. Because ArrayList is thread-unsafe, we’ll compare ArrayList to a thread-unsafe LinkedList in this paragraph.

Linkedlist is implemented as a two-way Linkedlist. It performs better than arraylists on add and Remove, but worse on GET and set methods.

Compare the definitions of two classes in the source code.

ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Copy the code

LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
Copy the code

After comparison, it is clear that LinkedList implements Deque interface more than ArrayList, but implements RandomAccess interface less than ArrayList. So LinkedList provides an interface Deque that operates the queue, enabling effective access to both ends of the set, such as offer (), peek (), poll (), and so on.

But LinkedList lacks RandomAccess interface, which means that LinkedList does not support random storage, that is, through sequential access, query speed is slow, add and delete elements fast. ArrayList supports random access. The query speed is fast, but adding and deleting elements is slow. So the corresponding ArrayList query is fast, LinkedList query is slow, RandomAccess is the tag interface is a RandomAccess to the collection of elements, simply is the underlying array implementation of the collection.

RandomAccess this interface is just an empty one, so it’s a marker. So what can we do with it? Of course, check that the collection class implements the interface, and then use the corresponding traversal mode. That is, the implementation of RandomAccess interface, do not use iterator access, no implementation, use iterator access.

Time complexity of common operations

ArrayList LinkedList
get() O(1) O(n)
add() O(1) O(1)
remove() O(n) O(n)

conclusion

ArrayList LinkedList
Expansion mechanism The underlying implementation is an array that can be initialized in size and has an expansion mechanism. After the expansion mechanism is triggered, the array is expanded to 1.5 times the original capacity The bottom layer is implemented with two-way linked list, no initial size, so there is no expansion mechanism, has been in front of the increase or increase after
inheritance Implement List, RandomAccess interface Implement List, Deque interface
Insert the delete To operate in the middle of the structure, displacement is required No displacement is required to operate anywhere
advantage More suitable for static storage and read access More suitable for static data storage, suitable for delete, insert operations

In conclusion, we should first select LinkedList if the following conditions are met:

  • Elements don’t have a lot of random access
  • There are a lot of add/remove operations