TheHorse, это основы даже не Java а теории структур и алгоритмов. Если нет совсем хитрой подоплёки в вопросах, я действительно даже не знаю что тут отвечать ещё))
1. для вставки я бы задумался, тут есть нюансы. Но я знаю как работает и тот и другой и в теории и в реализации стандартной библиотеки Java, так что придумал бы) как комментатор выше я тоже склонился бы к ArrayList в данном случае
2. в теории сложностей алгоритмов да, гарантирует, разумеется, допуская наихудшее
3. не очень понял, по сути порядок вставки не важен, или речь про выборку