So removing the last element of the ArrayList is O(1) where as for the first element is O(n). Removing element from an ArrayList requires less time reaching to the element that has to be removed (just accessing the array index) but requires shifting all the elements, after the element that has to be removed, backward to fill the space left by the removed element. LinkedList insertion is O(1) as adding element just requires to adjust references for previous and next nodes.īut one thing to note here is that the constant factor in ArrayList is low compared to that for the LinkedList implementation. With all these possibilities while adding element to the ArrayList, add operation in ArrayList runs in amortized constant time, that is, adding n elements requires O(n) time. Same overhead is there of you add element using the add(int index, E element) method to add element at the specified position. If elements are frequently added to the beginning of the ArrayList then also there is added overhead of shifting all the elements of the array to make place for the new element.
If array is full then the insertion of next element in the ArrayList would require resizing the array and moving all the existing element of the ArrayList to the new array. Since array is created as a contiguous memory block so adding element in an ArrayList is as simple as putting element in the next index but there are some complexities involved. LinkedList in Java doesn’t have any initial capacity, as and when an element is added object of type Node is created.ĪrrayList in Java has an array of size 10 created by default even if internal capacity is not specified. Even if no initial capacity is specified ArrayList is created with the default capacity of 10. In the node object apart from the element, references of the previous and next nodes are also stored.ĪrrayList has a constructor ArrayList(int initialCapacity) which can construct an ArrayList of the specified capacity. LinkedList is internally implemented as a doubly linked list where elements are stored as object of type node. The size of the array can be increased dynamically if needed that is why ArrayList is known as the resizeable array implementation. ArrayList Vs LinkedList in JavaĪrrayList internal implementation uses an array to store its element.
Knowing the differences between ArrayList and LinkedList will also help you to determine which implementation is better in which scenario. In this post we’ll see the differences between ArrayList and LinkedList in Java to understand these two implementations better. In Java Collections framework there are two general-purpose List implementations- ArrayList and LinkedList.