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

مختلف ڈیٹا ڈھانچے مختلف مقاصد کے لیے بنائے جاتے ہیں۔ آپ ArrayList کے بارے میں جان سکتے ہیں (اگر اب بھی نہیں ہے تو، ہم آپ کو مشورہ دیتے ہیں کہ پہلے اس کے بارے میں پڑھیں)۔ اس مضمون میں، ہم LinkedList کے بارے میں جاننے اور یہ جاننے کے لیے جا رہے ہیں کہ یہ مجموعہ کس چیز کے لیے اچھا ہے۔ اگر آپ LinkedList Java 8 (یا زبان کے بعد کے ورژن) کلاس کوڈ سورس (Oracle ویب سائٹ پر یا آپ کے IDE میں، IDEA کی صورت میں: کلاس کے نام پر crtl+B) کو دیکھیں گے تو آپ کو اگلا اعلان نظر آئے گا:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

اس وقت کوڈ سے سب سے اہم معلومات یہ ہے کہ LinkedList List اور Deque انٹرفیس کو لاگو کرتا ہے ۔ فہرست انٹرفیس اشیاء کو شامل کرنے کی ترتیب کو برقرار رکھتا ہے اور انڈیکس کے ذریعہ آئٹم تک رسائی کی اجازت دیتا ہے۔ "عام" قطار عناصر کو آخر میں شامل کرنے اور انہیں شروع سے نکالنے کی حمایت کرتی ہے۔ Deque ایک دو طرفہ قطار ہے، اور یہ دونوں اطراف سے عناصر کو شامل کرنے اور ہٹانے میں معاون ہے۔ آپ اسے اسٹیک اور قطار کے امتزاج کے طور پر سوچ سکتے ہیں۔ لہذا، LinkedList ان دونوں کا نفاذ ہے، اور یہ ہمیں ایک دو طرفہ قطار بنانے کی اجازت دیتا ہے جس میں null سمیت کسی بھی چیز پر مشتمل ہو۔ LinkedList عناصر کا مجموعہ ہے۔ ہم اسے کلاس کے کوڈ سورس میں دیکھ سکتے ہیں، اس بار فیلڈز پر توجہ دیں:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

ہر عنصر، عام طور پر ہم اسے Node کہتے ہیں، ایک آبجیکٹ پر مشتمل ہوتا ہے اور اس میں دو پڑوسی اشیاء کا حوالہ ہوتا ہے - پچھلا اور اگلا۔ لہذا، یہ میموری کو استعمال کرنے کے لحاظ سے زیادہ مؤثر نہیں ہے. جیسا کہ LinkedList اصل میں ایک دو طرفہ ڈھانچہ ہے، ہم آسانی سے دونوں اطراف سے عناصر کو شامل یا ہٹا سکتے ہیں۔

لنکڈ لسٹ کنسٹرکٹرز

کوڈ ماخذ پر واپس، ہم یہ جان سکتے ہیں کہ LinkedList میں دو کنسٹرکٹرز ہیں۔

• پیرامیٹر کے بغیر LinkedList() کو خالی فہرست بنانے کے لیے استعمال کیا جاتا ہے۔
• >LinkedList(Collection<? extensions E> c) مخصوص مجموعہ کے عناصر پر مشتمل ایک فہرست بنانے کے لیے ہے، ترتیب میں، وہ مجموعہ کے تکرار کرنے والے کے ذریعے واپس کیے جاتے ہیں۔

لنکڈ لسٹ کا اعلان

درحقیقت، ایک منسلک فہرست (جاوا یا کسی دوسری زبان میں) نوڈس کی ترتیب پر مشتمل ہوتی ہے۔ ہر نوڈ کو تخلیق کرتے وقت بیان کردہ قسم کی کسی چیز کو ذخیرہ کرنے کے لیے ڈیزائن کیا گیا ہے۔ تو LinkedList بنانے کے لیے ، جاوا کوڈ اگلا ہے:

LinkedList<Integer> myList = new LinkedList<>();

ہمارے پاس پڑوسیوں سے عدد اور روابط کی ترتیب رکھنے کے لیے ایک اعتراض ہے۔ تاہم، یہ اس وقت خالی ہے۔

لنکڈ لسٹ مین آپریشنز

معمول کے مطابق، کلیکشنز کے معاملے میں آپ عناصر کو LinkedList میں ڈال سکتے ہیں (اس کے آخر تک یا درمیان میں)، وہاں سے ہٹا سکتے ہیں، اور انڈیکس کے لحاظ سے ایک عنصر حاصل کر سکتے ہیں۔ تو وہ یہاں ہیں:

• add(E عنصر) اس فہرست کے آخر میں مخصوص عنصر کو شامل کرتا ہے۔
• add(int index, E عنصر) مخصوص پوزیشن انڈیکس پر عنصر داخل کرتا ہے ۔
• get(int index) عنصر کو اس فہرست میں مخصوص پوزیشن پر لوٹاتا ہے۔
• remove(int index) عنصر کو ہٹاتا ہے جو پوزیشن انڈیکس پر ہے۔
• ہٹا دیں (آبجیکٹ o) کی پہلی موجودگی کو ہٹاتا ہے؟ o اس فہرست سے عنصر اگر یہ موجود ہے۔
• remove() فہرست کے پہلے عنصر کو بازیافت اور ہٹاتا ہے۔

جاوا میں لنکڈ لسٹ کا نفاذ، عناصر کو شامل کرنا اور ہٹانا۔ مثال

آئیے ان کارروائیوں کو عملی طور پر آزماتے ہیں۔ سب سے پہلے، جاوا لنکڈ لسٹ کا نفاذ: سٹرنگز کی ایک لنکڈ لسٹ بنانا، وہاں 3 عناصر شامل کرنا۔ پھر ایک کو ہٹا دیں، پھر درمیان میں ایک شامل کریں۔

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

اس پروگرام کو چلانے کا نتیجہ:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

لنکڈ لسٹ کلیکشن فریم ورک کا ایک حصہ ہے ، آپ عناصر کو ہٹانے کے لیے Iterator کا استعمال کر سکتے ہیں، ساتھ ہی فہرستوں کے لیے ایک خصوصی تکرار کرنے والا — ListIterator ۔ اس سے بھی بڑھ کر، ایٹریٹر کے ساتھ آپریشنز LinkedList کلاس کے اہم فوائد فراہم کرتے ہیں : insert/delete آپریشنز کی اچھی کارکردگی۔ Iterator کا استعمال کرتے ہوئے آپ کو ان کے لیے مستقل وقت مل سکتا ہے۔ اس مضمون میں بعد میں، ہم ArrayList اور LinkedList+Iterator کا موازنہ کرنے کے لیے ایک کوڈ کی مثال لکھیں گے۔

• Iterator.remove() اس تکرار کنندہ کے ذریعہ واپس کردہ آخری عنصر کو ہٹاتا ہے۔
• ListIterator.add(E عنصر) فہرست میں ایک عنصر داخل کرتا ہے۔

جاوا لنکڈ لسٹ کی مثال: Iterator کیسے کام کرتا ہے۔

یہاں ہمارے پاس جاوا لنکڈ لسٹ کا ایک چھوٹا مثال کوڈ ہے، جہاں ہم Iterator کے ذریعے شامل کرنے اور حذف کرنے کی کوشش کرتے ہیں۔

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);

       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);

   }
}

اس پروگرام کو چلانے کا نتیجہ:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

مزید جاوا لنکڈ لسٹ آپریشنز:

• addFirst() , addLast() فہرست کے آغاز/آخر میں ایک عنصر شامل کریں۔
• clear() فہرست سے تمام عناصر کو ہٹاتا ہے۔
• contains(Object o) صحیح لوٹاتا ہے اگر فہرست میں o عنصر ہو۔
• indexOf(Object o) o عنصر کی پہلی موجودگی کا اشاریہ واپس کرتا ہے، یا -1 اگر یہ فہرست میں نہیں ہے۔
• سیٹ (int index, E عنصر) عنصر کو انڈیکس پوزیشن پر عنصر سے بدل دیتا ہے۔
• size() فہرست میں عناصر کی مقدار لوٹاتا ہے۔
• toArray() پہلے سے آخری عنصر تک فہرست کے تمام عناصر پر مشتمل ایک صف لوٹاتا ہے۔

BTW دو سائز کی قطار ہونے کی وجہ سے، جاوا میں LinkedList نے مخصوص آپریشنز کو اسٹیک کیا ہے:

• pop() جو اسٹیک سے ایک عنصر کو پاپ کرتا ہے (فہرست کے ذریعہ پیش کیا جاتا ہے)
• پش (ای ای) جو کسی عنصر کو اسٹیک پر دھکیلتا ہے (اس فہرست کے ذریعہ پیش کیا جاتا ہے)

LinkedList کو کیسے ریورس کریں: مثال

یہاں ایک چھوٹی سی مثال ہے، ایک مقبول، پھر بھی beginners کے لیے ایک آسان کام۔ ہمارے پاس ایک LinkedList ہے اور اسے پلٹنا چاہیے۔ سب سے آسان الگورتھم یہ ہے کہ لنکڈ لسٹ کو الٹ ترتیب میں دیکھیں اور ہر عنصر کو نئے میں ڈالیں۔ تاہم، شاید آپ کو ایک بہتر طریقہ مل جائے گا؟ یہ ہے ریورس لنکڈ لسٹ جاوا پروگرام کا کوڈ:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

نتیجہ:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList بمقابلہ ArrayList: پہلا استعمال کب کرنا ہے۔

LinkedList اور ArrayList دونوں لسٹ انٹرفیس کے نفاذ ہیں ۔ LinkedList اسے دوگنا منسلک فہرست کے ساتھ نافذ کرتی ہے۔ ArrayList اسے متحرک طور پر سائز تبدیل کرنے والی صف کا استعمال کرتے ہوئے لاگو کرتا ہے۔ جیسا کہ آپ پہلے ہی جانتے ہیں، LinkedList کے ہر نوڈ میں آبجیکٹ اور پڑوسیوں کے دو حوالہ جات ہوتے ہیں۔ اس کا مطلب ہے جاوا LinkedList کے معاملے میں عناصر کے درمیان حوالہ جات کو ذخیرہ کرنے کے لیے اضافی میموری لاگت ۔ ArrayList اسے متحرک طور پر سائز تبدیل کرنے والی صف کے ساتھ نافذ کرتی ہے۔ LinkedList اور ArrayList کے کچھ آپریشن ایک جیسے نظر آتے ہیں، لیکن وہ مختلف طریقے سے کام کرتے ہیں۔ ArrayList کیس میں ، آپ LinkedList میں - حوالوں کے ساتھ اندرونی صفوں کے ساتھ جوڑ توڑ کرتے ہیں ۔ ArrayList سب سے زیادہ مقبول فہرست کا نفاذ ہے۔ آپ کو یقینی طور پر ArrayList استعمال کرنا چاہئے جب انڈیکس تک رسائی ترجیح ہو کیونکہ یہ کارروائیاں مستقل وقت میں انجام دی جاتی ہیں۔ اوسطاً فہرست کے آخر میں شامل کرنا بھی مستقل وقت میں کیا جاتا ہے۔ اس سے بھی زیادہ، ArrayList میں عناصر کے ایک گروپ کو ذخیرہ کرنے کے لیے اضافی اخراجات نہیں ہیں۔ آپ داخل کرنے اور ہٹانے کی کارروائیوں کی رفتار کو Cons کے طور پر شمار کر سکتے ہیں جب یہ فہرست کے آخر میں نہ ہو۔ LinkedList کچھ طریقوں سے آپریشن کی کارکردگی کو داخل کرنے اور حذف کرنے کی صورت میں زیادہ مفید ہے: اگر آپ تکرار کرنے والے استعمال کرتے ہیں تو یہ مستقل وقت میں ہوتا ہے۔ انڈیکس کے ذریعہ رسائی کی کارروائیاں مطلوبہ عنصر کے اختتام کے آغاز سے (جو بھی قریب ہو) تلاش کرکے انجام دی جاتی ہیں۔ تاہم، عناصر کے درمیان حوالہ جات کو ذخیرہ کرنے کے لیے اضافی اخراجات کے بارے میں مت بھولنا۔ تو یہاں الگورتھمک رن ٹائم کے ساتھ معیاری LinkedList اور ArrayList آپریشنز۔ N سے مراد ان اشیاء کی تعداد ہے جو فہرست میں پہلے سے موجود ہیں۔ O(N) کا مطلب ہے کہ بدترین صورت میں ہمیں اس وقت تک پوری فہرست میں "چلنا" چاہئے جب تک کہ مطلوبہ پوزیشن نہ مل جائے، مثال کے طور پر، فہرست میں نیا عنصر داخل کرنا۔ O(1) کا مطلب ہے کہ آپریشن مستقل وقت میں ہوتا ہے، آزادانہ طور پر اشیاء کی تعداد پر۔

لنکڈ لسٹ ٹائم پیچیدگی

ArrayList وقت کی پیچیدگی

LinkedList کب استعمال کریں: مثال

یقینی طور پر، ArrayList سب سے زیادہ مقبول فہرست کا نفاذ ہے۔ تاہم، آپ ان حالات کو پورا کر سکتے ہیں، جب شامل/ہٹانے کی کارروائیوں کی کثرت سے ضرورت ہو۔ اس صورت میں، Iterator کے ساتھ LinkedList فائدہ مند ثابت ہو سکتی ہے۔ یہاں ایک مثال ہے۔ ہمارے پاس ایک لمبی فہرست ہے، اور ہمیں اس فہرست سے ہر عنصر کو حذف کرنا چاہیے۔ آئیے یہ کام ArrayList اور LinkedList + Iterator کے ساتھ کرتے ہیں ۔ ہم ہر آپریشن کے وقت کا موازنہ کرتے ہیں اور اسے کنسول میں پرنٹ کرتے ہیں۔ یہاں کوڈ ہے:

import java.util.*;
import java.util.function.BiPredicate;

public class ListTest2 {

   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());

       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }

   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);

           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }

   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }

   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

ArrayList کے لیے نتیجہ:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

لنکڈ لسٹ کا نتیجہ:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

جیسا کہ آپ اس معاملے میں دیکھ سکتے ہیں LinkedList طریقہ زیادہ موثر ہے۔ ایماندار بنیں. حقیقی سافٹ ویئر ڈویلپمنٹ میں LinkedList کا استعمال ایک قسم کا نایاب واقعہ ہے۔ اس کے باوجود، ایک پیشہ ور کو اس ڈیٹا ڈھانچے کے وجود اور اس کے فوائد کے بارے میں جاننا چاہیے۔ اگر حقیقی کوڈ میں LinkedList ایک نایاب مہمان ہے، تو Java Junior کے انٹرویوز پر یہ بہت مشہور ہے۔ اور پھر بھی، جوشوا بلوچ نے LinkedList کے بارے میں کیا لکھا ہے :

ایڈ آن: سنگلی لنکڈ لسٹ جاوا

جاوا میں کلاسیکی کلیکشن میں سنگلی لنکڈ لسٹ نہیں ہے ، سنگلی لنکڈ لسٹ ایک ایسا ڈھانچہ ہے جہاں ہر نوڈ میں ایک آبجیکٹ اور اگلے نوڈ کا حوالہ ہوتا ہے، لیکن پچھلے نوڈ کے لیے نہیں۔ Java LinkedList دو لنکڈ ہے، لیکن کوئی بھی آپ کے ساتھ اپنا ڈیٹا سٹرکچر بنانے میں مداخلت نہیں کرتا، جیسے سنگلی ,code> لنکڈ لسٹ۔ ان کاموں کو حل کرنے کے لیے کچھ اقدامات یہ ہیں:

1. دو صفات، ڈیٹا اور اگلی کے ساتھ نوڈ کلاس بنائیں ۔ اگلا اگلے نوڈ کا حوالہ ہے۔
2. دو صفات، سر اور دم کے ساتھ فرسٹ لاسٹ کلاس بنائیں ۔
3. فہرست میں ایک نیا نوڈ شامل کرنے کے لیے ایک add() طریقہ بنائیں۔ چیک کریں کہ آیا فہرست پہلے خالی ہے ( head == null )۔ اگر ایسا ہے تو، سر اور دم نئے نوڈ کا حوالہ دیتے ہیں۔ اگر فہرست خالی نہیں ہے تو، نئے نوڈ کو آخر میں شامل کیا جائے گا، لہذا ٹیل کی اگلی صفت سے مراد شامل کردہ نوڈ ہے اور نیا نوڈ فہرست کا دم بن جاتا ہے۔

ویسے آپ ایک مشق کے طور پر بھی اپنی LinkedList بنانے کی کوشش کر سکتے ہیں۔ آپ کے سیکھنے میں اچھی قسمت.