Question

Analysis
In java, a List can be implemented in a number of ways. Compare and contrast an ArrayList and a LinkedLists. In which situations would you use one to implement a List over another?

(explain in runtime on add and remove, memory usage, and get/set.)

Answer 1

ArrayList and LinkedLists both implements list interface . They both are used to store large amount of data of similar type like marks of 1000 students. All operations they provide are same , difference lies in the performance of various operations , so according to the problem ,operations required frequently are identified and a decision is made between ArrayList and LinkedList.

While deciding which one to use , following points must be kept in mind :

Difference between Arraylist and LinkedList

ArrayList	LinkedList
It uses dynamic array to store elements.	It uses doubly linked list to store elements.
Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the bits are shifted in memory.	Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory.
Get/Set operations can be done in O(1) , since they are directly accessed using indexes.	Get/Set operations are done in O(n). LinkedList has to be travelled to the required positions.
ArrayList requires resizing which makes insertion and deletion slow , whenever arraylist gets full , it resize itself to make space for newer elements and this operation is O(n) in time complexity in worst case.	Adding data or removing data in Linked list is O(1) if adding at the beginning or end , but if to be added in middle somewhere, time complexity will be O(n).
In arrayList , each index always holds actual object (actual data) .So , memory required is less.	In linkedList, each node holds actual object(data) , as well address of previous and next node. Therefore , memory required is more per node in linked List.
Finding an element requires O(n) time but here data may be sorted and binary search can be applied , reducing the time complexity to O(log n).	Finding an element requires O(n) time .

So , we can say ArrayList is better for storing and accessing data but linked list is better for manipulating data.