Skip to main content

Difference between ArrayList and LinkedList

What is the difference between ArrayList and LinkedList

First of all lets see what Interfaces they implement.
  • ArrayList (See on Oracle/sun site)
    • Serializable
    • Cloneable
    • Iterable<E>
    • Collection<E>
    • List<E>
    • RandomAccess
  • LinkedList(See on Oracle/Sun site)
    • Serializable
    • Cloneable
    • Iterable<E>
    • Collection<E>
    • Deque<E>
    • List<E>
    • Queue<E>
By looking at interface being implemented by these two collection, we could see RandomAccess is implemented by ArrayList and Queue<E>,Deque<E> implemented by LinkedList only. So all the differences between these two collections are because of these three Interfaces and their implementation.

  1. RandomAccess : ArrayList can be accessed randomly, means we could access nth element of an ArrayList directly without affecting search/seek performance. e.g. list.get(n). Means get performance of nth element will never depend on how large is the ArrayList.It will remain constant.
    While LinkedList cant be accessed randomly(though it does have get(0) function but internally its done sequentially), means if you want to access nth element, you will have to access n-1 elements too.So the get/seek performance will always depends on how large is LinkedList and which elemnt you are looking for, smaller is faster , bigger is slower
  2. List Manipulation :
    Insertion at the end : Performance for insertion at the end of ArrayList or LinkedList will remain almost same(ArrayList have slight edge), as linked list keep a pointer at the end of List(Queue,DeQueue) and dont need to traverse other items in the list.
    If you are have requirment just to insert at the end of list and then iterate, think about ArrayList.
    Insertion at the Start: Performance for insertion at the Start of ArrayList will be affected by Size of array already allocated, total number of records in the list. At insert if your underlying array is already full then first array Relocation will happen then all elements after n will be pushed
    but in linked list performance wont be affected by such fators,as linked list keep as pointer at the start of list (Dequeu interface).
    So if you have requirment of inserting items at start and then just iterating, think about LinkedList.
    Insertion at random index :
    ArrayList : In arraylist index item can be reached without any performance degradtion but to insert it the underlying array need to be updated, means all element after n index need to be pushed and that will cost performance.Also there may be memory relocation for underlying array. The worst scenerio will be when you are trying to insert at 0th postion and you have already used underlying allocated array space and best when at the end.
    LinkedList : In Linked list to reach at nth element, first we need to traverse n-1 element(cost performance) and then insert it without any loss of performace(as it was in case of ArrayList). So in case of LinkedList best case is when you insert at 0th location and worst when you insert at end-1 position.
I will do a bench mark later and post result here. If you have becnhmarked and have some chart/graph, let me know i will post it here.


    Comments

    Popular posts from this blog

    Understanding Equals and hashCode contract,and what can go wrong

    SO what about Equals and hashcode?
    Most people will say these are the two basic function available in Object class and could be called from any Class object created in Java. Well thats true but there is more then this.
    First take a look at HashCode:
    Every JVM provides a good hashCode implementation mostly based on the object's memory location and for two different object(by location) it produce different hashCode.
    And at the same time Equal method also consider two different memory location object as Not Equal. So at core two are in a contract and works great.

    But as soon as start writing code and write a class and create a state of a class(means create few data variables in a class), the core contract of hashCode and Equal doesnt work any more.
    e.g.
    Class MyFirstCLass{ int value; public MyFirstCLass(int value){ this.value = value; } } MyFistCLass obj1 = new MyFirstCLass(10); MyFistCLass obj2 = new MyFirstCLass(10);
    Now obj1 and obj2, theoratically should be equal as both holds …

    Validate HTML as XHTML in Intelij

    When working in intelij with HTML, sometimes we need to make sure our HTML is XHTML compliance, no un ened tags etc.
    i.e. we should not have

    <img src="myimage.jpg> If You put above code in an HTML and run it in browser it will work fine, but if you are using some server side framework like Thymeleaf with Spring, it will generate error saying <img> tag must be terminated.

    By Default intelij will not complaint about this and when you are writing HTML you may ignore the error and will get the error when you actually run it with in server. Or worst some HTML developer is writing the code HTML code for you and then you will have to fix all these errors.

    Intelij can help you to make sure you write a valid HTML(XHTML). You can enable XHTML validation for HTML files by following below steps.

    Go to Settings(Windows)/Preference(mac) in Intelij.Search for "File Types"Find HTML as shown in image below. You will see HTML has some extension associated with like *.html, *…