قائمة جافا المرتبطة

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

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

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

earlBio.add(str2);

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

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

كما ترون، تتيح لك طريقة add() المحملة بشكل زائد تحديد فهرس محدد لعنصر جديد. في هذه الحالة، نريد إضافة String str2 بين str1 و str3 . وهذا ما سيحدث داخليًا: بعد تغيير الروابط الداخلية، تمت إضافة str2 بنجاح إلى القائمة: الآن تم توصيل جميع العناصر الثلاثة. يمكنك الانتقال عبر الرابط التالي من العنصر الأول في السلسلة إلى العنصر الأخير والعودة مرة أخرى. لذا، نحن مرتاحون إلى حد ما للإدراج، ولكن ماذا عن إزالة العناصر؟ المبدأ هو نفسه تماما. نقوم فقط بتحديث الروابط الموجودة في العنصرين "على اليسار واليمين" للعنصر الذي تتم إزالته:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

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

نظرة عامة على الأساليب

لدى LinkedList الكثير من الأساليب المشتركة مع ArrayList . على سبيل المثال، تحتوي كلا الفئتين على توابع مثل add() و remove() و indexOf() و clear() و contains() (يشير إلى ما إذا كان العنصر موجودًا في القائمة) و set() (يستبدل عنصرًا موجودًا) و مقاس() . على الرغم من أن العديد منها يعمل بشكل مختلف داخليًا (كما وجدنا مع add() و remove() )، فإن النتيجة النهائية هي نفسها. ومع ذلك، لدى LinkedList طرق منفصلة للتعامل مع بداية القائمة ونهايتها، وهو ما لا يتوفر لدى ArrayList :

• addFirst() , addLast() : هذه الطرق لإضافة عنصر إلى بداية/نهاية القائمة

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

الإخراج: [Car{model='Ferrari 360 Spider'}، Car{model='Bugatti Veyron'}، Car{model='Lamborghini Diablo'}] [Car{model='Ford Mondeo'}، Car{model=' فيراري 360 سبايدر'}، سيارة {model='Bugatti Veyron'}، سيارة{model='Lamborghini Diablo'}، Car{model='Fiat Ducato'}] وانتهى بنا الأمر مع "Ford" في أعلى القائمة، و"فيات" في النهاية.

• peekFirst() , peekLast() : تقوم الطرق بإرجاع العنصر الأول/الأخير في القائمة. يعودون فارغة إذا كانت القائمة فارغة.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

الإخراج: سيارة {موديل = 'فيراري 360 سبايدر'} سيارة {موديل = 'لامبورغيني ديابلو'}

• pollFirst() , pollLast() : تقوم هذه الطرق بإرجاع العنصر الأول/الأخير في القائمة وإزالته من القائمة. يعودون فارغة إذا كانت القائمة فارغة

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

الإخراج: Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'} ما الذي بقي في القائمة؟ [سيارة {موديل = 'بوجاتي فيرون'}]

• toArray() : تقوم هذه الطريقة بإرجاع مصفوفة تحتوي على عناصر القائمة

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

الإخراج: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] الآن نعرف كيف يعمل LinkedList وكيف يختلف تنظيمه عن ArrayList . ما هي فوائد استخدام LinkedList ؟ قبل كل شيء، نستفيد عندما نعمل في منتصف القائمة. تعد عمليات الإدراج والإزالة في منتصف LinkedList أبسط بكثير مما هي عليه في ArrayList . نحن ببساطة نقوم بتحديث روابط العناصر المجاورة، و"ينقطع" العنصر غير المرغوب فيه من سلسلة الروابط. ولكن في ArrayList ، يجب علينا ذلك

• تحقق مما إذا كانت هناك مساحة كافية (عند الإدخال)
• إذا لم يكن الأمر كذلك، فإننا نقوم بإنشاء مصفوفة جديدة ونسخ البيانات هناك (عند الإدراج)
• نقوم بإزالة/إدراج العنصر، ونقل جميع العناصر الأخرى إلى اليمين/اليسار (حسب نوع العملية). ويعتمد تعقيد هذه العملية بشكل كبير على حجم القائمة. إن نسخ/نقل 10 عناصر شيء، وفعل الشيء نفسه مع مليون عنصر شيء آخر.

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

نظريا

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

الإخراج: الوقت الذي تستغرقه LinkedList (بالمللي ثانية) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

الإخراج: الوقت الذي تستغرقه ArrayList (بالمللي ثانية) = 181 كان ذلك غير متوقع! لقد أجرينا عملية حيث يجب أن تكون LinkedList أكثر كفاءة: إدراج 100 عنصر في منتصف القائمة. وقائمتنا ضخمة: 5,000,000 عنصر. كان على ArrayList نقل مليوني عنصر مع كل عملية إدخال! كيف فاز؟ أولاً، الوقت اللازم لوصول ArrayList إلى العناصر ثابت (ثابت). عندما تكتب

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

إذن ArrayList [2_000_000] هو عنوان ذاكرة محدد (بعد كل شيء، تحتوي القائمة على مصفوفة داخلية). لكن قائمة LinkedList لا تحتوي على مصفوفة. سيتم البحث عن العنصر رقم 2_000_000 على طول سلسلة الروابط. بالنسبة إلى LinkedList، هذا ليس عنوان ذاكرة، ولكنه رابط لا يزال يتعين الوصول إليه: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next……… ونتيجة لذلك، أثناء كل إدراج (إزالة) في منتصف القائمة ، يعرف ArrayList بالفعل عنوان الذاكرة الدقيق الذي يجب الوصول إليه، لكن LinkedList لا يزال بحاجة إلى "الوصول إلى هناك". ثانيًا، هناك بنية ArrayList نفسها . تعمل وظيفة داخلية خاصة ( System.arrayCopy() ) على توسيع المصفوفة الداخلية ونسخ جميع العناصر ونقلها. إنه سريع جدًا، لأنه مُحسّن لهذا العمل المحدد. ولكن عندما لا تضطر إلى "الوصول" إلى فهرس معين، فإن LinkedList هو الفائز. لنفترض أننا أدخلنا في بداية القائمة. دعونا نحاول إدراج مليون عنصر هناك:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

الإخراج: النتيجة بالمللي ثانية: 43448 النتيجة بالمللي ثانية: 107 الآن حصلنا على نتيجة مختلفة تمامًا! استغرق ArrayList أكثر من 43 ثانية في إدخال مليون عنصر في مقدمة القائمة، بينما تمكن LinkedList من القيام بذلك في 0.1 ثانية! استفاد LinkedList هنا، لأنه لم يكن من الضروري تشغيله عبر سلسلة الروابط إلى منتصف القائمة في كل مرة. يقوم على الفور بالعثور على الفهرس المطلوب في بداية القائمة، وبالتالي فإن الخوارزمية المختلفة تعد ميزة بالفعل. :) في الواقع، مناقشة " ArrayList vs LinkedList " منتشرة على نطاق واسع، ولن نتعمق فيها عند المستوى الحالي. الشيء الرئيسي الذي عليك أن تتذكره هو:

• ليست كل المزايا النظرية لأي مجموعة معينة تعمل دائمًا في الواقع (لقد رأينا ذلك في المثال الذي يتضمن منتصف القائمة)
• لا تتبنى موقفًا متطرفًا عندما يتعلق الأمر باختيار مجموعة (" ArrayList دائمًا أسرع. استخدمه ولن تخطئ. لم يستخدم أحد LinkedList لفترة طويلة").

على الرغم من أن مؤلف موقع LinkedList ، جوشوا بلوخ، يقول أن هذا هو الحال. :) ومع ذلك، فإن هذا المنظور أبعد ما يكون عن الصحة بنسبة 100%، وقد أقنعنا أنفسنا بذلك. في مثالنا السابق، كانت LinkedList أسرع بـ 400 (!) مرة. شيء آخر هو أن هناك بالفعل حالات قليلة يكون فيها LinkedList هو الخيار الأفضل. لكنها موجودة بالفعل، وفي اللحظة المناسبة يمكن لـ LinkedList أن يكافئك بسخاء. لا تنس ما قلناه في بداية الدرس: تختلف هياكل البيانات الأكثر كفاءة باختلاف المهام. من المستحيل أن تكون متأكدًا بنسبة 100% من بنية البيانات الأفضل حتى تعرف جميع شروط مهمتك. ستعرف المزيد عن هذه المجموعات لاحقًا، مما سيجعل الاختيار أسهل. لكن الخيار الأبسط والأكثر فعالية هو نفسه دائمًا: جرب كلا الخيارين على البيانات الفعلية المستخدمة في برنامجك. وبعد ذلك سوف تكون قادرًا على أن ترى بنفسك كيفية أداء كلا النوعين من القوائم، وبالتأكيد لن تخطئ. :) لتعزيز ما تعلمته، نقترح عليك مشاهدة درس فيديو من دورة Java الخاصة بنا