Qaysi ma'lumotlar tuzilmasida yangi element qo'shish tezroq amalga oshiriladi: LinkedList yoki ArrayList?

LinkedList ga yangi element qo'shish odatda ArrayList ga qaraganda tezroq bo'ladi, ayniqsa qo'shish ro'yxat oxirida bo'lmasa.

Sababi shundaki, LinkedList ikki tomonlama bog'langan ro'yxat bo'lib, har bir element oldingi va keyingi havolalarni o'z ichiga oladi. Qo'shish uchun faqat bir nechta havolalarni o'zgartirish kerak, bu pozitsiya ma'lum bo'lsa, O(1) vaqt oladi.

ArrayList esa ma'lumotlarni massivda saqlaydi. O'rta yoki boshida qo'shish uchun, barcha keyingi elementlarni siljish kerak, bu O(n) vaqt oladi.

Ammo, agar qo'shish oxirida bo'lsa:

• ArrayList elementni amortizatsiya qilingan O(1) vaqtda qo'shadi (agar massivni kengaytirish talab qilinmasa).
• LinkedList ham O(1) da qo'shadi, agar oxirgi elementga havola bo'lsa.

Shuning uchun, tasodifiy pozitsiyaga qo'shish uchun LinkedList tezroq, oxiriga qo'shish uchun — taxminan bir xil ishlash ko'rsatkichlariga ega.