جاوا ۾ ڳنڍيل لسٽ ڊيٽا جي جوڙجڪ

مختلف ڊيٽا جي جوڙجڪ مختلف مقصدن لاء ٺاهيا ويا آهن. توهان شايد 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 لسٽ ۽ ڊيڪ انٽرفيس کي لاڳو ڪري ٿو . لسٽ انٽرفيس شيون شامل ڪرڻ جي ترتيب کي برقرار رکي ٿو ۽ انڊيڪس ذريعي شيون تائين رسائي جي اجازت ڏئي ٿو. "عام" قطار آخر تائين عناصر شامل ڪرڻ ۽ شروعات کان انھن کي ڪڍڻ جي حمايت ڪري ٿو. 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 Constructors

ڪوڊ ماخذ ڏانهن واپس، اسان اهو ڳولي سگهون ٿا ته LinkedList ۾ ٻه تعمير ڪندڙ آهن

• LinkedList() بغير پيراميٽر جي استعمال ڪيو ويندو آھي خالي لسٽ ٺاھڻ لاءِ.
• >LinkedList(collection<? extensions E>c) ھڪڙي فهرست ٺاھڻ لاءِ آھي جنھن ۾ مخصوص ڪيل مجموعن جا عنصر شامل آھن، ترتيب ۾، اھي ڪليڪشن جي ائٽريٽر طرفان موٽايا ويندا آھن.

LinkedList اعلان

حقيقت ۾، هڪ ڳنڍيل فهرست (جاوا يا ڪنهن ٻئي ٻوليء ۾) نوڊس جي هڪ ترتيب تي مشتمل آهي. هر نوڊ ٺهيل هڪ قسم جي اعتراض کي ذخيرو ڪرڻ لاء ٺهيل آهي جڏهن ٺاهي وئي آهي. تنهنڪري LinkedList ٺاهڻ لاء ، جاوا ڪوڊ هيٺ ڏنل آهي:

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

اسان وٽ هڪ اعتراض آهي ته انٽيجرز جي تسلسل ۽ پاڙيسرين سان ڳنڍڻ لاء. بهرحال، اهو هن وقت خالي آهي.

LinkedList مکيه آپريشن

عام طور تي، مجموعن جي صورت ۾ توهان عناصر کي LinkedList (ان جي پڇاڙي يا وچ ۾) ۾ وجهي سگهو ٿا، اتان هٽايو، ۽ انڊيڪس ذريعي هڪ عنصر حاصل ڪريو. تنهن ڪري اهي هتي آهن:

• add(E element) هن لسٽ جي آخر ۾ مخصوص عنصر شامل ڪريو؛
• add(int index, E عنصر) عنصر داخل ڪري ٿو مخصوص پوزيشن انڊيڪس تي ؛
• get(int index) هن لسٽ ۾ مخصوص پوزيشن تي عنصر کي واپس ڪري ٿو؛
• هٽايو (int index) عنصر کي هٽائي ٿو جيڪو پوزيشن انڊيڪس تي آهي؛
• هٽايو (Object o) جي پهرين واقعن کي هٽائي ٿو؟ o هن فهرست مان عنصر جيڪڏهن اهو موجود آهي.
• هٽائي ٿو () لسٽ جي پهرين عنصر کي ٻيهر حاصل ڪري ٿو ۽ هٽائي ٿو.

جاوا ۾ ڳنڍيل لسٽ تي عمل درآمد، عناصر شامل ڪرڻ ۽ ختم ڪرڻ. مثال

اچو ته انهن عملن کي عملي طور تي ڪوشش ڪريون. پهريون، جاوا LinkedList تي عملدرآمد: Strings جي LinkedList ٺاهڻ، اتي 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]

هڪ LinkedList ڪليڪشن فريم ورڪ جو هڪ حصو آهي ، توهان عناصر کي هٽائڻ لاءِ Iterator استعمال ڪري سگهو ٿا، ۽ انهي سان گڏ فهرستن لاءِ هڪ خاص آئٽرٽر — ListIterator . اڃا به وڌيڪ، آئٽرٽر سان آپريشن LinkedList طبقي جا بنيادي فائدا مهيا ڪن ٿا : داخل ڪرڻ / حذف ڪرڻ جي عملن جي سٺي ڪارڪردگي. Iterator استعمال ڪندي توھان انھن لاءِ مستقل وقت حاصل ڪري سگھو ٿا. بعد ۾ هن آرٽيڪل ۾، اسان ArrayList ۽ LinkedList + Iterator جي مقابلي لاءِ ڪوڊ جو مثال لکنداسين

• Iterator.remove() هن آئٽرٽر طرفان واپس ڪيل آخري عنصر کي هٽائي ٿو.
• ListIterator.add(E عنصر) لسٽ ۾ هڪ عنصر داخل ڪري ٿو

Java LinkedList مثال: ڪيئن آئيٽرٽر ڪم ڪري ٿو

هتي اسان وٽ هڪ ننڍڙو Java LinkedList مثال ڪوڊ آهي، جتي اسان ڪوشش ڪريون ٿا شامل ڪرڻ ۽ حذف ڪرڻ جي ذريعي 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]

وڌيڪ جاوا LinkedList آپريشن:

• addFirst() , addLast() هڪ عنصر شامل ڪريو لسٽ جي شروعات/آخر ۾
• صاف () فهرست مان سڀني عناصر کي هٽائي ٿو
• contains(Object o) صحيح موٽائي ٿو جيڪڏھن لسٽ ۾ o عنصر شامل آھي.
• indexOf (Object o) o عنصر جي پهرين واقعن جي انڊيڪس کي واپس ڪري ٿو، يا -1 جيڪڏهن اهو فهرست ۾ نه آهي.
• سيٽ (int index، E عنصر) عنصر کي انڊيڪس پوزيشن تي عنصر سان تبديل ڪري ٿو
• سائيز () فهرست ۾ عناصر جي مقدار کي واپس ڪري ٿو.
• toArray() ھڪڙي صف کي واپس ڏئي ٿو جنھن ۾ سڀني لسٽ جي عناصر شامل آھن پھرين کان آخري عنصر تائين.

BTW هڪ ٻه-سائيز قطار هجڻ ڪري، جاوا ۾ LinkedList مخصوص آپريشن کي اسٽيڪ ڪيو آهي:

• پاپ () جيڪو اسٽيڪ مان هڪ عنصر کي پاپ ڪري ٿو (فهرست جي نمائندگي ڪئي وئي آهي)
• push (E e) جيڪو هڪ عنصر کي اسٽيڪ تي دٻائي ٿو (هن لسٽ جي نمائندگي ڪئي وئي آهي)

LinkedList کي ڪيئن ريورس ڪجي: مثال

هتي هڪ ننڍڙو مثال آهي، هڪ مشهور، اڃا تائين نئين سکندڙن لاء هڪ آسان ڪم. اسان وٽ هڪ LinkedList آهي ۽ ان کي ريورس ڪرڻ گهرجي. سڀ کان آسان الگورٿم آهي 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 وٽ عناصر جي گروپ کي محفوظ ڪرڻ لاء اضافي خرچ نه آهي. توھان شمار ڪري سگھوٿا ڪنس جي طور تي داخل ڪرڻ جي رفتار کي ختم ڪرڻ ۽ عملن کي ختم ڪرڻ جڏھن اھو ڪيو ويو فهرست جي آخر ۾ نه. LinkedList وڌيڪ ڪارائتو آهي داخل ڪرڻ ۽ ختم ڪرڻ جي صورت ۾ آپريشن جي ڪارڪردگي ڪجهه طريقن سان: جيڪڏهن توهان استعمال ڪندا آهيو آئٽرٽر اهو مسلسل وقت ۾ ٿئي ٿو. انڊيڪس ذريعي رسائي جي عملن کي انجام ڏنو ويندو آهي ڳولا جي شروعات کان پڇاڙيءَ تائين (جيڪو به ويجهو هجي) گهربل عنصر تائين. بهرحال، عناصر جي وچ ۾ حوالن کي محفوظ ڪرڻ لاء اضافي خرچن جي باري ۾ نه وساريو. تنهن ڪري هتي معياري LinkedList ۽ ArrayList آپريشنز الورورٿمڪ رن ٽائمز سان. N مان مراد انھن شين جو تعداد آھي جيڪي اڳ ۾ ئي لسٽ تي آھن. O (N) جو مطلب آهي ته بدترين صورت ۾ اسان کي سڄي لسٽ ذريعي "هلڻ" گهرجي جيستائين گهربل پوزيشن نه ملي، مثال طور، فهرست ۾ نئين عنصر داخل ڪرڻ لاء. O (1) مطلب ته آپريشن مستقل وقت ۾ ٿئي ٿو، آزاديءَ سان شين جي تعداد تي.

LinkedList وقت جي پيچيدگي

ArrayList وقت جي پيچيدگي

LinkedList استعمال ڪرڻ وقت: مثال

يقينا، ArrayList سڀ کان وڌيڪ مشهور فهرست تي عمل درآمد آهي. جڏهن ته، توهان حالتن سان ملن ٿا، جڏهن شامل ڪرڻ / هٽائڻ جي عملن کي تمام گهڻو گهربل هجي. انهي صورت ۾، LinkedList سڀ گڏجي Iterator سان فائدو حاصل ڪري سگھن ٿا. هتي هڪ مثال آهي. اسان وٽ هڪ ڊگهي لسٽ آهي، ۽ اسان کي هن فهرست مان هر عنصر کي ختم ڪرڻ گهرجي. اچو ته هي ڪم 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

LinkedList لاءِ نتيجا:

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

جئين توهان ڏسي سگهو ٿا هن معاملي ۾ LinkedList طريقو وڌيڪ اثرائتو آهي. اچو ته ايماندار ٿي وڃو. حقيقي سافٽ ويئر ڊولپمينٽ ۾ LinkedList استعمال هڪ قسم جو نادر واقعو آهي. تنهن هوندي به، هڪ پروفيسر کي ڄاڻڻ گهرجي ته هن ڊيٽا جي جوڙجڪ جي وجود ۽ ان جي فائدن بابت. جيڪڏهن حقيقي ڪوڊ ۾ LinkedList هڪ نادر مهمان آهي، جاوا جونيئر انٽرويو تي اهو تمام مشهور آهي. ۽ اڃا تائين، هتي اهو آهي جيڪو جوشوا بلچ لکيو آهي LinkedList بابت :

AddOn: اڪيلو ڳنڍيل فهرست جاوا

جاوا ۾ ڪلاسيڪل ڪليڪشن جي وچ ۾ ڪابه سنگل لنڪ ٿيل لسٽ ناهي ، سنگل لنڪ لسٽ هڪ اهڙي جوڙجڪ آهي جتي هر نوڊ ۾ هڪ اعتراض ۽ ايندڙ نوڊ جو حوالو هوندو آهي، پر پوئين هڪ لاءِ نه. Java LinkedList ٻه-ڳنڍيل آهي، پر ڪو به توهان سان توهان جي پنهنجي ڊيٽا جي جوڙجڪ ٺاهڻ ۾ مداخلت نٿو ڪري، جهڙوڪ سنگل، ڪوڊ> لنڪ ٿيل لسٽ. هتي انهن ڪمن کي حل ڪرڻ لاء ڪجهه قدم آهن:

1. ھڪڙو نوڊ ڪلاس ٺاھيو ٻن خاصيتن، ڊيٽا ۽ ايندڙ سان. اڳيان ايندڙ نوڊ جو حوالو آهي.
2. فرسٽ لاسٽ ڪلاس ٺاھيو ٻن خاصيتن سان، سر ۽ دم.
3. لسٽ ۾ نئون نوڊ شامل ڪرڻ لاءِ add() طريقو ٺاهيو . چيڪ ڪريو ته لسٽ پهرين خالي آهي ( head == null ). جيڪڏهن ائين آهي، سر ۽ دم نئين نوڊ ڏانهن اشارو ڪيو. جيڪڏهن لسٽ خالي نه آهي، نئين نوڊ کي آخر ۾ شامل ڪيو ويندو، تنهنڪري دم جي ايندڙ خاصيت شامل ٿيل نوڊ ڏانهن اشارو ڪري ٿو ۽ نئين نوڊ فهرست جي دم بڻجي ويندي آهي.

انهي طريقي سان توهان ڪوشش ڪري سگهو ٿا توهان جي پنهنجي LinkedList هڪ مشق جي طور تي پڻ. توهان جي سکيا ۾ سٺي قسمت.