هو أكثر كفاءة لإزالة العناصر من ArrayList أو قائمة متصلة؟
-
10-07-2019 - |
سؤال
في نظرية، هو أكثر كفاءة لإزالة عناصر من ArrayList
أو LinkedList
؟
المحلول
وومن "أسهل" (أي، أكثر كفاءة) لإزالتها من LinkedList
، لأن إزالة من ArrayList
يتطلب نقل جميع العناصر اللاحقة إلى موضع جديد في القائمة كل العناصر اللاحقة للمجموعة يجب تعيين ل قيمة جديدة. مع قائمة مرتبطة، مؤشر واحد فقط (أو اثنين، مع قائمة مرتبطة مضاعف) يجب أن يعاد تعيينه.
نصائح أخرى
حسنا، وإزالة عنصر من (مضاعف linked-) القائمة O (1). ولكن إزالة من مجموعة سيتطلب أن العناصر المتبقية وتحولت إلى أسفل مسافة واحدة في مجموعة، والتي هي O (ن).
وقال ذلك، الحصول على عنصر معين في القائمة حسب مؤشر وO (ن)، في حين أن الحصول على عنصر معين في مجموعة من مؤشر وO (1).
وهكذا، لإزالة الفعلية، قائمة متصلة سيكون أفضل. هناك مزيد من المعلومات عن صفيف في مقابل قائمة متصلة هنا .