بنية بيانات القائمة المرتبطة في جافا

يتم إنشاء هياكل بيانات مختلفة لأغراض مختلفة. ربما تعرف عن 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 هو تطبيق لهذين الاثنين، ويسمح لنا بإنشاء قائمة انتظار ثنائية الاتجاه تتكون من أي كائنات بما في ذلك العناصر الخالية. 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<? Extends E> c) مخصص لإنشاء قائمة تحتوي على عناصر المجموعة المحددة، بالترتيب، يتم إرجاعها بواسطة مكرر المجموعة.

إعلان القائمة المرتبطة

في الواقع، تتكون القائمة المرتبطة (جافا أو أي لغة أخرى) من سلسلة من العقد. تم تصميم كل عقدة لتخزين كائن من النوع المحدد عند الإنشاء. لذا، لإنشاء LinkedList ، كود Java هو التالي:

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

لدينا كائن للاحتفاظ بسلسلة من الأعداد الصحيحة والروابط مع الجيران. ومع ذلك، فهو فارغ في الوقت الراهن.

العمليات الرئيسية لـ LinkedList

كالعادة، في حالة المجموعات، يمكنك وضع عناصر في LinkedList (حتى نهايتها أو في المنتصف)، وإزالتها من هناك، والحصول على عنصر حسب الفهرس. إذن ها هم:

• add(E element) يُلحق العنصر المحدد بنهاية هذه القائمة؛
• add(int Index, E element) يُدرج العنصر في فهرس الموضع المحدد ؛
• get(int Index) يُرجع العنصر إلى الموضع المحدد في هذه القائمة؛
• إزالة (int Index) إزالة العنصر الموجود في فهرس الموضع؛
• إزالة (كائن س) يزيل التواجد الأول لـ؟ o عنصر من هذه القائمة إذا كان موجودًا.
• Remove() يسترد ويزيل العنصر الأول من القائمة.

تنفيذ القائمة المرتبطة في جافا، وإضافة وإزالة العناصر. مثال

دعونا نجرب هذه العمليات عمليا. أولاً، تنفيذ Java LinkedList: إنشاء قائمة 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 element) بإدراج عنصر في القائمة

مثال Java LinkedList: كيف يعمل Iterator

لدينا هنا مثال صغير لرمز 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]

المزيد من عمليات Java LinkedList :

• addFirst() و addLast() تضيف عنصرًا إلى بداية/نهاية القائمة
• Clear () يزيل جميع العناصر من القائمة
• يحتوي على (Object o) يُرجع صحيحًا إذا كانت القائمة تحتوي على العنصر o.
• يقوم مؤشر IndexOf(Object o) بإرجاع فهرس التواجد الأول للعنصر o، أو -1 إذا لم يكن موجودًا في القائمة.
• set(int Index, E element) يستبدل العنصر الموجود في موضع الفهرس بالعنصر
• size() يُرجع كمية العناصر الموجودة في القائمة.
• تُرجع الدالة toArray() ‎ مصفوفة تحتوي على جميع عناصر القائمة من العنصر الأول إلى العنصر الأخير.

راجع للشغل كونها قائمة انتظار ذات حجمين، فإن LinkedList في Java يحتوي على عمليات محددة:

• pop() الذي ينبثق عنصرًا من المكدس (ممثلًا بالقائمة)
• Push(E e) الذي يدفع عنصرًا إلى المكدس (ممثلًا بهذه القائمة)

كيفية عكس 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 vs ArrayList: متى يتم استخدام القائمة الأولى

يعد كل من LinkedList و ArrayList بمثابة تطبيقات لواجهة القائمة . يقوم LinkedList بتنفيذه بقائمة مرتبطة بشكل مزدوج. يقوم ArrayList بتنفيذه باستخدام مصفوفة تغيير الحجم ديناميكيًا. كما تعلم، تحتوي كل عقدة في LinkedList على كائنات ومرجعين للجيران. وهذا يعني تكاليف ذاكرة إضافية لتخزين المراجع بين العناصر في حالة Java LinkedList . يقوم ArrayList بتنفيذه باستخدام مصفوفة لتغيير الحجم ديناميكيًا. تبدو بعض عمليات LinkedList و ArrayList متشابهة، ولكنها تعمل بطريقة مختلفة. في حالة ArrayList ، يمكنك التعامل مع المصفوفات الداخلية، في LinkedList - مع المراجع. ArrayList هو تطبيق القائمة الأكثر شيوعًا . يجب عليك بالتأكيد استخدام ArrayList عندما يكون الوصول إلى الفهرس أولوية حيث يتم تنفيذ هذه العمليات في وقت ثابت. تتم الإضافة إلى نهاية القائمة في المتوسط ​​أيضًا في وقت ثابت. علاوة على ذلك، ليس لدى ArrayList تكاليف إضافية لتخزين مجموعة من العناصر. قد تعتبر من السلبيات سرعة الإدراج والإزالة للعمليات عندما لا يتم ذلك في نهاية القائمة. يعد LinkedList أكثر فائدة في حالة أداء عمليات الإدراج والحذف بعدة طرق: إذا كنت تستخدم التكرارات، فسيحدث ذلك في وقت ثابت. تتم عمليات الوصول بالفهرس من خلال البحث من بداية النهاية (أيهما أقرب) إلى العنصر المطلوب. ومع ذلك، لا تنس التكاليف الإضافية لتخزين المراجع بين العناصر. إذن هنا عمليات LinkedList و ArrayList القياسية مع أوقات تشغيل خوارزمية. يشير N إلى عدد العناصر الموجودة بالفعل في القائمة. O(N) يعني أنه في أسوأ الحالات يجب علينا "المشي" عبر القائمة بأكملها حتى يتم العثور على الموضع المطلوب، على سبيل المثال، لإدراج العنصر الجديد في القائمة. O(1) يعني أن العملية تحدث في وقت ثابت، بشكل مستقل عن عدد العناصر.

تعقيد وقت القائمة المرتبطة

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

نتيجة القائمة المرتبطة:

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

كما ترون في هذه الحالة فإن LinkedList أكثر فاعلية. لنكن صادقين. في تطوير البرمجيات الحقيقي، يعد استخدام LinkedList نوعًا من الأحداث النادرة. ومع ذلك، يجب أن يعرف المحترف وجود بنية البيانات هذه ومزاياها. إذا كان LinkedList ضيفًا نادرًا في الكود الحقيقي ، فإنه يحظى بشعبية كبيرة في مقابلات Java Junior. ومع ذلك، إليكم ما كتبه جوشوا بلوخ عن LinkedList :

AddOn: قائمة مرتبطة منفردة Java

لا توجد قائمة مرتبطة بشكل فردي بين المجموعة الكلاسيكية في Java، القائمة المرتبطة بشكل فردي عبارة عن هيكل حيث تحتوي كل عقدة على كائن ومرجع إلى العقدة التالية، ولكن ليس للعقدة السابقة. Java LinkedList عبارة عن رابطين، لكن لا أحد يتدخل معك لإنشاء بنية بيانات خاصة بك، مثل قائمة مرتبطة منفردة، رمز>. فيما يلي بعض الخطوات لحل هذه المهام:

1. أنشئ فئة العقدة بخاصيتين، البيانات والتالي. التالي هو إشارة إلى العقدة التالية.
2. قم بإنشاء فئة FirstLast بخاصيتين، الرأس والذيل.
3. قم بإنشاء طريقة add () لإضافة عقدة جديدة إلى القائمة. تحقق مما إذا كانت القائمة فارغة أولاً ( head == null ). إذا كان الأمر كذلك، يشير الرأس والذيل إلى العقدة الجديدة. إذا لم تكن القائمة فارغة، فستتم إضافة العقدة الجديدة إلى النهاية، وبالتالي تشير السمة التالية للذيل إلى العقدة المضافة وتصبح العقدة الجديدة ذيل القائمة.

بالمناسبة، يمكنك محاولة إنشاء قائمة LinkedList الخاصة بك كتمرين أيضًا. حظا سعيدا في التعلم الخاص بك.