Which Implementation of the List Interface Provides for the Fastest Insertion of a new Element into the Middle of the List?

Vector, ArrayList, LinkedList

ArrayList and Vector both use an array to store the elements of the list. When an element is inserted into the middle of the list the elements that follow the insertion point must be shifted to make room for the new element.

The LinkedList is implemented using a doubly linked list; an insertion requires only the updating of the links at the point of insertion. Therefore, the LinkedList allows for fast insertions and deletions.