Difference between ArrayList and LinkedList

The other day, I was asked if I could understand the difference between ArrayList and LinkedList, and I couldn't answer, so I will post it as a memorandum.

What is ArrayList?

ArrayList is a list structure that uses arrays internally. The difference from the standard array is that you can resize it later. By its nature, reading and writing values by index value is fast, but inserting / deleting elements becomes slower as the array size increases and the operation position approaches the beginning.

·merit Each element has a sequence number and is all indexed in memory so you can quickly access a particular element.

·Demerit When an element other than the end is added or subtracted, a rearrangement process is performed to move up or down the sequence number of all subsequent elements. As a result of that process, all the elements in the ArrayList are neatly arranged with all sequence numbers from 0 to the total number of elements minus 1, but it takes time for the process to be performed. I will. And the number of processes increases in proportion to the number of elements.

Method Overview
add([int index,] E e) Insert element e at the specified position index (insert at the end without index omitted)
clear() Remove all elements from list
contains(Object e) Determine if the list contains element o
get(int index) be
indexOf(Object e) Get the first index value where element o appears
isEmpty() Determine if the list is empty
remove(int index|Object o) Delete the specified element
set(int index, E e) Set index th element int size()
int size() Get the number of elements in the list

What is Linked List?

LinkedList represents a linked list that references elements with bidirectional links. Due to its nature, inserting / deleting elements is faster than ArrayList because it only requires relinking. On the other hand, it has the property that it is not good at random access by index value. For this reason, LinkedList will be used in situations where there are many insert / delete operations, and ArrayList will be used in other cases. The methods that can be used in the LinkedList class are the same as ArrayList, so please refer to that as well. The following is an example of setting elements in LinkedList and reading their contents in order.

·merit When adding or subtracting elements, rewriting the link information is the end, so it is faster than ArrayList because the relocation process is not performed.

·Demerit Since each element does not hold a sequence number, when retrieving a specific element, it is necessary to count the sequence one by one from the beginning or the end, so compared to the ArrayList that holds the sequence number in advance. , It will take a lot of time.

Conclusion

ArrayList is used when random access is required for elements and there is not much need for insert / delete operations for elements in the array. LinkedList is used when the addition / deletion process is frequently required in addition to the last element and access to a specific element is not required.

reference

How to use LinkedList and ArrayList properly ArrayList class

Recommended Posts

Difference between ArrayList and LinkedList
Difference between List and ArrayList
LinkedList and ArrayList
[Java] Difference between array and ArrayList
Difference between EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA in ArrayList
Difference between vh and%
Difference between i ++ and ++ i
[Java] Difference between == and equals
Rails: Difference between resources and resources
Difference between puts and print
Difference between CUI and GUI
Difference between variables and instance variables
Difference between mockito-core and mockito-all
Difference between bundle and bundle install
Difference between render and redirect_to
Difference between .bashrc and .bash_profile
Difference between StringBuilder and StringBuffer
Difference between render and redirect_to
Difference between render and redirect_to
[Ruby] Difference between get and post
Difference between instance method and class method
Difference between render method and redirect_to
Difference between == operator and equals method
[Java] Difference between Hashmap and HashTable
[Terminal] Difference between irb and pry
JavaServlet: Difference between executeQuery and executeUpdate
[Ruby] Difference between is_a? And instance_of?
Difference between == operator and eqals method
Rough difference between RSpec and minitest
[Rails] Difference between find and find_by
Understand the difference between each_with_index and each.with_index
Difference between instance variable and class variable
[JAVA] Difference between abstract and interface
Difference between Thymeleaf @RestController and @Controller
Difference between Stream map and flatMap
Difference between primitive type and reference type
Difference between string.getByte () and Hex.decodeHex (string.toCharaArray ())
[Java] Difference between Closeable and AutoCloseable
[Java] Difference between StringBuffer and StringBuilder
[Java] Difference between length, length () and size ()
[rails] Difference between redirect_to and render
[Android] Difference between finish (); and return;
Note: Difference between Ruby "p" and "puts"
Difference between final and Immutable in Java
[Memo] Difference between bundle install and update
Difference between pop () and peek () in stack
[For beginners] Difference between Java and Kotlin
Difference between isEmpty and isBlank of StringUtils
Difference between getText () and getAttribute () in Selenium
About the difference between irb and pry
Difference between "|| =" and "instance_variable_defined?" In Ruby memoization
Difference between addPanel and presentModally of FloatingPanel
[Ruby] Difference between print, puts and p
[Java] Difference between Intstream range and rangeClosed
Difference between int and Integer in Java
[Rails] Difference between redirect_to and render [Beginner]
[Java] Understand the difference between List and Set
Difference between render and redirect_to, need for arguments
[Rails / ActiveRecord] About the difference between create and create!
[Java] Difference between Closeable and AutoCloseable
== and equals
Understand the difference between abstract classes and interfaces!