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

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

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

خاتمة:

[Hello World! My name is Earl, I love Java, I live in Moscow]

هذا ما سيبدو عليه هيكل قائمتنا: دعونا نرى كيف تتم إضافة عنصر جديد. ويتم ذلك باستخدام add().

earlBio.add(str2);

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

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

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

public class Main {

   public static void main(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 Moscow");

       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()size()add()remove()LinkedListArrayList

• 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='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

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

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

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());
}

خاتمة:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

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

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 left on the list?");
   System.out.println(cars);
}

خاتمة:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

• 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 to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

خاتمة:

Время работы для LinkedList (в мorсекундах) = 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 to run for 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 على طول سلسلة الروابط. بالنسبة له، هذا ليس عنوانًا في الذاكرة، بل رابط لا يزال يتعين الوصول إليه:

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("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

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

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

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