في المقالة السابقة ، قمنا بتحليل التنفيذ الأساسي لـ ArrayList وعرفنا أن التنفيذ الأساسي لـ ArrayList يعتمد على المصفوفات ، بحيث يتمتع بخصائص البحث السريع والتعديل أثناء الإدراج البطيء والحذف. يعد LinkedList الذي تم تقديمه في هذه المقالة تطبيقًا آخر لواجهة القائمة. تعتمد طبقتها الأساسية على قائمة مرتبطة ثنائية الاتجاه. لذلك ، فإنه يحتوي على خصائص الإدراج السريع والحذف أثناء البحث البطيء والتعديل. بالإضافة إلى ذلك ، يمكن تحقيق وظائف قوائم الانتظار والمداخن من خلال تشغيل القائمة المرتبطة ثنائية الاتجاه. يظهر الهيكل الأساسي لـ LinkedList في الشكل أدناه.
يمثل F مرجع عقدة الرأس ، ويمثل L مرجع عقدة الذيل ، وكل عقدة في القائمة المرتبطة بها ثلاثة عناصر ، وهي مرجع العقدة الأمامية (P) ، وقيمة عنصر العقدة (E) ، ومرجع العقدة اللاحق (N). يتم تمثيل العقدة من خلال عقدة الفئة الداخلية ، دعونا نلقي نظرة على هيكلها الداخلي.
// عقدة الفئة الداخلية الفئة الثابتة الخاصة <e> {e item ؛ // element node <e> next ؛ // عقدة العقدة التالية <e> prev ؛ // عقدة العقدة السابقة (العقدة <e> prev ، e element ، node <e> next) {this.item = element ؛ this.next = التالي ؛ this.prev = prev ؛ }}عقدة الفئة الداخلية بسيطة للغاية في الواقع ، مع ثلاثة متغيرات فقط من الأعضاء ومشارك. يمثل العنصر قيمة العقدة ، التالي هو الإشارة إلى العقدة التالية ، و DRED هو المرجع إلى العقدة السابقة. يتم تمرير هذه القيم الثلاث من خلال المنشئ. بعد ذلك ، دعنا نلقي نظرة على متغيرات الأعضاء ومقدمي LinkedList.
// يتم ترجمة عدد عناصر SET int size = 0 ؛ // مرجع عقدة الرأس العابرة <e> first ؛ // يشير عقدة الذيل إلى العقدة العابرة <e> last ؛ // The Parameterless Constructor public LinkedList () addall (c) ؛}
يحمل LinkedList مرجعًا إلى عقدة الرأس ومرجع إلى عقدة الذيل. يحتوي على مُنشئين ، أحدهما مُنشئ بدون معلمات ، والآخر هو مُنشئ تم تمريره إلى المجموعة الخارجية. على عكس ArrayList ، لا تحدد LinkedList منشئ الحجم الأولي. تحقق من أساليبها لإضافة وحذف وتعديل والبحث.
// إضافة (إضافة) Boolean Public Add (e e) {// إضافة linklast (e) ؛ return true ؛} // إضافة (insert) void public add (int index ، e element) {checkPositionIndex (index) ؛ if (index == size) {// إضافة linklast (element) ؛ } آخر {// insert linkbefore (العنصر ، العقدة (الفهرس)) ؛ }} // delete (إعطاء الفهرس) e public e remove (int index) {// تحقق مما إذا كان التراجع هو checkElementIndex (index) ؛ return Unlink (node (index)) ؛} // delete (element element) public boolean remove (object o) {if (o == null) {for (node <e> x = first ؛ x! = null ؛ x = x.next) {if (x.item == null) {unflink (x) ؛ العودة صحيح. }}} آخر {// قائمة ارتباط Tranquility لـ (Node <e> x = first ؛ x! = null ؛ x = x.next) {if (o.equals (x.item)) {// deflete (x) ؛ العودة صحيح. }}} return false ؛} // قم بتغيير مجموعة e العامة (int index ، e element) {// تحقق مما إذا كان التراجع هو checkElementIndex (index) ؛ // احصل على مرجع العقدة للعقدة التراكمية المحددة <e> x = node (index) ؛ // احصل على قيمة العقدة التراكمية المحددة E Oldval = X.Item ؛ // قم بتعيين عنصر العقدة على القيمة الجديدة x.item = العنصر ؛ // إرجاع القيمة السابقة إرجاع OldVal ؛} // تحقق من Public E GET (int Index) {// تحقق مما إذا كان المنشور هو checkElementIndex (index) ؛ // إرجاع قيمة العقدة لعقدة الإرجاع المشترك المحدد (index) .item ؛}طريقة إضافة عناصر في LinkedList هي أساسا استدعاء الطريقتين Linklast و LinkBefore. تتمثل طريقة LinkLast في ربط عنصر خلف القائمة المرتبطة ، وتتمثل طريقة LinkBefore في إدراج عنصر في منتصف القائمة المرتبطة. تزيل طريقة حذف LinkedList عنصرًا من القائمة المرتبطة من خلال استدعاء طريقة غير مرتبة. دعونا نلقي نظرة على الكود الأساسي لعمليات الإدراج والحذف في القائمة المرتبطة.
// قبل الارتباط بـ linkbefore node void fore (e e ، node <e> succ) {// احصل على مرجع العقدة السابقة للعقدة النهائية المعطاة <e> pred = succ.prev ؛ // قم بإنشاء عقدة جديدة ، يشير مرجع العقدة السابقة للعقدة الجديدة إلى العقدة السابقة للعقدة المحددة // مرجع العقدة التالية للعقدة الجديدة تشير إلى العقدة النهائية المعطاة <e> newNode = New Node <> (pred ، e ، succ) ؛ // نقطة مرجع العقدة السابقة للعقدة المحددة للعقدة الجديدة Succ.prev = newNode ؛ // إذا كانت العقدة السابقة للعقدة المحددة فارغة ، فهذا يعني أن العقدة المعطاة هي عقدة الرأس إذا (pred == null) {// نقطة مرجع عقدة الرأس إلى العقدة الجديدة = newNode ؛ } else {// خلاف ذلك ، قم بإشارة مرجع العقدة التالية إلى العقدة الجديدة pred.next = newNode ؛ } // إضافة عدد عناصر تعيين حجم واحد ++ ؛ // إضافة عدد التعديلات الواحدة modcount ++ ؛ } // قم بإلغاء تحميل العقدة المحددة e unlink (node <e> x) {// احصل على عنصر العقدة المحددة e element e = x.item ؛ // احصل على المرجع إلى العقدة التالية للعقدة النهائية المعطاة <e> next = x.next ؛ // احصل على المرجع إلى العقدة السابقة للعقدة النهائية المعطى <e> prev = x.prev ؛ // إذا كانت العقدة السابقة للعقدة المحددة فارغة ، فشرح: العقدة المعطاة هي عقدة رأس إذا (prev == null) {// نقطة مرجع عقدة الرأس إلى العقدة التالية للعقدة المحددة أولاً = التالي ؛ } آخر {// المرجع العقدة الخلف للعقدة السابقة تشير إلى العقدة اللاحقة للعقدة المعطاة Prev.Next = التالي ؛ // مرجع العقدة السابقة للعقدة المعطاة x.prev = null ؛ } // إذا كانت العقدة التالية للعقدة المعطاة فارغة ، فهذا يعني أن العقدة المعطاة هي عقدة ذيل إذا (التالي == null) {// نقطة مرجع عقدة الذيل إلى العقدة السابقة للعقدة المحددة last = prev ؛ } آخر {// المرجع العقدة الأمامية للعقدة التالية تشير إلى العقدة السابقة للعقدة المعطاة next.prev = prev ؛ x.next = null ؛ } // تفريغ عنصر العقدة المعطاة x.item = null ؛ // طرح عدد العناصر المحددة حسب الحجم-؛ // إضافة modcount ++ ؛ عنصر العودة ؛} LinkBefore و Ilninl هي عمليات تمثيلية لربط العقد وإلغاء تثبيت العقد. تتشابه الطرق الأخرى لربط العقد وإلغاء التثبيت في كلا الطرفين ، لذلك نركز على LinkBefore و INFLING TELLES.
مخطط عملية طريقة LinkBefore:
مخطط العملية للأسلوب غير المرتبط:
من خلال التوضيح أعلاه ، فإن التعقيد الزمني لعمليات الإدراج والحذف للقائمة المرتبطة هو O (1) ، وتتطلب عمليات البحث والتعديل للقائمة المرتبطة اجتياز القائمة المرتبطة لتحديد موقع العناصر. تسمى كلتا العمليتين طريقة العقدة (int index) لتحديد موقع العناصر لمعرفة كيفية تحديد موقع العناصر من خلال الاشتراكات.
// GET NODE NODE <E> NODE (int index) {// إذا كان الفهرس في النصف الأول من القائمة المرتبطة ، تحقق من البداية إذا (index <(size> 1)) {node <e> x = first ؛ لـ (int i = 0 ؛ i <index ؛ i ++) {x = x.next ؛ } إرجاع x ؛ } آخر {// إذا كان الفهرس في النصف الثاني من القائمة المرتبطة ، تحقق من العقدة النهائية <e> x = last ؛ لـ (int i = size-1 ؛ i> index ؛ i--) {x = x.prev ؛ } إرجاع x ؛ }} عند تحديد موقع المنشأة ، حدد أولاً ما إذا كان في النصف العلوي أو النصف السفلي من القائمة المرتبطة. إذا كان في النصف العلوي ، ابدأ من البداية ، وإذا كان النصف السفلي ، فابدأ من النهاية. لذلك ، فإن التعقيد الزمني لتشغيل البحث وتعديل المنشأة هو O (N/2). من خلال تشغيل القائمة المرتبطة ثنائية الاتجاه ، يمكن أيضًا تحقيق وظائف قوائم الانتظار الفردية وقوائم الانتظار في اتجاهين ومداخن.
عملية قائمة انتظار في اتجاه واحد:
// احصل على عقدة الرأس العامة e peek () {Final Node <e> f = first ؛ العودة (f == فارغة)؟ NULL: f.Item ؛} // احصل على element e e e e e e e e {return getfirst () ؛} العودة (f == فارغة)؟ NULL: Unlinkfirst (f) ؛} // قم بإزالة عقدة الرأس العامة e remove () {return removeFirst () ؛} // إضافة عقدة في نهاية عرض قائمة الانتظار المنطقية العامة (e e) {return add (e) ؛}عملية قائمة الانتظار ثنائية الاتجاه:
// إضافة عرض منطقي عام (e e) {addFirst (e) ؛ return true ؛} // إضافة عرض منطقي عام (e e) {addlast (e) ؛ return true ؛} // الحصول على عقدة الرأس العامة e peekfirst () {final node <e> f = first ؛ العودة (f == فارغة)؟ NULL: F.ITEM ؛ } // احصل على عقدة الذيل العامة e peeklast () {final node <e> l = last ؛ العودة (l == فارغة)؟ NULL: L.ITEM ؛}عملية المكدس:
// وضع مكدس public void push (e e) {addFirst (e) ؛} // وضع المكدس pop e pop () {return removeFirst () ؛} سواء كانت قائمة انتظار في اتجاه واحد أو قائمة انتظار ثنائية الاتجاه أو مكدس ، فإنها تعمل بالفعل على العقد والذيل في القائمة المرتبطة. تعتمد تطبيقاتها على الطرق الأربعة: addfirst () ، addlast () ، removeFirst () ، و readovelast (). تشبه عملياتهم linkbefore () و unlink () ، باستثناء أن الشخص هو العمل على طرفي القائمة المرتبطة ، والآخر هو العمل في منتصف القائمة المرتبطة. يمكن القول أن هذه الأساليب الأربعة هي حالات خاصة من LinkBefore () وطرق غير () ، لذلك ليس من الصعب فهم تطبيقاتها الداخلية ، لذلك لن أقدمها هنا. في هذه المرحلة ، فإن تحليلنا لـ LinkedList على وشك الانتهاء ، وسنلخص النقاط الرئيسية في النص كله:
1. يتم تنفيذ LinkedList بناءً على قائمة مرتبطة ثنائية الاتجاه. سواء كان ذلك هو الإضافة أو الحذف والتعديل والبحث أو تنفيذ قوائم الانتظار والمداخن ، يمكن تنفيذها من خلال عقد التشغيل.
2. LinkedList لا تحتاج إلى تحديد السعة مقدمًا ، لأنه استنادًا إلى عمليات القائمة المرتبطة ، ستزداد قدرة المجموعة تلقائيًا مع إضافة العناصر.
3. يتم تقليل الذاكرة التي تشغلها المجموعة بعد حذف LinkedList تلقائيًا ، وليس هناك حاجة لاستدعاء طريقة TrimTosize () مثل ArrayList
4. لا يتم مزامنة جميع طرق LinkedList ، لذلك ليست آمنة لخيط ، ويجب تجنبها في بيئات متعددة الخيوط.
5. يعتمد التحليل أعلاه على JDK1.7 ، وسيكون للإصدارات الأخرى بعض الاختلافات ، لذلك لا يمكن تعميمها.
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.