Arrylist and linked list difference in java

In Java collections framework ArrayList and LinkedList are two different implementations of List interface (LinkedList also implement Deque interface though). In most of the cases we do use ArrayList and it works very well but there are some use cases where using LinkedList may be a better choice. So let's see some of the differences between ArrayList and LinkedList in Java, it will help you in making an informed choice when to use ArrayList and when a LinkedList. ArrayList Vs LinkedList in Java 1- If we have to list the differences between the LinkedList and ArrayList in Java, first difference is in the implemenation itself- LinkedList is implemented using a doubly linked list concept where as ArrayList internally uses an array of Objects which can be resized dynamically. 2- ArrayList class provides a constructor ArrayList(int initialCapacity) even if the default constructor ArrayList() is used an empty list is constructed with an initial capacity of ten. Where as LinkedList just provides one constructor LinkedList() which constructs an empty list. Note that in LinkedList there is no provision of initial capacity or default capacity. What it means is that if elements are added at the last every time and capacity is not breached then ArrayList will work faster because it already has an initial capacity and just need to add that element at the index in the underlying array. Where as in LinkedList a new node has to be created and references for Next and Prev are to be adjusted to accommodate the new Node.

Refer post How ArrayList works internally in Java to know more about internal working of ArrayList.

Refer post How Linked List class works internally in Java to know more about internal working of LinkedList. 3- One more difference is that LinkedList implementation provides a descendingIterator() which comes from implementing the Deque interface. descendingIterator() returns an iterator over the elements in this deque in reverse sequence. In ArrayList there is no such iterator. ArrayList Vs LinkedList performance wise It is mainly the performance in specific scenarios which dictates whether to go with ArrayList or with LinkedList. Let's go through some of the operations to see how ArrayList Vs LinkedList fares performance wise. Adding an element- If you are frequently adding element at the beginning of the listthen LinkedList may be a better choice because in case of ArrayList adding at the beginning every time will result in shuffling all the existing elements within the underlying array by one index to create space for the new element. In the case of adding at the last ArrayList may give O(N) performance in the worst case. That will happen if you add more elements than the capacity of the underlying array, as in that case a new array (1.5 times the last size) is created, and the old array is copied to the new one. So for LinkedList add(e Element) is always O(1) where as for ArrayList add(e Element)operation runs in amortized constant time, that is, adding n elements requires O(N) time. So the amortized time (i.e. time per insertion) is O(1). Retrieving an element- Retrieving an element from the list using get(int index) is faster in ArrayList than in LinkedList. Since ArrayList internally uses an array to store elements so get(int index) means going to that index directly in the array. In Linked list get(int index) will mean traversing through the linked list nodes. So, for ArrayList get(int index) is O(1) where as for LinkedList get(int index) is O(N). Removing an element- If you are removing element from a list using the remove(int index) method then for LinkedList class it will be O(N) as list has to be traversed to get to that index and then the element removed. Though the LinkedList provides methods like removeFirst() and removeLast() to remove the first or last element and in that case it will be O(1). In case of ArrayList getting to that index is fast but removing will mean shuffling the remaining elements to fill the gap created by the removed element with in the underlying array. It ranges from O(1) for removing the last element to O(N). Thus it can be said remove(int index) operation is O(N - index) for the ArrayList. Removing an element while iterating- if you are iterating the list and removing element using iterator.remove() then for LinkedList it is O(1) as the iterator is already at the element that has to be removed so removing it means just adjusting the Next and Prev references. Where as for ArrayList it is again O(N - index) because of an overhead of shuffling the remaining elements to fill the gap created by the removed elements. While using ArrayList we generally use add() method, very rarely we use add method where index is also passed to add element at any specific position in the ArrayList and to fetch elements from List we use get(int index) which also is faster in ArrayList. That's why we normally use ArrayList, even JavaDocs advocate the same thing-

Related blog:

Spring boot hibernate crud example with mysql

Recommended Posts

Arrylist and linked list difference in java
Difference between final and Immutable in Java
Difference between int and Integer in Java
[java] sort in list
[Memo] Java Linked List
[Java] Understand the difference between List and Set
Difference between next () and nextLine () in Java Scanner
[Java] Difference between == and equals
[Java] Difference between static final and final in member variables
Difference between List and ArrayList
java Generics T and? Difference
List aggregation in Java (Collectors.groupingBy)
Difference between element 0, null and empty string (check in list)
Is short-circuit evaluation really fast? Difference between && and & in Java
[Java] Difference between Hashmap and HashTable
Encoding and Decoding example in Java
StringBuffer and StringBuilder Class in Java
[JAVA] Difference between abstract and interface
List of members added in Java 9
Understanding equals and hashCode in Java
List of types added in Java 9
[Java] Difference between Closeable and AutoCloseable
[Java] Difference between StringBuffer and StringBuilder
[Java] Difference between length, length () and size ()
Hello world in Java and Gradle
Sort List in descending order in Java and generate a new List non-destructively
Difference between pop () and peek () in stack
[Java] for Each and sorted in Lambda
Change List <Optional <T >> to Optional <List <T >> in Java
Immutable (immutable) List object conversion function in Java8
[Java 7] Divide the Java list and execute the process
Difference between "|| =" and "instance_variable_defined?" In Ruby memoization
Difference between EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA in ArrayList
Process every arbitrary number in Java List
Program PDF headers and footers in Java
[Java] Difference between Intstream range and rangeClosed
Learn Flyweight patterns and ConcurrentHashMap in Java
Java Direction in C ++ Design and Evolution
[Java] Contents of Collection interface and List interface
Java to C and C to Java in Android Studio
Reading and writing gzip files in Java
Do not declare variables in List in Java
Discrimination of Enums in Java 7 and above
Understand the difference between int and Integer and BigInteger in java and float and double
Regarding the transient modifier and serialization in Java
Create barcodes and QR codes in Java PDF
Detect similar videos in Java and OpenCV rev.2
Partization in Java
Java memorandum (list)
Clone Java List.
Changes in Java 11
Rock-paper-scissors in Java
Detect similar videos in Java and OpenCV rev.3
Add, read, and delete Excel comments in Java
Check static and public behavior in Java methods
[Java] Understand in 10 minutes! Associative array and HashMap
Java and JavaScript
XXE and Java
Distinguish between positive and negative numbers in Java
Java adds and removes watermarks in word documents
Detect similar videos in Java and OpenCV rev.1