ArrayList and LinkedList are linear lists based on arrays and bidirectional linked lists, respectively. Because of the different implementation principles, ArrayList and LinkedList differ in the efficiency of random queries and inserts and deletes. Random query of ArrayList is fast, insertion is slow, and deletion is slow. This method applies to scenarios with frequent query and little modification. The LinkedList random query is slow, and the insertion and deletion are slow. It is applicable to the scenario where the query is few and the modification is frequent.

ArrayList

  • An ArrayList is an array-based, automatically scalable, sequential, linear list of addresses
  • Each element in the Arraylist has a corresponding subscript, and the query can quickly find the corresponding element according to the subscript
  • Each time an element is inserted or deleted from an Arraylist, some elements need to be moved to ensure continuity, so the insertion and deletion are inefficient
  • The initial size of the Arraylist is 10 (which can be specified). The calculation method for the first expansion is 10 x 1.5+1=16

LinkedList

  • LinkedList is a linear list based on a bidirectional LinkedList
  • LinkedList stores two Pointers before and after each element, which takes up more memory than ArrayList
  • Each query of LinkedList has to move the pointer from the beginning to the end of the traversal, and the performance of random query is low
  • When LinkedList is inserted or deleted, you only need to change the pointer direction, which has high performance
  • The LinkedList is theoretically infinite in size and does not need to be expanded