The difference between LinkedList and ArrayList

data structure

    ArrayList Is the implementation of a dynamic array based data structure , During initialization , If the array size is not specified , The default size of the application is 10 Array of , When the number of elements increases , When an array cannot be stored , The system will be expanded (grow), The length of the new array is... Of the original length 1.5 times , Then copy the previous data to the new array .  

   LinkedList Is based on the two - way circular linked list , A two-way linked list contains two pointers ,pre Point to previous node ,next Point to the next node , But the first node head Of pre Point to null, Of the last node tail Point to null. The values are stored in item in ,LinkedList There is no concept of length , Therefore, there is no problem of insufficient capacity , Therefore, there is no need to provide a constructor of the initialization size , Therefore, only two methods are provided , One is the nonparametric construction method , The first one LinkedList object , One is and designated aggregate Elements converted to LinkedList Construction method .

Access elements

        For random access ArrayList The speed of is absolutely better than LinkedList. because ArrayList The data structure of is a dynamic array , We can directly use subscript pairs ArrayList Conduct get and set operation , and LinkedList It's a two-way circular list , Need to traverse .

Add and delete

        For addition and deletion ,LinkedList Is better than ArrayList, Because in ArrayList Need to move data , When the added element is larger than the length of the array , It also needs to be expanded , In addition, the more forward the position , The more elements you need to move , The more expensive it is . and LinkedList You only need to modify the previous element or the next element pre Point to and next Just point .

LinkedList Method and use of ArrayList Almost the same , because LinkedList It's a linked list , So it's extra to add... At the head and tail / How to delete elements , There is no ArrayList The problem of capacity expansion .