ArrayList vs. LinkedList

There has been quite a bit discussion already. So just sum up by a few words:

ArrayList

• Lookup by index is O(1). (in Java, it implements RandomAccess) Suitable for dataset with random access pattern.
• Insertion can be expensive. Worst case O(n).
  1. Insertion to the middle can cause shifting.
  2. Insertion to the end can cause changing in the size of the internal storage, usually doubling.
• Deletion Depending on the implementation, it may vary a bit. Generally not bad.
  

LinkedList

• Lookup by index is O(n) in worst case. (in Java, it implements Queue). Suitable for data set that most of operations against it is iteration, or access mostly happens at the beginning or the end, such as FIFO queues, FILO stacks.
• Insertion is O(1)
• Deletion
  1. Deletion by reference is O(1)
  2. Deletion by value is as bad as lookup.

General thoughts:

Comparing two data structures, always at least think from two perspectives:

1. operations: lookup, insertion, deletion, manipulation.
2. input data characteristics: matching the characteristics with the cost of each operation to find the better data structure to solve your problem.

Online selection algorithm. Random Selection in Linked Lists with Unknown Length

Question: Given a finite linked list with unknown length(in terms of nodes count), select one item(multiple nodes) with equal possibility for every node in the linked list.

* One item only.
Assuming the input list has k nodes. The possibility for each node to be selected is 1/k. We need to guarantee that after we visiting m nodes, the possibility for each node is 1/m.



Proof of correctness:
When i = 0, node 0 is selected with 100% possibility.
When i = 1, node 1 has 50% chance to replace node 0 as selection result. Both of node 1 and node 0 will have equal chance to be chosen.
When i = n(which means we are testing the (n+1)th node), before line 3 is executed, all nodes from node 0 to node n-1 have possibility of 1/n to be selected. The (n+1)th node has 1/(n+1) possibility to be selected at line 3. For the previous selected node, it has a possibility of n/(n+1) to survive this round. Multiplying with its chance to be selected: 1/n, we get 1/(n+1) as well,

*Extended: Multiple items.
Assuming we have k nodes in the list and we are targeting a result set of size m,
each node will have possibility of m/k to be added to the result set.