About Array, ArrayList, LinkedList

Array:

1. Fixed length data structure, cannot change length once created

2. Cannot user Generics.

3. All kinds of Array provideslength variable which denotes length of Arra, array.length to get length

4. Allow both primitives and Objects. (int[], Object[])

5. You can simply use assignment operator to store element into Array. (int[] i = new int[10]; int[1] = 1;)

6. Must provide size when init.

ArrayList:

1. Dynamic length, however, re-size is slow (create a new array and copying content from old to new)

2. Allows to use Generics to ensure type safe.

3. All kinds of Array provideslength variable which denotes length of Arra, arraylist.size() to get size

4. Only allow Objects but not primitives. (ArrayList)

5. Java provides add() method to insert element into ArrayList.

6. Do not need to provide size when init.


--------------------------------------------------
ArrayList:
1. Index based data-structure. O(1) for search, get(index).

2. Add element, O(1) if doesn't trigger re-size of the array. O(log(n)) if re-size.

3. O(n) for remove and insert, need to re-arrange all elements.

4. Less memory overhead, because ArrayList each index only holds actual object (data).


LinkedList:

1. O(n) for search(get) element.

2. O(1) for add element.

3. For insert or remove element, still need O(n) to travers to that pointer (can traverse from either direction based upon proximity)

4. More memory overhead, because LinkedList each node holds both data and address of next and previous node.