جاوا میں لنکڈ لسٹ

ہیلو! تمام حالیہ لیکچرز ArrayList فہرست کے مطالعہ کے لیے وقف کیے گئے ہیں ۔ یہ ڈیٹا ڈھانچہ بہت آسان ہے اور آپ کو بہت سے مسائل حل کرنے کی اجازت دیتا ہے۔ تاہم، جاوا میں بہت سے دوسرے ڈیٹا ڈھانچے ہیں۔ کیوں؟ سب سے پہلے، کیونکہ موجودہ کاموں کا دائرہ بہت وسیع ہے، اور مختلف کاموں کے لیے مختلف ڈیٹا ڈھانچے سب سے زیادہ موثر ہیں ۔ آج ہم ایک نئے ڈھانچے سے واقف ہوں گے - ایک دوگنا لنکڈ لسٹ LinkedList ۔ آئیے معلوم کریں کہ یہ کیسے کام کرتا ہے، اسے دوگنا جڑا کیوں کہا جاتا ہے، اور یہ ArrayList سے کیسے مختلف ہے ۔ لنکڈ لسٹ میں ، عناصر دراصل ایک سلسلہ میں جڑے ہوتے ہیں۔ ہر عنصر، اس کے ذخیرہ کردہ ڈیٹا کے علاوہ، پچھلے اور اگلے عنصر سے ایک لنک رکھتا ہے ۔ یہ لنکس آپ کو ایک عنصر سے دوسرے عنصر میں جانے کی اجازت دیتے ہیں۔ یہ اس طرح بنایا گیا ہے:

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، جیسے 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کے درمیان ایک لائن شامل کرنا چاہتے ہیں ۔ یہ وہی ہے جو اندر ہوگا: اور اندرونی لنکس کو تبدیل کرنے کے نتیجے میں، عنصر کو کامیابی سے فہرست میں شامل کیا گیا ہے: اب تمام 3 عناصر منسلک ہیں. زنجیر کے ساتھ پہلے عنصر سے آپ آخری اور پیچھے جا سکتے ہیں۔ ہم نے کم و بیش اندراج کا پتہ لگایا ہے، لیکن عناصر کو حذف کرنے کا کیا ہوگا؟ آپریٹنگ اصول ایک ہی ہے۔ ہم صرف ہٹائے جانے والے دو عناصر کے "اطراف" کے لنکس کی نئی وضاحت کرتے ہیں: str1str3str2next

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؟ سب سے پہلے، فہرست کے وسط کے ساتھ کام کرنے میں ۔ بیچ میں ڈالنا اور حذف کرنا LinkedListin کی نسبت بہت آسان ہے 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% اعتماد کے ساتھ یہ کہنا ناممکن ہے کہ جب تک مسئلہ کی تمام شرائط معلوم نہ ہو جائیں ڈیٹا کا ڈھانچہ کون سا بہتر ہوگا۔ بعد میں آپ ان مجموعوں کے بارے میں مزید جان لیں گے، اور انتخاب کرنا آسان ہو جائے گا۔ لیکن سب سے آسان اور موثر آپشن ہمیشہ ایک جیسا ہوتا ہے: اپنے پروگرام کے اصلی ڈیٹا پر دونوں کی جانچ کریں۔ پھر آپ اپنی آنکھوں سے دونوں فہرستوں کے نتائج دیکھ سکتے ہیں اور آپ یقینی طور پر غلط نہیں ہوں گے :)