هو أكثر كفاءة لإزالة العناصر من ArrayList أو قائمة متصلة؟

Question

في نظرية، هو أكثر كفاءة لإزالة عناصر من ArrayList أو LinkedList؟

Answer 1

وومن "أسهل" (أي، أكثر كفاءة) لإزالتها من LinkedList، لأن إزالة من ArrayList يتطلب نقل جميع العناصر اللاحقة إلى موضع جديد في القائمة كل العناصر اللاحقة للمجموعة يجب تعيين ل قيمة جديدة. مع قائمة مرتبطة، مؤشر واحد فقط (أو اثنين، مع قائمة مرتبطة مضاعف) يجب أن يعاد تعيينه.

Answer 2

حسنا، وإزالة عنصر من (مضاعف linked-) القائمة O (1). ولكن إزالة من مجموعة سيتطلب أن العناصر المتبقية وتحولت إلى أسفل مسافة واحدة في مجموعة، والتي هي O (ن).

وقال ذلك، الحصول على عنصر معين في القائمة حسب مؤشر وO (ن)، في حين أن الحصول على عنصر معين في مجموعة من مؤشر وO (1).

وهكذا، لإزالة الفعلية، قائمة متصلة سيكون أفضل. هناك مزيد من المعلومات عن صفيف في مقابل قائمة متصلة هنا .