beginnersbook.com

  • Home
  • All Tutorials
    • Learn Servlet
    • Learn JSP
    • Learn JSTL
    • Learn C
    • Learn C++
    • Learn MongoDB
    • Learn XML
    • Learn Python
    • Learn Perl
    • Learn Kotlin
  • Core Java
  • OOPs
  • Collections
  • Java I/O
  • JSON
  • DBMS

Difference between ArrayList and LinkedList in Java

By Chaitanya Singh | Filed Under: Java Collections

ArrayList and LinkedList both implements List interface and their methods and results are almost identical. However there are few differences between them which make one better over another depending on the requirement.

ArrayList Vs LinkedList

1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).

Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.

2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (While removing last element).

Conclusion: LinkedList element deletion is faster compared to ArrayList.

Reason: LinkedList’s each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.

3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in worst case. Reason is same as explained for remove.

4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes hence the memory consumption is high in LinkedList comparatively.

There are few similarities between these classes which are as follows:

  1. Both ArrayList and LinkedList are implementation of List interface.
  2. They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
  3. Both these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method.
  4. The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException).

When to use LinkedList and when to use ArrayList?

1) As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)). Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.

2) Search (get method) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n)) so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

References:

  • ArrayList documentation
  • LinkedList Javadoc

Enjoyed this post? Try these related posts

  1. Vector Enumeration example in Java
  2. How to override toString method for ArrayList in Java
  3. Vector in Java
  4. Get size of Hashtable example in Java
  5. Java – Remove mapping from HashMap example
  6. TreeMap in Java with Example

Comments

  1. krishna kumar gupta says

    June 19, 2014 at 7:38 AM

    really great explanations

    Reply
  2. Subhankar Adhikary says

    July 7, 2014 at 7:09 PM

    I am new in java. I want to know basic difference between ArrayList and LinkList. This is nice article. Nice Job. Nice explained. Its really helps me.

    Reply
  3. vairam says

    September 12, 2014 at 3:06 PM

    very gud explanation. Superb.

    Reply
  4. enadun says

    September 28, 2014 at 4:17 PM

    Thanks a lot. Fully satisfied answer !

    Reply
  5. Anshuman Dwivedi says

    November 12, 2014 at 3:51 AM

    You said –
    The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods.
    How are you going to add element via iterator ?

    Reply
  6. Subbareddy says

    December 22, 2014 at 1:46 PM

    Hi,
    This post is really good. But, In the above I have one doubt. while searching arraylist follows O(1) because of index. At the same time why arraylist will not follow same one while deletion.
    regards,
    Subbareddy

    Reply
    • Neel Mehta says

      January 20, 2015 at 6:12 AM

      ArrayList doesn’t follow the same for delete since even though it can find the element at the given index fairly quickly, it has to shift all the elements at the later indices back one so that the empty index of the deleted element gets filled.

      Reply
      • Mfily says

        June 25, 2015 at 9:52 PM

        It’s really a nice post but i want to know the definition of array list and linked list I can’t get the definition.

        Reply
    • Prince Abhijeet says

      February 20, 2017 at 5:00 PM

      You see: ArrayList has indexes and LinkedList has pointer to next node. So deleting an item of ArrayList will cause next items to shift left so shifting takes more time. Whereas in case of LinkedList when an item is deleted there is no need to shift left the next items, only thing is needed is to point the pointer to the next node.

      Reply
    • Anonymous007 says

      June 20, 2017 at 5:33 AM

      An arrayList stores data at contiguous memory locations, so when deletion operation is performed it creates an empty space in arrayList. This empty space has to be occupied again by performing large number of shift operations. And hence DELETION from arrayList does not give O(1).

      Reply
  7. robert says

    August 8, 2015 at 10:17 AM

    why isn’t array list implemented to insert an item to the end -> so no reindexing would be needed and the insert operation would be O(1) ? If I wanted to delete an item from linked list, wouldn’t it be needed to search for the item firstly (so it would be O(n) ) ?

    Reply
  8. Michael says

    November 24, 2015 at 8:16 AM

    Dear Robert, this is what I asked myself, too. I looked into the code and remove has O(n). If you use iterator for remove or add, then you have O(1).

    See Stackoverflow: http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist

    Reply
  9. Paras Mehta says

    December 2, 2015 at 1:19 PM

    Isn’t array list add is O(1) as it adds element at the end. Insertion order is maintained. So add should be O(1) only….

    Reply
  10. Wasim says

    July 5, 2016 at 1:03 PM

    Superb explanation :)

    Reply
  11. Ilia says

    July 28, 2016 at 11:24 AM

    Great, thanks! And what about editing the data? Which one is better if you change it a lot? Like if the type is integer and you constantly increase the values of the items. Sorry, if the question is stupid.

    Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Java Tutorial

  • Java Tutorial
  • OOPs Concepts

Java Collections

  • ArrayList
  • LinkedList
  • ArrayList vs LinkedList
  • Vector
  • ArrayList vs Vector
  • HashMap
  • TreeMap
  • LinkedHashMap
  • HashSet
  • TreeSet
  • LinkedHashSet
  • Hashtable
  • HashMap vs Hashtable
  • Queue
  • PriorityQueue
  • Deque & ArrayDeque
  • Iterator
  • ListIterator
  • Comparable Interface
  • Comparator Interface
  • Java Collections Interview Q

MORE ...

  • Java String
  • Exception handling
  • Java Multithreading
  • Java I/O
  • Java Serialization
  • Java Regex
  • Java AWT
  • Java Swing
  • Java Enum
  • Java Annotations

Copyright © 2012 – 2021 BeginnersBook . Privacy Policy . Sitemap