java, جاوا, ساختمان داده در جاوا

ادغام دو لیست پیوندی مرتب در جاوا (Merge Sorted LinkedList)

ادغام دو لیست پیوندی مرتب در جاوا

در این جلسه تیم کدگیت را با آموزش ادغام دو لیست پیوندی مرتب در جاوا همراهی کنید. پیش نیاز این آموزش شامل موارد زیر است:

  1. آشنایی با لیست پیوندی
  2. آشنایی با متد
  3. آشنایی با انواع For (منظور enhance for است)
  4. آشنایی با while
  5. آشنایی با if
  6. آشنایی با generic

لیست پیوندی

یکی از مشکلاتی که آرایه دارد ساختار و طول ثابت آن است بنابراین نمیتوان براحتی ساختار آن را طوری تغییر داد که با داده های(اطلاعات) ما همخوانی داشته باشد. همچنین آرایه هزینه insert و delete آن بالا است.

لیست پیوندی یک داده ساختار خطی است که بر خلاف آرایه طول آن میتواند تغییر کند و فضای اضافی را اشغال نکند. در لیست پیوندی هر عنصر یک Object (شی) جداگانه است. هر عنصر در لیست دو بخش دارد 1.داده (اطلاعات) 2. ارجاع(refrence) به شی(Object) بعدی.

الگوریتم ادغام دو لیست پیوندی مرتب در جاوا

در آموزش های قبل در مورد پیاده سازی لیست پیوندی صحبت شد.در آن لیست پیوندی پیاده سازی شده هر عنصر به اول لیست اضافه میشد.(دقیقا شبیه به پشته). ما از همان لیست پیاده سازی شده استفاده میکنیم و در الگوریتم خود به کار میبریم. دقت داشته باشید که آخرین عنصر ما در لیست پیوندی اولین عنصری است که وارد کردیم!!

الگوریتم ادغام دو لیست پیوندی مرتب در جاوا بدین صورت است که ما عناصر اول هر لیست را میگیریم. داده های این عناصر را مقایسه میکنیم و هر کدام کوچکتر بود را در لیست جدیدی میریزیم و به خانه بعدی آن لیست میرویم. آنقدر این کار را تکرار میکنیم تا هر دو لیست کامل بررسی شده باشند.

پیاده سازی ادغام دو لیست پیوندی مرتب در جاوا

کد ادغام دو لیست در جاوا به صورت زیر است:

     public static SingleLinkedList<Integer> mergeList(Node list1, Node list2) {
          SingleLinkedList<Integer> mergelist = new SingleLinkedList<>();

          while (list1 != null || list2 != null) {
              if (list1 != null && list2 != null) {
                   if ((Integer) list1.getData() < (Integer) list2.getData()) {
                        mergelist.add((Integer) list1.getData());
                        list1 = list1.getNext_node();
                    } else {
                        mergelist.add((Integer) list2.getData());
                        list2 = list2.getNext_node();
                   }
              } else if (list1 == null) {
                   mergelist.add((Integer) list2.getData());
                   list2 = list2.getNext_node();
              } else if (list2 == null) {
                   mergelist.add((Integer) list1.getData());
                   list1 = list1.getNext_node();
              }

          }

          return mergelist;
     }

در کد بالا ما متدی به نام mergelist تعریف کردیم. این متد دو ورودی میگیرد. هر کدام از ورودی ها عناصر اول هر لیست هستند. سپس یک while نوشتیم که تا موقعی که لیست های ما خالی نباشند کار ادغام را انجام دهد. درون while ما سه شرط را بررسی کردیم:

  1. لیست اول و دوم خالی نباشند. در این صورت باید عنصر کوچکتر را انتخاب کرد
  2. لیست اول خالی باشد. عنصر لیست دوم را وارد لیست پیوندی ادغام میکنیم.
  3. لیست دوم خالی باشد. عنصر لیست اول را وارد لیست پیوندی ادغام میکنیم

تست ادغام دو لیست مرتب در جاوا

برای تست کدهای بالا، کد main زیر را بزنید:

   SingleLinkedList<Integer> list1 = new SingleLinkedList<>();

          list1.add(6);
          list1.add(5);
          list1.add(2);

          SingleLinkedList<Integer> list2 = new SingleLinkedList<>();

          list2.add(4);
          list2.add(3);
          list2.add(1);

          SingleLinkedList<Integer> merging = mergeList(list1.getFirst(),
                   list2.getFirst());

          for (Iterator iterator = merging.iterator(); iterator.hasNext();) {

              System.out.println((Integer) iterator.next());
          }

     }

در کد بالا دو لیست پیوندی ساختیم و آنها را ادغام کردیم و در آخر لیست ادغام شده را نمایش دادیم. خروجی به صورت زیر است:

6
5
4
3
2
1

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *