قائمة الارتباط المطلوبة:
فرز حسب القيم الرئيسية. عند حذف رأس السلسلة ، يتم حذف قيمة الحد الأدنى (/الحد الأقصى). عند الإدراج ، ابحث عن موضع الإدراج.
عند الإدراج ، تحتاج إلى مقارنة O (n) ، ومتوسط O (n/2) ، وعند حذف البيانات الدنيا (/الحد الأقصى) في رأس السلسلة ، تكون الكفاءة O (1) ،
إذا كان التطبيق يتطلب وصولًا متكررًا (إدراج/العثور/حذف) إلى أصغر (/أقصى) عناصر البيانات ، فإن القوائم المرتبطة المطلوبة هي خيار جيد. يمكن أن تستخدم قوائم قوائم الأولوية القوائم المرتبطة المطلوبة لتنفيذ فرز الإدراج من القوائم المرتبطة المطلوبة:
للحصول على صفيف غير مرتبة ، قم بفرزه بقائمة مرتبطة مرتبة ، والمستوى الزمني للمقارنة هو O (n^2)
مستوى زمن النسخ هو O (2*N). نظرًا لأن عدد النسخ صغيرة ، يتم نقل البيانات الموجودة في القائمة المرتبطة بأوقات لأول مرة ، ثم يتم نسخها من القائمة المرتبطة بالمصفوفة. N مرات ، في كل مرة يتم فيها إدخال رابط جديد ، ليست هناك حاجة لنسخ البيانات المتحركة ، فقط واحد أو اثنين من الروابط تحتاج إلى تغيير مجال الارتباط.
استيراد java.util.arrays ؛ استيراد java.util.random ؛ / *** إدراج صفائف التورم في قائمة مرتبطة مرتبطة* @Author Stone*/ Class Public ClasseListInsertSort <T يمتد قابلة للمقارنة <T >> {Link Private <T> أولاً ؛ // First Node Public LinkedListinSertSort () {} public boolean isempty () {return first == null ؛ } public void sortlist (t [] ary) {if (ary == null) {return ؛ } // إدراج عناصر صفيف في القائمة المرتبطة وفرزها في قائمة مرتبطة مرتبة لـ (T Data: ARY) {insert (data) ؛ } //} public void insert (t data) {// insert إلى رأس السلسلة ، فرز من رابط صغير إلى كبير <T> newLink = New Link <T> (Data) ؛ Link <t> current = first ، previour = null ؛ بينما (current! = null && data.compareto (current.data)> 0) {prevent = current ؛ الحالي = current.next ؛ } if (previp == null) {first = newLink ؛ } else {previct.next = newLink ؛ } newLink.next = current ؛ } الرابط العام <T> deletefirst () {// حذف رابط رأس السلسلة <T> temp = first ؛ أولا = الأول. // تغيير العقدة الأولى لإرجاع درجة الحرارة ؛ } الرابط العام <T> Find (t t) {link <t> find = first ؛ بينما (البحث! = null) {if (! find.data.equals (t)) {find = find.next ؛ } آخر {break ؛ }} العثور على ؛ } الرابط العام <T> delete (t t) {if (isempty ()) {return null ؛ } آخر {if (first.data.equals (t)) {link <t> temp = first ؛ أولا = الأول. // تغيير العقدة الأولى إلى درجة حرارة الإرجاع العقدة التالية ؛ }} link <t> p = first ؛ Link <t> q = first ؛ بينما (! p.data.equals (t)) {if (p.next == null) {// تشير إلى أنه لم يتم العثور على عودة فارغة في نهاية السلسلة ؛ } آخر {q = p ؛ p = p.next ؛ }} q.next = p.next ؛ العودة P ؛ } public void displaylist () {// travel system.out.println ("list (first-> last):") ؛ Link <t> current = first ؛ بينما (current! = null) {current.displayLink () ؛ الحالي = current.next ؛ }} public void displistlisterSe () {// رابط اجتياز عكسي <T> p = first ، q = first.next ، t ؛ بينما يتم عكس (Q! = null) {// مؤشر ، فإن ترتيب البيانات المسحوب هو متخلف t = q.next ؛ // no3 if (p == first) {// عندما يكون الرأس الأصلي ، يجب أن يكون. } q.next = p ؛ // no3 -> no1 مؤشر عكس p = q ؛ // البدء هو عكس Q = t ؛ // no3 ابدأ} // في IF في الحلقة أعلاه ، أولاً. بعد العكس ، يتم تعيين P إلى أولاً أولا = P ؛ قائمة العرض () ؛ } رابط الفئة <T> {// Link Point T Data ؛ // رابط حقل البيانات <T> التالي ؛ // المؤشر اللاحق ، رابط مجال سلسلة العقدة (بيانات t) {this.data = data ؛ } void displaylink () {system.out.println ("البيانات هي" + data.toString ()) ؛ }} public static void main (string [] args) {linkedListInSertSort <integer> list = new LinkedListIntSertSort <integer> () ؛ عشوائي عشوائي = جديد عشوائي () ؛ int len = 5 ؛ عدد صحيح [] ary = عدد صحيح جديد [len] ؛ لـ (int i = 0 ؛ i <len ؛ i ++) {ary [i] = random.nextint (1000) ؛ } system.out.println ("--------------") ؛ System.out.println (Arrays.ToString (ary)) ؛ System.out.println ("-------------------------------------------------------) ؛ list.sortlist (ary) ؛ list.displaylist () ؛}}
مطبعة
--- قبل الفرز ---- [595 ، 725 ، 310 ، 702 ، 444] --- بعد فرز القائمة المرتبطة ---- القائمة (أولاً-> الأخير): البيانات هي 310 البيانات هي 444 البيانات هي 595 البيانات هي 702 البيانات هي 725
انعكاس قائمة واحدة مرتبطة:
الفئة العامة singleLinkedListerSe {public static void main (string [] args) {node head = new node (0) ؛ عقدة temp = null ؛ العقدة cur = null ؛ لـ (int i = 1 ؛ i <= 10 ؛ i ++) {temp = new node (i) ؛ if (i == 1) {head.setNext (temp) ؛ } آخر {cur.setNext (temp) ؛ } cur = temp ؛ } // 10.next = null ؛ العقدة H = الرأس ؛ بينما (h! = null) {system.out.print (h.getData () + "/t") ؛ h = h.getNext () ؛ } system.out.println () ؛ // invert 1 // h = node.reverse1 (head) ؛ // بينما (h! = null) {// system.out.print (h.getData () + "/t") ؛ // h = h.getNext () ؛ //} // invert 2 h = node.reverse1 (head) ؛ بينما (h! = null) {system.out.print (h.getData () + "/t") ؛ h = h.getNext () ؛ }}}/** كل عقدة قائمة مرتبطة واحدة تحتوي على سمات تشير إلى العقدة التالية*/class node {object data ؛ // Data Object Node next ؛ // NEXT NODE NODE (Object D) {this.data = d ؛ } node (object d ، node n) {this.data = d ؛ this.next = n ؛ } الكائن العام getData () {return data ؛ } public void setData (بيانات الكائن) {this.data = data ؛ } العقدة العامة getNext () {return next ؛ } public void setNext (node next) {this.next = next ؛ }. // الرأس الجديد بعد عقدة الانعكاس q = الرأس ؛ // نتيجة التناوب: 012،123،234 ، ...... 10 null null بينما (head.next! = null) {p = head.next ؛ // يتم استبدال الأول بالثاني ، ثم يمثل p head.next = p.next ؛ // يتم استبدال الثانية بالثالث ، والآخر الذي وصلت بالفعل إلى المركز الأول سيصبح الأول ، وسيصبح الأول الأول ؛ // يتم استبدال واحد جديد بالآخر} إرجاع p ؛ } // method 2 head لا يعيد تعيين العقدة الثابتة العكسي 2 (رأس العقدة) {// نقطة مؤشر العقدة الوسيطة إلى العقدة السابقة ، لا يزال بإمكانك الاستمرار في اجتياز القائمة المرتبطة بالعقدة الخلفية المرتبطة p1 = head ، p2 = head.next ، p3 ؛ // الأمامي والوسط والخلف/التناوب نتيجة: 012 ، 123 ، 234 ، 345 ، 456 .... 9 10 NULL بينما (p2! = null) {p3 = p2.next ؛ p2.next = p1 ؛ // أشر إلى الوراء وأشار إلى الأمام p1 = p2 ؛ // 2 ، 3 يتحرك إلى الأمام p2 = p3 ؛ } head.next = null ؛ // لم يتغير الرأس. عندما يصل الإخراج إلى 0 ، اطلب 0.next إلى 1 إرجاع P1 ؛ }}