عند استخدام LinkedList على ArrayList في جافا ؟

Question

أنا كنت دائما واحدة ببساطة استخدام:

List<String> names = new ArrayList<>();

يمكنني استخدام واجهة مثل اكتب اسم قابلية, بحيث عندما نسأل أسئلة مثل هذه لا يمكن صياغة قانون بلدي.

متى يجب أن LinkedList تستخدم على ArrayList والعكس بالعكس ؟

Answer 1

ملخص ArrayList مع ArrayDeque هي الأفضل في العديد من أكثر حالات الاستخدام من LinkedList.إذا كنت غير متأكد — تبدأ فقط مع ArrayList.

---

LinkedList و ArrayList اثنين من تطبيقات مختلفة من القائمة واجهة. LinkedList تنفذ ذلك مع مضاعفة-قائمة مرتبطة. ArrayList تنفذ ذلك مع حيوي إعادة التحجيم مجموعة.

كما هو الحال مع معيار قائمة مرتبطة و مجموعة العمليات المختلفة أساليب مختلفة حسابي أوقات التشغيل.

بالنسبة LinkedList<E>

• get(int index) هو O(n) (مع n/4 خطوات في المتوسط)
• add(E element) هو س(1)
• add(int index, E element) هو O(n) (مع n/4 خطوات في المتوسط) ، ولكن س(1) عندما index = 0 <--- الفائدة الرئيسية LinkedList<E>
• remove(int index) هو O(n) (مع n/4 خطوات في المتوسط)
• Iterator.remove() هو س(1).<--- الفائدة الرئيسية LinkedList<E>
• ListIterator.add(E element) هو س(1) هذه هي واحدة من الفوائد الرئيسية من LinkedList<E>

^{ملاحظة:العديد من العمليات التي تحتاج n/4 خطوات في المتوسط ، ثابت عدد من الخطوات في أفضل الأحوال (مثلا ، index = 0) ، ن/2 خطوات في أسوأ الأحوال (منتصف القائمة)}

بالنسبة ArrayList<E>

• get(int index) هو س(1) <--- الفائدة الرئيسية ArrayList<E>
• add(E element) هو س(1) المطفأة ، ولكن O(n) أسوأ حالة منذ المصفوفة يجب أن يكون حجمها و نسخها
• add(int index, E element) هو O(n) (مع ن/2 خطوات في المتوسط)
• remove(int index) هو O(n) (مع ن/2 خطوات في المتوسط)
• Iterator.remove() هو O(n) (مع ن/2 خطوات في المتوسط)
• ListIterator.add(E element) هو O(n) (مع ن/2 خطوات في المتوسط)

^{ملاحظة:العديد من العمليات التي تحتاج ن/2 خطوات في المتوسط ، ثابت عدد من الخطوات في أفضل الأحوال (نهاية القائمة) ، n خطوات في أسوأ الأحوال (ابدأ من القائمة)}

LinkedList<E> يسمح ثابت وقت الإدراج أو الإزالة استخدام التكرار, ولكن فقط الوصول المتسلسل من العناصر.وبعبارة أخرى, يمكنك المشي قائمة إلى الأمام أو إلى الوراء ، ولكن العثور على وظيفة في قائمة يستغرق وقتا يتناسب مع حجم القائمة.جافادوك يقول "العمليات التي المؤشر في قائمة سوف اجتياز قائمة من بداية أو نهاية ، أيهما أقرب", حتى تلك الوسائل ، O(n) (n/4 خطوات) في المتوسط ، على الرغم من س(1) بالنسبة index = 0.

ArrayList<E>, من جهة أخرى ، تسمح بسرعة قراءة عشوائية الوصول حتى تتمكن من الاستيلاء على أي عنصر في وقت ثابت.ولكن إضافة أو إزالة من أي مكان ولكن في نهاية يتطلب تحويل جميع الأخير عناصر أكثر ، إما فتح أو ملء الفجوة.أيضا, إذا قمت بإضافة المزيد من العناصر من القدرات الكامنة مجموعة, مجموعة جديدة (1.5 مرة حجم) يتم تخصيص القديمة مجموعة نسخ إلى واحدة جديدة ، مشيرا بذلك إلى ArrayList هو O(n) في أسوأ الأحوال ولكن ثابتة في المتوسط.

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

الفوائد الرئيسية من استخدام LinkedList تنشأ عند إعادة استخدام القائمة التكرار لإدراج وإزالة العناصر.هذه العمليات ومن ثم يمكن القيام به في س(1) عن طريق تغيير القائمة محليا فقط.في مجموعة قائمة ، ما تبقى من مجموعة يحتاج إلى انتقلت (أينسخها).على الجانب الآخر يسعى في LinkedList يعني الروابط التالية في O(n) (ن/2 خطوات) على أسوأ الأحوال ، بينما في ArrayList المطلوب موقف يمكن حسابها رياضيا و الوصول إليها س(1).

فائدة أخرى من استخدام LinkedList تنشأ عند إضافة أو إزالة من رئيس القائمة منذ تلك العمليات س(1), بينما هم O(n) بالنسبة ArrayList.علما بأن ArrayDeque قد يكون بديل جيد LinkedList إضافة وإزالة من الرأس ، ولكن ليس List.

أيضا, إذا كان لديك قوائم كبيرة, نضع في اعتبارنا أن استخدام الذاكرة هي أيضا مختلفة.كل عنصر من عناصر LinkedList لديه المزيد من النفقات العامة منذ مؤشرات السابق " و " التالي العناصر أيضا تخزينها. ArrayLists لا يكون هذا الحمل.ومع ذلك ، ArrayLists تأخذ الكثير من الذاكرة كما يتم تخصيص القدرة ، بغض النظر عما إذا كانت العناصر قد تم إضافتها.

الافتراضي الأولي قدرة ArrayList صغير جدا (10 من جافا 1.4 - 1.8).ولكن منذ تنفيذ الأساسي هو مجموعة, مجموعة يجب أن يكون حجمها إذا قمت بإضافة الكثير من العناصر.لتجنب ارتفاع تكلفة تغيير حجم عندما كنت أعلم أنك سوف تضيف الكثير من عناصر بناء ArrayList مع ارتفاع القدرة الأولية.

Answer 2

حتى الآن يبدو أن لا أحد قد تناولت الذاكرة لكل من هذه القوائم إلى جانب التوافق العام في الآراء أن LinkedList هو "الكثير" من ArrayList لذا قمت ببعض عدد الطحن لإثبات بالضبط كم القائمتين أن ن null المراجع.

منذ المراجع إما 32 أو 64 بت (حتى عندما null) في النسبية النظم ، وقد شملت 4 مجموعات من البيانات 32 و 64 بت LinkedLists و ArrayLists.

ملاحظة: أحجام هو ArrayList خطوط على قلص قوائم - في الممارسة العملية ، فإن قدرة على دعم مجموعة في ArrayList عموما أكبر من الحالي عنصر الاعتماد.

ملاحظة 2: (شكرا BeeOnRope) كما CompressedOops هو الافتراضي الآن من منتصف JDK6 و حتى القيم أدناه لأجهزة 64 بت أساسا تطابق 32 بت النظراء ، ما لم يكن بالطبع كنت على وجه التحديد إيقاف تشغيله.

---

---

نتيجة يبين بوضوح أن LinkedList هو الكثير أكثر من ArrayList, خصوصا مع ارتفاع عنصر الاعتماد.إذا كانت الذاكرة هي عامل ، توجيه واضح من LinkedLists.

الصيغ اعتدت متابعة, اسمحوا لي أن أعرف إذا كنت قد فعلت أي شيء خطأ و سوف إصلاحه.'ب' إما 4 أو 8 32 أو 64 بت أنظمة 'n' هو عدد العناصر.ملاحظة سبب تعديل لأن جميع الكائنات في جافا سوف يستغرق متعددة من 8 بايت مساحة بغض النظر عما إذا كانت تستخدم أو لا.

ArrayList:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

Answer 3

ArrayList هو ما تريد. LinkedList هو دائما تقريبا (الأداء) علة.

لماذا LinkedList مقرف:

• يستخدم الكثير من الذاكرة الصغيرة الكائنات ، وبالتالي يؤثر الأداء عبر هذه العملية.
• الكثير من الأشياء الصغيرة هي سيئة بالنسبة ذاكرة التخزين المؤقت المحلية.
• أي فهرسة العملية يتطلب اجتياز أيوقد O(n) الأداء.هذا ليس واضحا في التعليمات البرمجية المصدر ، مما يؤدي إلى خوارزميات O(n) أبطأ مما لو ArrayList تم استخدامها.
• الحصول على الأداء الجيد هو صعب.
• حتى عندما big-O الأداء هو نفس ArrayList, فمن المحتمل ان تكون أبطأ بكثير على أية حال.
• إنه التنافر لرؤية LinkedList في المصدر لأنه ربما يكون خيار خاطئ.

Answer 4

وكما شخص الذي تم القيام الهندسة الأداء التشغيلية على نطاق واسع جدا الخدمات SOA على شبكة الإنترنت لحوالي عقد من الزمن، وأود أن تفضل سلوك قائمة متصلة على ArrayList. في حين أن سرعة ثابتة للدولة من قائمة متصلة هو أسوأ، وبالتالي قد يؤدي إلى شراء المزيد من الأجهزة - سلوك ArrayList تحت ضغط يمكن أن يؤدي إلى تطبيقات في كتلة توسيع صفائف في القريب التزامن ولأحجام مجموعة كبيرة يمكن أن تؤدي إلى عدم التجاوب في التطبيق وانقطاع، في حين تحت الضغط، والذي هو السلوك كارثية.

وبالمثل، يمكنك الحصول على إنتاجية أفضل في أحد التطبيقات من الإنتاجية الافتراضي مثبت جامع القمامة، ولكن بمجرد الحصول على تطبيقات جافا مع 10GB أكوام يمكنك يختتم حبس التطبيق لمدة 25 ثانية خلال GCS كامل والذي يسبب مهلة والفشل في SOA تطبيقات وضربات مستوى الخدمة الخاص بك إذا كان يحدث في كثير من الأحيان. على الرغم من أن جامع CMS يأخذ المزيد من الموارد ولا يحقق نفس سرعة نقل الخام، بل هو خيار أفضل بكثير لأنه يحتوي الكمون أكثر قابلية للتنبؤ وأصغر.

وArrayList ليست سوى الخيار الأفضل للحصول على أداء إذا كان كل ما تعني أداء غير الإنتاجية ويمكنك تجاهل الكمون. في تجربتي في وظيفتي لا أستطيع تجاهل أسوأ حالة الكمون.

Answer 5

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

الخوارزميات: كبير أوه تدوين

وArrayLists جيدة لأو appenders، ولكن سيئا على الإضافة مرة واحدة قراءة العديد الكتابة / إزالة من الأمام أو الوسط.

Answer 6

ونعم، وأنا أعلم، وهذا هو السؤال القديم، ولكن أنا رمي في بلدي اثنين سنتا:

وقائمة متصلة غير <م> دائما خيار خاطئ، والأداء الحكيم. هناك بعض خوارزميات محددة للغاية حيث يسمى قائمة متصلة ل، ولكن هذه هي غاية، نادرة جدا وسوف خوارزمية عادة ما يعتمد بشكل خاص على قدرة قائمة متصلة لإدراج وحذف العناصر في منتصف القائمة بسرعة نسبيا، وبمجرد أبحر هناك مع ListIterator.

وهناك حالة واحدة استخدام المشتركة التي يتفوق قائمة متصلة ArrayList: أن قائمة انتظار. ومع ذلك، إذا كان هدفك هو الأداء، بدلا من قائمة متصلة يجب عليك أن تنظر أيضا باستخدام ArrayBlockingQueue (إذا كان يمكنك تحديد الحد الأعلى لحجم قائمة الانتظار الخاصة بك في وقت مبكر، ويمكن أن تحمل على تخصيص كافة الذاكرة في خط الهجوم)، أو هذا <ل أ href = "http://www.javaspecialists.eu/archive/Issue027.html" يختلط = "noreferrer"> تنفيذ CircularArrayList . (نعم، انها من عام 2001، لذلك ستحتاج إلى generify ذلك، ولكن حصلت على معدلات الأداء مماثلة لما نقلت في المقالة للتو في JVM الأخير)

Answer 7

وانها مسألة الكفاءة. LinkedList سريع لإضافة وحذف العناصر، ولكن بطيئة للوصول إلى عنصر معين. ArrayList سريع للوصول إلى عنصر معين ولكن يمكن أن تكون بطيئة إضافة إلى طرفي، وبطيئة خاصة إلى حذف في الوسط.

صفيف مقابل ArrayList مقابل قائمة متصلة مقابل ناقل يذهب أكثر في العمق، كما يفعل قائمة مرتبط .

Answer 8

وصحيحة أو غير صحيحة: الرجاء تنفيذ الاختبار محليا وتقرر لنفسك

وتعديل / إزالة أسرع في LinkedList من ArrayList.

وArrayList، مدعومة Array، الذي يجب أن يكون ضعف حجم، هو أسوأ في تطبيق الحجم الكبير.

ويعطى

وفيما يلي نتيجة اختبار وحدة لكل operation.Timing في النانوسيكند.

---

Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

---

وهنا رمز:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

Answer 9

ArrayList هو في الأساس مجموعة. LinkedList يتم تطبيق مزدوج قائمة مرتبطة.

على get هو واضح جدا.س(1) ArrayList, لأن ArrayList يسمح الوصول العشوائي باستخدام المؤشر.O(n) LinkedList, لأنه يحتاج إلى العثور على مؤشر الأولى.ملاحظة:هناك إصدارات مختلفة من add و remove.

LinkedList أسرع في إضافة وإزالة لكن أبطأ في الحصول على.باختصار ، LinkedList ينبغي تفضيل إذا:

1. هناك عدد كبير من وصول عشوائي من عنصر
2. هناك عدد كبير من إضافة/إزالة العمليات

=== ArrayList ===

• إضافة(هـ e)
  • إضافة في نهاية ArrayList
  • تتطلب ذاكرة حجم التكلفة.
  • O(n) أسوأ ، O(1) المطفأة
• add(int مؤشر ه العنصر)
  • إضافة إلى مؤشر محدد الموقف
  • تتطلب تحويل & الممكن تغيير حجم الذاكرة التكلفة
  • O(n)
• إزالة(int index)
  • إزالة العنصر المحدد
  • تتطلب تحويل & الممكن تغيير حجم الذاكرة التكلفة
  • O(n)
• إزالة(كائن o)
  • إزالة أول حدوث المحدد عنصر من هذه القائمة
  • تحتاج إلى البحث عن العنصر الأول ثم تحول & الممكن تغيير حجم الذاكرة التكلفة
  • O(n)

=== LinkedList ===

• إضافة(هـ e)

  • إضافة إلى نهاية القائمة
  • س(1)

• add(int مؤشر ه العنصر)

  • إدراج في الموقع المحدد
  • تحتاج إلى العثور على موقف الأولى
  • O(n)
• إزالة()
  • إزالة العنصر الأول من القائمة
  • س(1)
• إزالة(int index)
  • إزالة عنصر مع الفهرس المحدد
  • تحتاج إلى العثور على العنصر الأول
  • O(n)
• إزالة(كائن o)
  • إزالة التواجد الأول من العنصر المحدد
  • تحتاج إلى العثور على العنصر الأول
  • O(n)

هنا هو شخصية من programcreek.com (add و remove هي من النوع الأول ، أي إضافة عنصر في نهاية القائمة وإزالة عنصر في الموضع المحدد في القائمة.):

Answer 10

وجوشوا بلوك، مؤلف من قائمة متصلة:

<اقتباس فقرة>   

هل هناك فعلا استخدام قائمة متصلة؟ لقد كتبت ذلك، وأنا أبدا استخدامها.

الرابط: https://twitter.com/joshbloch/status/583813919019573248

وأنا آسف عن الجواب لكونه ليس بالمعلومات والإجابات الأخرى، ولكن اعتقد انها ستكون الأكثر إثارة للاهتمام وتحتاج إلى شرح.

Answer 11

وArrayList يمكن الوصول إليها بشكل عشوائي، في حين LinkedList رخيصة حقا لتوسيع وإزالة عناصر من. بالنسبة لمعظم الحالات، ArrayList على ما يرام.

وإلا إذا كنت قد أنشأت قوائم كبيرة وقياس عنق الزجاجة، عليك ربما لا تحتاج للقلق حول الفرق.

Answer 12

إذا تمت add(0) التعليمات البرمجية وremove(0)، استخدم LinkedList وانها أجمل طرق addFirst() وremoveFirst(). وإلا، استخدم ArrayList.

وبطبيعة الحال، الجوافة الصورة <لأ href = "HTTPS: //google.github. الإعلام والتوعية / الجوافة / الإصدارات / 21.0 / المعهد / مستندات / كوم / جوجل / مشترك / جمع / ImmutableList.html "يختلط =" noreferrer "> ImmutableList هو أفضل صديق.

Answer 13

وأنا أعلم أن هذه هي وظيفة العمر، ولكن أنا بصراحة لا أستطيع أن أصدق ذكر أحد أن LinkedList تنفذ Deque. مجرد إلقاء نظرة على الطرق في Deque (وQueue)؛ إذا كنت ترغب في مقارنة عادلة، حاول تشغيل LinkedList ضد ArrayDeque والقيام مقارنة ميزة للميزة.

Answer 14

هنا هو Big-O التدوين في كل ArrayList و LinkedList و أيضا CopyOnWrite-ArrayList:

ArrayList

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

LinkedList

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

وبناء على هذه عليك أن تقرر ماذا تختار.:)

Answer 15

TL;DR بسبب الكمبيوتر الحديثة العمارة ، ArrayList سوف يكون إلى حد كبير أكثر كفاءة ما يقرب من أي من الممكن استخدام القضية - وبالتالي LinkedList ينبغي تجنب ما عدا بعض فريدة من نوعها للغاية و الحالات القصوى.

---

من الناحية النظرية ، LinkedList وقد O(1) add(E element)

أيضا إضافة عنصر في منتصف القائمة يجب أن تكون فعالة جدا.

الممارسة هي مختلفة جدا ، LinkedList هو ذاكرة التخزين المؤقت معادية بنية البيانات.من أداء بوف - هناك القليل جدا من الحالات التي LinkedList يمكن أن يكون أفضل أداء من ذاكرة التخزين المؤقت-ودية ArrayList.

وهنا نتائج اختبار قياس الأداء إدراج عناصر في مواقع عشوائية.كما يمكنك أن ترى مجموعة قائمة إذا أكثر كفاءة بكثير, على الرغم من الناحية النظرية كل تضاف في منتصف القائمة سوف تتطلب "نقل" ، n في وقت لاحق من عناصر المصفوفة (أقل القيم هي الأفضل):

العمل في وقت لاحق على أجهزة الجيل (أكبر وأكثر كفاءة مخابئ) - نتائج أكثر قاطعة:

LinkedList يأخذ الكثير من الوقت لإنجاز نفس المهمة. المصدر التعليمات البرمجية المصدر

هناك سببين رئيسيين لذلك:

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

2. الثانوية LinkedList مطلوب عقد إلى الوراء/إلى الأمام المؤشرات ، مما يعني 3 مرات استهلاك الذاكرة في القيمة المخزنة مقارنة ArrayList.

DynamicIntArray, للمعلومية هو العرف ArrayList تنفيذ عقد Int (نوع بدائي) وليس الكائنات - وبالتالي كل البيانات هو حقا المخزنة adjacently - وبالتالي أكثر كفاءة.

أحد العناصر الرئيسية أن نتذكر أن تكلفة جلب كتلة الذاكرة هو أكثر أهمية من التكلفة الوصول إلى ذاكرة وحيدة الخلية.لهذا القارئ 1MB من ذاكرة متسلسلة تصل إلى x400 مرات أسرع من قراءة هذه الكمية من البيانات من كتل مختلفة من الذاكرة:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

المصدر: الكمون أرقام كل مبرمج يجب أن تعرف

فقط لجعل نقطة أكثر وضوحا ، يرجى التحقق من المعيار إضافة عناصر إلى بداية القائمة.هذا هو الاستخدام-حالة-من الناحية النظريه ، LinkedList ينبغي أن تألق حقا ، ArrayList ينبغي أن يقدم الفقراء أو حتى أسوأ حالة النتائج:

ملاحظة:هذا هو المعيار C++ Std ليب ، ولكن تجربتي السابقة أظهرت C++ و Java النتائج متشابهة جدا. التعليمات البرمجية المصدر

نسخ متتابعة الأكبر من الذاكرة هو عملية الأمثل من وحدات المعالجة المركزية الحديثة المتغيرة ونظرية جعل الواقع ، مرة أخرى ، ArrayList/Vector أكثر كفاءة بكثير

---

الاعتمادات:جميع المعايير المنشورة هنا يتم إنشاؤها من قبل كجيل Hedström.المزيد من البيانات ويمكن الاطلاع على بلوق

Answer 16

دعونا نقارن LinkedList و ArrayList ث.r.t.أدناه المعلمات:

1.تنفيذ

ArrayList هو يمكن تغيير حجم مجموعة تنفيذ قائمة واجهة ، في حين

LinkedList هو مضاعف-قائمة مرتبطة تنفيذ قائمة واجهة.

---

2.الأداء

• الحصول على(int index) أو عملية البحث

  ArrayList الحصول على(int index) عملية تجري في وقت ثابت أنا.e O(1) في حين

  LinkedList الحصول على(int index) تشغيل الوقت O(n) .

  السبب وراء ArrayList يجري أسرع من LinkedList هو أن ArrayList يستخدم فهرس القائمة على نظام عناصرها كما يستخدم داخليا مجموعة البيانات هيكل ، من ناحية أخرى ،

  LinkedList لا تقدم على أساس مؤشر وصول عناصرها كما تتكرر إما من البداية أو النهاية (أيهما أقرب) لاسترداد عقدة في العنصر المحدد مؤشر.

• إدراج() أو إضافة(كائن) عملية

  الإدراج في LinkedList عموما سريع مقارنة ArrayList.في LinkedList إضافة أو إدراج O(1) عملية .

  بينما في ArrayList, إذا كان الصفيف هو أنا.هـ أسوأ الأحوال ، هناك تكلفة إضافية من تغيير حجم مجموعة نسخ العناصر إلى مجموعة جديدة ، مما يجعل من وقت إضافة عملية في ArrayList O(n), وإلا فمن O(1).

• إزالة(الباحث) عملية

  إزالة عملية في LinkedList هو عموما نفس ArrayList أيO(n).

  في LinkedList, هناك نوعان من طاقتها إزالة الأساليب.واحد هو إزالة() دون أي معلمة الذي يزيل رأس قائمة تشغيل في وقت ثابت س(1).أخرى مثقلة إزالة الأسلوب في LinkedList هو إزالة(الباحث) أو إزالة(الكائن) الذي يزيل كائن أو الباحث مرت كمعلمة.هذه الطريقة تقطع LinkedList حتى وجدت موضوع فك ارتباط من القائمة الأصلية.وبالتالي هذا الأسلوب التشغيل O(n).

  بينما في ArrayList إزالة(الباحث) الأسلوب ينطوي على نسخ العناصر من مجموعة جديدة تحديث مجموعة ، وبالتالي وقت التشغيل O(n).

---

3.عكس مكرر

LinkedList يمكن أن يتحرك في عكس اتجاه باستخدام descendingIterator() في حين

لا يوجد descendingIterator() في ArrayList لذا علينا ان نكتب كود تكرار عبر ArrayList في الاتجاه المعاكس.

---

4.القدرة الأولية

إذا كان المنشئ هو فوق طاقتها ، ثم ArrayList يخلق قائمة فارغة من القدرات الأولية 10 ، في حين

LinkedList فقط بنيات قائمة فارغة دون أي القدرة الأولية.

---

5.الذاكرة العلوية

الذاكرة العلوية في LinkedList هو أكثر بالمقارنة مع ArrayList كما عقدة في LinkedList يحتاج إلى الحفاظ على العناوين التالية والسابقة عقدة.في حين

في ArrayList كل مؤشر فقط يحمل الكائن الفعلي(البيانات).

---

المصدر

Answer 17

وبالإضافة إلى حجج وجيهة أخرى أعلاه، يجب أن تلاحظ ArrayList الأدوات RandomAccess واجهة، بينما LinkedList تنفذ Queue.

وهكذا، على نحو ما تعالج مشاكل مختلفة قليلا، مع فارق والكفاءة والسلوك (انظر قائمة من الأساليب).

Answer 18

ودروس جافا - قائمة تطبيقات

Answer 19

ويمكن الاطلاع على قائمة مجموعة هي في الأساس مجموعة مع طرق لإضافة عناصر الخ (ويجب عليك استخدام قائمة عامة بدلا من ذلك). وهي عبارة عن مجموعة من الأدوات التي يمكن الوصول إليها من خلال مفهرس (على سبيل المثال [0]). أنه ينطوي على الانتقال من عنصر واحد إلى آخر.

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

Answer 20

وهذا يعتمد على ما العمليات التي سوف تفعل أكثر على القائمة.

وArrayList أسرع للوصول إلى القيمة المفهرسة. ومن أسوأ بكثير عند إدخال أو حذف الكائنات.

لمعرفة المزيد، قراءة أي مقال يتحدث عن الفرق بين المصفوفات والقوائم المرتبطة.

Answer 21

وعادة ما تستخدم واحد على الآخر على أساس التعقيدات وقت العمليات التي كنت بها على أن قائمة معينة.

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

Answer 22

وهناك سمة مهمة من قائمة مرتبطة (التي لم أكن قرأت في إجابة أخرى) هي سلسلة من قائمتين. مع مجموعة وهذا هو O (ن) (+ النفقات العامة من بعض عمليات إعادة التخصيص) مع قائمة مرتبطة هذه ليست سوى O (1) أو O (2)؛ -)

على هام : لللجافا LinkedList له هذا غير صحيح! انظر هل هناك طريقة CONCAT سريع لقائمة مرتبطة في جافا؟

Answer 23

ولقد قرأت الردود، ولكن هناك سيناريو واحد حيث كنت دائما استخدام قائمة متصلة عبر ArrayList التي أريد أن أشارك لسماع آراء:

وفي كل مرة كان لي أسلوب بإرجاع قائمة من البيانات التي تم الحصول عليها من DB أنا دائما استخدام قائمة متصلة.

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

وبقدر من ArrayList، أنا أوافق على الأقل يجب عليك دائما استخدام منشئ مع القدرة الأولية، لتقليل الازدواجية في صفائف قدر الإمكان.

Answer 24

وArrayList وقائمة متصلة لديها الايجابيات والسلبيات.

وArrayList يستخدم عنوان الذاكرة متجاورة مقارنة قائمة متصلة التي تستخدم المؤشرات نحو العقدة المقبل. حتى عندما كنت تريد البحث عن عنصر في ArrayList أسرع من القيام تكرار ن مع قائمة متصلة.

وعلى صعيد آخر، الإدراج والحذف في قائمة متصلة هي أسهل بكثير لأنه لديك فقط لتغيير مؤشرات حين أن ArrayList يعني استخدام عملية التحول لأي الإدراج أو الحذف.

إذا كان لديك عمليات استرجاع متكررة في التطبيق الخاص بك استخدام ArrayList. إذا كان لديك الإدراج المتكرر وحذف استخدام قائمة متصلة.

Answer 25

ArrayList و LinkedList كل من ينفذ List interface و الأساليب و النتائج متطابقة تقريبا.ومع ذلك هناك بعض الاختلافات بينهما مما جعل أحد أفضل على الآخر اعتمادا على الشرط.

ArrayList مقابل LinkedList

1) Search: ArrayList عملية البحث سريعة جدا مقارنة LinkedList عملية البحث. get(int index) في ArrayList يعطي أداء O(1) في حين LinkedList الأداء O(n).

Reason: ArrayList يحافظ المؤشر على أساس نظام عناصرها كما أنه يستخدم مجموعة البيانات هيكل ضمنا مما يجعلها أسرع للبحث عن عنصر في القائمة.على الجانب الآخر LinkedList تنفذ قائمة مرتبطة مضاعف مما يتطلب اجتياز من خلال جميع العناصر للبحث عن عنصر.

2) Deletion: LinkedList إزالة عملية يعطي O(1) الأداء أثناء ArrayList يعطي متغير الأداء: O(n) في أسوأ الأحوال (في حين إزالة العنصر الأول) ، O(1) في أفضل الأحوال (في حين إزالة آخر عنصر).

الخلاصة:LinkedList عنصر الحذف هو أسرع مقارنة ArrayList.

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

3) Inserts Performance: LinkedList طريقة إضافة يعطي O(1) الأداء أثناء ArrayList يعطي O(n) في أسوأ الأحوال.السبب هو نفسه كما هو موضح من أجل إزالة.

4) Memory Overhead: ArrayList يحافظ على فهارس عنصر بيانات في حين LinkedList يحافظ على عنصر بيانات اثنين من المؤشرات على الجار العقد

وبالتالي استهلاك الذاكرة عالية في LinkedList نسبيا.

هناك بعض أوجه التشابه بين هذه الفئات التي هي على النحو التالي:

• كل ArrayList و LinkedList يتم تنفيذ قائمة واجهة.
• كلاهما الحفاظ على عناصر الإدراج الأمر الذي يعني أثناء عرض ArrayList و LinkedList عناصر مجموعة النتائج سوف يكون لها نفس ترتيب العناصر التي يجب إدراجها في القائمة.
• كل من هذه الفئات غير متزامنة و يمكن أن تكون متزامنة صراحة باستخدام مجموعات.synchronizedList الأسلوب.
• على iterator و listIterator عاد قبل هذه الفئات fail-fast (إن قائمة هيكليا تعديلها في أي وقت بعد التكرار يتم إنشاؤه في أي حال من الأحوال إلا من خلال iterator’s الخاصة بإزالة أو إضافة أساليب التكرار سوف throw a ConcurrentModificationException).

عند استخدام LinkedList ومتى تستخدم ArrayList?

• كما هو موضح أعلاه إدراج وإزالة العمليات تعطي أداء جيد (O(1)) في LinkedList مقارنة ArrayList(O(n)).

  وبالتالي إذا كان هناك شرط من كثرة بالإضافة و الحذف في التطبيق ثم LinkedList هو أفضل خيار.

• البحث (get method) العمليات بسرعة في Arraylist (O(1)) ولكن ليس في LinkedList (O(n))

  حتى إذا كان هناك أقل من إضافة و إزالة عمليات البحث أكثر العمليات الشرط ، ArrayList سيكون أفضل رهان.

Answer 26

عملية الحصول على(أنا) في ArrayList أسرع من LinkedList لأن:
ArrayList: يمكن تغيير حجم-مجموعة تنفيذ قائمة واجهة
LinkedList: مرتبطة على نحو مضاعف قائمة تنفيذ قائمة Deque واجهات

عمليات أنه مؤشر إلى قائمة سوف اجتياز قائمة من بداية أو نهاية ، أيهما أقرب إلى الفهرس المحدد.

Answer 27

1) البيانات الأساسية هيكل

الفرق الأول بين ArrayList و LinkedList يأتي مع حقيقة أن ArrayList تدعمها مجموعة في حين LinkedList مدعومة LinkedList.وهذا سوف يؤدي إلى مزيد من الاختلافات في الأداء.

2) LinkedList تنفذ Deque

وثمة فرق آخر بين ArrayList و LinkedList هو أنه بغض النظر عن القائمة واجهة LinkedList كما تنفذ Deque واجهة ، الذي يقدم لأول مرة في أول عمليات إضافة() و استطلاع() والعديد من Deque وظائف.3) إضافة عناصر في ArrayList إضافة عنصر في ArrayList O(1) عملية إذا كان لا يؤدي إعادة حجم مجموعة ، وفي هذه الحالة يصبح O(log(n)), من ناحية أخرى, إضافة عنصر في LinkedList O(1) عملية ، كما أنها لا تتطلب أي الملاحة.

4) إزالة عنصر من موقف

من أجل إزالة عنصر من مؤشر معين على سبيل المثالمن خلال الاتصال إزالة(المؤشر) ، ArrayList ينفذ عملية نسخ مما يجعلها قريبة من O(n) بينما LinkedList يحتاج إلى اجتياز تلك المرحلة مما يجعل O(n/2) ، كما يمكن أن تعبر عن أي اتجاه على أساس القرب.

5) بالتكرار على ArrayList أو LinkedList

التكرار هو O(n) عملية لكل LinkedList و ArrayList حيث n هو عدد من عنصر.

6) استرداد عنصر من موقف

الحصول على(مؤشر) عملية O(1) في ArrayList حين O(n/2) في LinkedList ، كما أنه يحتاج إلى اجتياز حتى أن دخول.رغم ذلك ، في تدوين O O(n/2) هو مجرد O(n) لاننا تجاهل ثوابت هناك.

7) الذاكرة

LinkedList يستخدم كائن المجمع, دخول, وهو ثابت متداخلة الدرجة لتخزين البيانات و عقدتين التالي و السابق في حين ArrayList فقط بتخزين البيانات في مصفوفة.

حتى الذاكرة الشرط يبدو أقل في حالة ArrayList من LinkedList باستثناء الحالة التي يكون فيها مجموعة ينفذ إعادة حجم العملية عند نسخ المحتوى من مجموعة واحدة إلى أخرى.

إن مجموعة كبيرة بما يكفي قد يستغرق الكثير من الذاكرة عند هذه النقطة الزناد جمع القمامة ، والتي يمكن أن تبطئ زمن الاستجابة.

من كل ما سبق الخلافات بين ArrayList مقابل LinkedList ، يبدو ArrayList هو خيار أفضل من LinkedList في جميع الحالات تقريبا ، ما عدا عندما كنت تفعل متكررة إضافة() عملية من إزالة () أو().

انها أسهل لتعديل قائمة مرتبطة من ArrayList ، خاصة إذا كنت تقوم بإضافة أو إزالة عناصر من البداية أو النهاية لأنها قائمة مرتبطة داخليا يستمر المراجع من تلك المواقف يمكن الوصول إليها في س(1) مرة.

وبعبارة أخرى, لا تحتاج إلى اجتياز القائمة المرتبطة للوصول إلى الموضع حيث تريد إضافة عناصر, في هذه الحالة, بالإضافة إلى ذلك يصبح O(n) العملية.على سبيل المثال إدراج أو حذف عنصر في منتصف قائمة مرتبطة.

في رأيي, استخدام ArrayList على LinkedList لأكثر من غرض عملي في جاوة.

Answer 28

وكلاهما إزالة () وإدراج () لديها الكفاءة مدة عرضه O (ن) على حد سواء ArrayLists وLinkedLists. ومع ذلك، فإن السبب وراء وقت المعالجة الخطية يأتي من سببين مختلفين جدا:

في أحد ArrayList، لتحصل على عنصر في O (1)، ولكن في الواقع إدخال أو إخراج شيء يجعل من O (ن) لأن جميع العناصر التالية تحتاج إلى تغيير.

وفي قائمة متصلة، فإنه يأخذ O (ن) للحصول على الواقع إلى العنصر المطلوب، لأن علينا أن نبدأ في البداية حتى نصل إلى مؤشر المرجوة. إزالة فعلا أو ادخال هو ثابت، لأن لدينا فقط لتغيير 1 مرجعية لإزالة () و 2 المراجع لإدراج ().

وأي من الاثنين هو أسرع لإدراج وإزالة يعتمد على المكان وقوعها. إذا كان لنا أن نقترب من بداية لقائمة متصلة سيكون أسرع، لأن لدينا للذهاب من خلال عناصر قليلة نسبيا. إذا كان لنا أن نقترب من نهاية لArrayList سوف يكون أسرع، لأن نصل إلى هناك في وقت ثابت وليس لها سوى تغيير العناصر القليلة المتبقية التي تليه. عندما تنتهي من ذلك على وجه التحديد في منتصف لقائمة متصلة سيكون أسرع لأن يمر عناصر n غير أسرع من الانتقال القيم ن.

والمكافأة: ولئن كان هناك أي وسيلة لجعل هذه طريقتين O (1) لArrayList، هناك في الواقع وسيلة للقيام بذلك في LinkedLists. دعونا نقول أننا نريد أن تذهب من خلال قائمة كاملة عملية اخراج وادخال عناصر في طريقنا. عادة، هل نبدأ من البداية لكل عنصر باستخدام قائمة متصلة، يمكننا أيضا "انقاذ" العنصر الحالي نحن نعمل على مع مكرر. مع مساعدة من مكرر، نحصل على O (1) كفاءة لإزالة () وإدراج () عند العمل في قائمة متصلة. مما يجعل من مصلحة أداء الوحيدة أنا على علم من حيث قائمة متصلة هي دائما أفضل من أحد ArrayList.

Answer 29

وArrayList يمتد AbstractList وتنفذ واجهة قائمة. ArrayList هو صفيف حيوية.
ويمكن القول أن تم إنشاؤه أساسا للتغلب على عيوب صفائف

الطبقة قائمة متصلة تمتد AbstractSequentialList وتنفذ واجهة قائمة، صف مزدوج الذيل، وقائمة الانتظار.
الأداء
arraylist.get() هو O (1)، في حين هو linkedlist.get() O (ن)
arraylist.add() هو O (1) وlinkedlist.add() 0 (1)
arraylist.contains() هو O (ن) andlinkedlist.contains() هو O (ن)
arraylist.next() هو O (1) وlinkedlist.next() هو O (1)
arraylist.remove() هو O (ن) في حين هو linkedlist.remove() O (1)
في arraylist
iterator.remove() هو O (ن)
بينما في قائمة متصلة
iterator.remove()is O (1)

Answer 30

واحد من الاختبارات رأيت هنا تجري فقط في الاختبار مرة واحدة. ولكن ما لاحظته هو أن تحتاج إلى تشغيل هذه الاختبارات عدة مرات وفي النهاية أوقاتهم سوف تتقارب. في الأساس JVM تحتاج إلى الاحماء. لبلدي خاصة حالة استخدام كنت بحاجة إلى إضافة / إزالة العناصر إلى آخر أن ينمو إلى حوالي 500 قطعة. في بلدي التجارب LinkedList خرج بشكل أسرع، مع LinkedList مرتبطة القادمة في حوالي 50،000 NS وArrayList القادمة في حوالي 90،000 NS ... يعطي أو يأخذ. راجع التعليمات البرمجية أدناه.

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}