جاوا ۾ LinkedList

سلام! سڀ تازو ليڪچر ارري لسٽ لسٽ جي مطالعي لاءِ وقف ڪيا ويا آهن . هي ڊيٽا جي جوڙجڪ تمام آسان آهي ۽ توهان کي ڪيترن ئي مسئلن کي حل ڪرڻ جي اجازت ڏئي ٿي. بهرحال، جاوا وٽ ڪيترائي ٻيا ڊيٽا ڍانچا آهن. ڇو؟ سڀ کان پهريان، ڇاڪاڻ ته موجوده ڪمن جي حد تمام وسيع آهي، ۽ مختلف ڪمن لاء مختلف ڊيٽا جي جوڙجڪ تمام مؤثر آهن . اڄ اسان هڪ نئين جوڙجڪ سان واقف ٿينداسين - هڪ ٻيڻو ڳنڍيل فهرست 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);

ڪوڊ جي هن لائن جي وقت، اسان جي لسٽ هڪ عنصر تي مشتمل آهي - string str1. اچو ته ڏسون ته تصوير ۾ اڳتي ڇا ٿئي ٿو: نتيجي طور str2، ۽ str1انھن ۾ محفوظ ڪيل لنڪ ذريعي ڳنڍجي وڃو next۽ previous: ھاڻي توھان کي سمجھڻ گھرجي اصلي خيال کي ٻيڻو ڳنڍيل لسٽ. عناصر LinkedListھڪڙي ھڪڙي فهرست آھن خاص طور تي لنڪ جي ھن زنجير جي مھرباني. اندر ڪا به صف نه آهي LinkedList، جهڙوڪ in 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ڪاميابيء سان لسٽ ۾ شامل ڪيو ويو آھي: ھاڻي سڀ 3 عناصر ڳنڍيل آھن. زنجير سان گڏ پهرين عنصر کان 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()) انهن مان ڪيترائي اندروني طور تي مختلف ڪم ڪن ٿا، پر آخرڪار اهي ساڳيو ڪم ڪن ٿا. بهرحال، ان 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='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

نتيجي طور، فورڊ لسٽ جي چوٽي تي ختم ٿي ويو، ۽ آخر ۾ Fiat.

• 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));

پوءِ [2_000_000] جي صورت ۾ ArrayListهي ميموري ۾ هڪ مخصوص ايڊريس آهي، ڇاڪاڻ ته ان جي اندر هڪ صف آهي. جڏهن ته 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٪ اعتماد سان چوڻ ناممڪن آهي ته ڪهڙي ڊيٽا جي جوڙجڪ بهتر هوندي جيستائين مسئلي جي سڀني حالتن کي ڄاڻايو وڃي. بعد ۾ توهان انهن مجموعن بابت وڌيڪ ڄاڻو ٿا، ۽ اهو چونڊڻ آسان ٿي ويندو. پر سڀ کان آسان ۽ سڀ کان وڌيڪ اثرائتو اختيار هميشه ساڳيو آهي: توهان جي پروگرام مان حقيقي ڊيٽا تي ٻنهي کي جانچيو. پوء توهان پنهنجي اکين سان ڏسي سگهو ٿا ٻنهي لسٽن جا نتيجا ۽ توهان ضرور غلط نه ٿيندا :)