جاوا لنکڈ لسٹ

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

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

   }
}

آؤٹ پٹ: [ہیلو ورلڈ! میرا نام ارل ہے، مجھے جاوا پسند ہے، میں کینیڈا میں رہتا ہوں] ہماری فہرست کیسی دکھتی ہے: آئیے دیکھتے ہیں کہ نیا عنصر کیسے شامل کیا جائے۔ یہ add() طریقہ استعمال کرتے ہوئے کیا جاتا ہے۔

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

   }
}

جیسا کہ آپ دیکھ سکتے ہیں، اوورلوڈ ایڈ() طریقہ آپ کو کسی نئی آئٹم کے لیے ایک مخصوص انڈیکس بتانے دیتا ہے۔ اس صورت میں، ہم String str2 کو str1 اور str3 کے درمیان شامل کرنا چاہتے ہیں ۔ اندرونی طور پر ایسا ہی ہوگا: اندرونی روابط کو تبدیل کرنے کے بعد، str2 کو کامیابی کے ساتھ فہرست میں شامل کیا گیا ہے: اب تمام 3 عناصر جڑ گئے ہیں۔ آپ اگلے لنک کے ذریعے سلسلہ کے پہلے عنصر سے آخری اور دوبارہ واپس جا سکتے ہیں ۔ تو، ہم اندراج کے ساتھ کافی آرام دہ ہیں، لیکن عناصر کو ہٹانے کے بارے میں کیا خیال ہے؟ اصول بالکل وہی ہے۔ ہم صرف ہٹائے جانے والے عنصر کے "بائیں اور دائیں" دو عناصر میں لنکس کو اپ ڈیٹ کرتے ہیں:

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=' Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] ہم فہرست میں سب سے اوپر "Ford" کے ساتھ آتے ہیں ، اور آخر میں "Fiat"۔

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

آؤٹ پٹ: کار{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'}

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

آؤٹ پٹ: کار{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));
   }
}

آؤٹ پٹ: لنکڈ لسٹ کے ذریعہ لیا گیا وقت (ملی سیکنڈ میں) = 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] ایک مخصوص میموری ایڈریس ہے (آخر کار، فہرست میں اندرونی صف ہوتی ہے)۔ لیکن، لنکڈ لسٹ میں کوئی صف نہیں ہوتی ہے۔ یہ لنکس کی زنجیر کے ساتھ عنصر نمبر 2_000_000 کو تلاش کرے گا۔ LinkedList کے لیے، یہ میموری ایڈریس نہیں ہے، بلکہ ایک لنک ہے جس تک پہنچنے کی ضرورت ہے: fistElement.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 کو یہاں فائدہ ہوا، کیونکہ اسے ہر بار فہرست کے وسط کے لنکس کے سلسلے سے گزرنا نہیں پڑتا تھا۔ یہ فہرست کے آغاز میں فوری طور پر مطلوبہ اشاریہ تلاش کرتا ہے، لہذا مختلف الگورتھم پہلے سے ہی ایک فائدہ ہے۔ :) درحقیقت، " ArayList بمقابلہ LinkedList " بحث بہت وسیع ہے، اور ہم موجودہ سطح پر اس میں گہرائی میں نہیں جائیں گے۔ اہم چیز جو آپ کو یاد رکھنے کی ضرورت ہے وہ یہ ہے:

• تمام نظریاتی فوائد کوئی خاص مجموعہ ہمیشہ حقیقت میں کام نہیں کرتے (ہم نے اسے فہرست کے وسط میں شامل مثال کے ساتھ دیکھا)
• جب کوئی مجموعہ منتخب کرنے کی بات آتی ہے تو انتہائی پوزیشن اختیار نہ کریں (" ArayList ہمیشہ تیز ہوتی ہے۔ اسے استعمال کریں اور آپ غلط نہیں ہو سکتے۔ کوئی بھی طویل عرصے سے LinkedList استعمال نہیں کر رہا ہے")۔

اگرچہ LinkedList کے مصنف، Joshua Bloch کا کہنا ہے کہ یہ معاملہ ہے۔ :) پھر بھی، یہ نقطہ نظر 100% درست نہیں ہے، اور ہم نے خود کو اس پر قائل کر لیا ہے۔ ہماری پچھلی مثال میں، LinkedList 400 (!) گنا تیز تھی۔ ایک اور بات یہ ہے کہ واقعی کچھ ایسے حالات ہیں جہاں LinkedList بہترین انتخاب ہے۔ لیکن وہ موجود ہیں، اور صحیح وقت پر LinkedList آپ کو بہت اچھا انعام دے سکتی ہے۔ سبق کے آغاز میں ہم نے جو کہا اسے مت بھولنا: مختلف کاموں کے لیے سب سے زیادہ موثر ڈیٹا ڈھانچہ مختلف ہوتے ہیں۔ 100% یقین ہونا ناممکن ہے کہ کون سا ڈیٹا ڈھانچہ بہترین ہوگا جب تک کہ آپ کو اپنے کام کی تمام شرائط معلوم نہ ہوں۔ آپ ان مجموعوں کے بارے میں بعد میں مزید جان پائیں گے، جو انتخاب کو آسان بنا دے گا۔ لیکن سب سے آسان اور موثر آپشن ہمیشہ ایک جیسا ہوتا ہے: اپنے پروگرام میں استعمال ہونے والے اصل ڈیٹا پر دونوں کو آزمائیں۔ تب آپ خود دیکھ سکیں گے کہ دونوں قسم کی فہرستیں کیسی کارکردگی کا مظاہرہ کرتی ہیں اور آپ یقینی طور پر غلط نہیں ہوں گے۔ :) جو کچھ آپ نے سیکھا ہے اس کو تقویت دینے کے لیے، ہمارا مشورہ ہے کہ آپ ہمارے جاوا کورس سے ایک ویڈیو سبق دیکھیں