4069

Mar 20, 2016

LinkedList and ArrayList both are ordered collections and implements List interface. These two Arraylist and linkedlist implementation has their own advantage and disadvantages and should be used based on the need. Here is a comparison and difference between these two implementations.

# | Point | LinkedList | ArrayList |
---|---|---|---|

1 | Nature | LinkedList is Sequential Access | ArrayList is Random Access |

2 | Internal Implementation | LinkedList is implemented by Doubly-linked list | ArrayList is implemented by Array |

3 | get(index) complexity | LinkedList is of O(n), needs to iterate over elements | ArrayList is of O(1), direct access |

4 | add(element) complexity | LinkedList is O(1), always has pointer to last element, just add a new node | ArrayList is O(1) * O(n) in worst-case if array capacity reached to modCount and array needs to be resized and copied |

5 | add(index,element) complexity | LinkedList is of O(n), need to iterate till nth element | ArrayList is of O(n-index), (n-index) element needs to be shifted* O(n) in worst-case if array capacity reached to modCount and array needs to be resized and copied |

6 | ListIterator.add(element) complexity | LinkedList is of O(1), only pointers needs to be adjusted | ArrayList is of O(n-index), (n-index) element needs to be shifted * O(n) in worst-case if array capacity reached to modCount and array needs to be resized and copied |

7 | remove(index) complexity | O(n), need to iterate to reach nth element | O(n-index), (n-index) element needs to be shifted |

8 | ListIterator.remove(element) complexity | O(1), only pointers needs to be adjusted | O(n-index), (n-index) element needs to be shifted * O(n) in worst-case if array capacity reached to modCount and array needs to be resized and copied |

9 | Memory usages | More, previous and next pointers to be maintained | Less |

In summary if most of the operations are insertion/deletion at beginning or end of list then linked-list is most useful (for example implementation of Queues) otherwise ArrayList has more advantages over LinkedList.

PopularRESTful web-services to get and search CountriesFree RESTful web services to Consume and TestFree Restful web service to get location geolocation by IP addressRESTful web-service to get and search States and territories of a CountrySession timeout handling in Java

© Copyright 2020