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

    How to add custom user attributes in keycloak and access them in spring boot application

    Sometime it may be possible you want to add more parameters to standard registration page of keyloak for your users and aaccess that data in your spring boot application. This artical will show step by steps on how to add such extra attributes. What is Keycloak Keycloak is an open source software product to allow single sign-on with Identity Management and Access Management aimed at modern applications and services, to learn more visit  h ttps://www.keycloak.org/ What is Spring boot Spring Boot makes it easy to create stand-alone, production-grade Spring based Applications that you can "just run". To learn more visit  https://spring.io/projects/spring-boot To add an extra attribute in keyclkoak server you will need to edit actuall html template and then registaer new attribute in json response so that it will be available on client. Edit HTML template Lets assume we want to add mobile number on default registration page. Go to Keycloak home installation directory edit fil

    How to create java maven project in intelij

    Open intellij Create a new java maven project in intellij . Select Maven type, Select JDK you want to use and click Next. Enter GroupId and ArtifactId, click Next Select project Location and click finish Intelij will display a warning, just press Ok. Once project is created , a popup may appear asking for auto import, select "Enable Auto Import" You will have a project created, looking something like this Note: I have created these instructions using, Instruction for other OS or intellij Version shouldn't be much different, if you need instruction for other version leave a comment and i will try to come up with another set of instructions. Intellij 2017.2.1 Java 1.8 Mac OS

    How to git without finger print confirmation

    In this article i will explain how you can run git clone command on a machine without having to accept sh key finger prints manually. Lets you want to write a script to initialise a developer machine, which require you to git clone various projects from gitlab or github or any other git repo. First time you run a git clone command, it will ask you if you accept the signature and it need to be part of automated script, its not nice thing to have. Here is the solution. First you download the git host's key then create its finger print then check this finger print against known valid finge rprint If its good then move downloaded ssh key to ~/.ssh/known_hosts file else throw error ssh-keyscan github.com >> githubKey ssh-keyscan gitlab.com >> gitlabKey export githubfinger=$(ssh-keygen -lf githubKey) export gitlabfinger=$(ssh-keygen -lf gitlabKey) echo $githubfinger echo $gitlabfinger if [[ $githubfinger == *"nThbg6kXUpJWGl7E1IGOCspRomTxdCARL