يتم إنشاء هياكل بيانات مختلفة لأغراض مختلفة. ربما تعرف عن ArrayList (إذا لم تكن تعرفه بعد، فنوصيك بقراءته أولاً). في هذه المقالة، سنتعرف على LinkedList وندرك فائدة هذه المجموعة. إذا نظرت إلى مصدر كود فئة LinkedList Java 8 (أو إصدار أحدث من اللغة) (على موقع Oracle الإلكتروني أو في IDE الخاص بك، في حالة IDEA: crtl+B في اسم الفئة) سترى الإعلان التالي:
في الوقت الحالي، أهم المعلومات من الكود هي حقيقة أن LinkedList ينفذ واجهات List و Deque . تحافظ واجهة القائمة على تسلسل إضافة العناصر وتسمح بالوصول إلى العنصر عن طريق الفهرس. تدعم قائمة الانتظار "العادية" إضافة العناصر إلى النهاية واستخراجها من البداية. Deque عبارة عن قائمة انتظار ثنائية الاتجاه، وهي تدعم إضافة وإزالة العناصر من كلا الجانبين. قد تفكر في الأمر على أنه مزيج من المكدس وقائمة الانتظار. لذلك، LinkedList هو تطبيق لهذين الاثنين، ويسمح لنا بإنشاء قائمة انتظار ثنائية الاتجاه تتكون من أي كائنات بما في ذلك العناصر الخالية. LinkedList عبارة عن مجموعة من العناصر. يمكننا أن نرى ذلك في مصدر التعليمات البرمجية للفصل، هذه المرة انتبه إلى الحقول:
transientint size =0;/**
* Pointer to first node.
*/transientNode<E> first;/**
* Pointer to last node.
*/transientNode<E> last;
كل عنصر، نسميه عادةً Node ، يحتوي على كائن ويشير إلى كائنين متجاورين - السابق والتالي. ومن ثم، فهي ليست فعالة للغاية من حيث استخدام الذاكرة. نظرًا لأن LinkedList عبارة عن بنية ثنائية الاتجاه، فيمكننا بسهولة إضافة أو إزالة العناصر من كلا الجانبين.
منشئو القائمة المرتبطة
بالعودة إلى مصدر الكود، يمكننا معرفة أن LinkedList لديه مُنشئان
يتم استخدام LinkedList() بدون معلمات لإنشاء قائمة فارغة.
>LinkedList(Collection<? Extends E> c) مخصص لإنشاء قائمة تحتوي على عناصر المجموعة المحددة، بالترتيب، يتم إرجاعها بواسطة مكرر المجموعة.
إعلان القائمة المرتبطة
في الواقع، تتكون القائمة المرتبطة (جافا أو أي لغة أخرى) من سلسلة من العقد. تم تصميم كل عقدة لتخزين كائن من النوع المحدد عند الإنشاء. لذا، لإنشاء LinkedList ، كود Java هو التالي:
LinkedList<Integer> myList =newLinkedList<>();
لدينا كائن للاحتفاظ بسلسلة من الأعداد الصحيحة والروابط مع الجيران. ومع ذلك، فهو فارغ في الوقت الراهن.
العمليات الرئيسية لـ LinkedList
كالعادة، في حالة المجموعات، يمكنك وضع عناصر في LinkedList (حتى نهايتها أو في المنتصف)، وإزالتها من هناك، والحصول على عنصر حسب الفهرس. إذن ها هم:
add(E element) يُلحق العنصر المحدد بنهاية هذه القائمة؛
add(int Index, E element) يُدرج العنصر في فهرس الموضع المحدد ؛
get(int Index) يُرجع العنصر إلى الموضع المحدد في هذه القائمة؛
إزالة (int Index) إزالة العنصر الموجود في فهرس الموضع؛
إزالة (كائن س) يزيل التواجد الأول لـ؟ o عنصر من هذه القائمة إذا كان موجودًا.
Remove() يسترد ويزيل العنصر الأول من القائمة.
تنفيذ القائمة المرتبطة في جافا، وإضافة وإزالة العناصر. مثال
دعونا نجرب هذه العمليات عمليا. أولاً، تنفيذ Java LinkedList: إنشاء قائمة LinkedList من السلاسل، وإضافة 3 عناصر إليها. ثم قم بإزالة واحدة، ثم قم بإضافة واحدة في المنتصف.
publicclassMyLinkedTest{publicstaticvoidmain(String[] args){String h1 ="my";String h2 ="favorite";String h3 ="book";// LinkedList implementation in JavaLinkedList<String> linkedList =newLinkedList();
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.
publicclassMyLinkedTest{publicstaticvoidmain(String[] args){String h1 ="my";String h2 ="favorite";String h3 ="book";LinkedList<String> linkedList =newLinkedList();
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 بترتيب عكسي ووضع كل عنصر في العنصر الجديد. ومع ذلك، ربما سوف تجد طريقة أفضل؟ فيما يلي رمز برنامج جافا للقائمة المرتبطة العكسية:
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) يعني أن العملية تحدث في وقت ثابت، بشكل مستقل عن عدد العناصر.
تعقيد وقت القائمة المرتبطة
عملية Java LinkedList
فعالية الخوارزمية
الحصول على (مؤشر كثافة العمليات)
O(n) ، في المتوسط — n/4 خطوات، حيث n هو حجم LinkedList
إضافة (العنصر E)
يا(1)
إضافة (مؤشر كثافة العمليات، عنصر E)
O(n) ، في المتوسط — n/4 خطوات؛ إذا كان مؤشر = 0 ثم O(1) ، لذلك إذا كنت بحاجة إلى إضافة شيء ما في بداية القائمة، فقد يكون LinkedList<E> خيارًا جيدًا
إزالة (مؤشر كثافة العمليات)
O(n) ، في المتوسط — n/4 خطوات
التكرار.إزالة ()
O(1) هذا هو السبب الرئيسي لاستخدام LinkedList<E>
ArrayList تعقيد الوقت
عملية القائمة المرتبطة
فعالية الخوارزمية
الحصول على (مؤشر كثافة العمليات)
O(1) أحد الأسباب الرئيسية لاستخدام ArrayList<E>
إضافة (العنصر E)
O(n) هي الحالة الأسوأ حيث يجب تغيير حجم المصفوفة ونسخها، ومع ذلك، من الناحية العملية، فهي ليست سيئة للغاية
إضافة (مؤشر كثافة العمليات، عنصر E)
O(n) ، n/2 خطوات في المتوسط
إزالة (مؤشر كثافة العمليات)
O(n) ، n/2 خطوات في المتوسط
التكرار.إزالة ()
O(n) ، n/2 خطوات في المتوسط
ListIterator.add(العنصر E)
O(n) ، n/2 خطوات في المتوسط
متى تستخدم LinkedList: مثال
من المؤكد أن ArrayList هو تطبيق القائمة الأكثر شيوعًا . ومع ذلك، قد تواجه مواقف عندما تكون عمليات الإضافة/الإزالة مطلوبة كثيرًا. في هذه الحالة، قد يكون كل LinkedList مع Iterator مفيدًا. هنا مثال. لدينا قائمة طويلة، ويجب علينا حذف كل عنصر من هذه القائمة. لنقم بهذه المهمة باستخدام ArrayList و LinkedList + Iterator . نحن نقارن وقت كل عملية ونطبعها على وحدة التحكم. هنا الكود:
importjava.util.*;importjava.util.function.BiPredicate;publicclassListTest2{staticvoidremoveElements(List<Double> list,BiPredicate<Integer,Double> predicate){// start navigation from end to preserve indexes of removed itemsListIterator<Double> iterator = list.listIterator(list.size());while(iterator.hasPrevious()){Double element = iterator.previous();if(predicate.test(iterator.previousIndex()+1, element)){
iterator.remove();}}}staticclassTestCase1{publicstaticvoidmain(String[] args){LinkedList<Double> testedList1 =newLinkedList<>(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 =newArrayList<>(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);}}staticclassTestLinkedListPerformance{publicstaticvoidmain(String[] args){LinkedList<Double> testedList =newLinkedList<>();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);}}staticclassTestArrayListPerformance{publicstaticvoidmain(String[] args){ArrayList<Double> testedList =newArrayList<>();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);}}}
كما ترون في هذه الحالة فإن LinkedList أكثر فاعلية. لنكن صادقين. في تطوير البرمجيات الحقيقي، يعد استخدام LinkedList نوعًا من الأحداث النادرة. ومع ذلك، يجب أن يعرف المحترف وجود بنية البيانات هذه ومزاياها. إذا كان LinkedList ضيفًا نادرًا في الكود الحقيقي ، فإنه يحظى بشعبية كبيرة في مقابلات Java Junior. ومع ذلك، إليكم ما كتبه جوشوا بلوخ عن LinkedList :
AddOn: قائمة مرتبطة منفردة Java
لا توجد قائمة مرتبطة بشكل فردي بين المجموعة الكلاسيكية في Java، القائمة المرتبطة بشكل فردي عبارة عن هيكل حيث تحتوي كل عقدة على كائن ومرجع إلى العقدة التالية، ولكن ليس للعقدة السابقة. Java LinkedList عبارة عن رابطين، لكن لا أحد يتدخل معك لإنشاء بنية بيانات خاصة بك، مثل قائمة مرتبطة منفردة، رمز>. فيما يلي بعض الخطوات لحل هذه المهام:
أنشئ فئة العقدة بخاصيتين، البيانات والتالي. التالي هو إشارة إلى العقدة التالية.
قم بإنشاء فئة FirstLast بخاصيتين، الرأس والذيل.
قم بإنشاء طريقة add () لإضافة عقدة جديدة إلى القائمة. تحقق مما إذا كانت القائمة فارغة أولاً ( head == null ). إذا كان الأمر كذلك، يشير الرأس والذيل إلى العقدة الجديدة. إذا لم تكن القائمة فارغة، فستتم إضافة العقدة الجديدة إلى النهاية، وبالتالي تشير السمة التالية للذيل إلى العقدة المضافة وتصبح العقدة الجديدة ذيل القائمة.
بالمناسبة، يمكنك محاولة إنشاء قائمة LinkedList الخاصة بك كتمرين أيضًا. حظا سعيدا في التعلم الخاص بك.
GO TO FULL VERSION