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

واروخوانه لیست پیوندی در جاوا (Palindrome Linked List)

واروخوانه لیست پیوندی در جاوا

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

  1. آشنایی با لیست پیوندی
  2. آشنایی با متد
  3. آشنایی با if
  4. آشنایی با while
  5. آشنایی با generic
  6. آشنایی با شی گرایی
  7. آشنایی با constructor
  8. آشنایی با this
  9. آشنایی با palindrome

در این آموزش از تمام موارد بالا استفاده شده است و موارد مهمی که حتما باید بدانید شماره های 1،2،3،4 است که در این قسمت استفاده شده است.

واروخوانه

قلب مستوی یا جناس قلب، همچنین شناخته شده با نام واروخوانه که معادل فارسی ایست برای پالیندروم (Palindrome) به واژه، جمله، عدد یا هر چیز دیگری گفته می‌شود که خواندن آن از چپ به راست یا از راست به چپ کاملاً یکسان باشد. به‌عنوان مثال عدد ۱۵۳۴۳۵۱ یک عدد واروخوانه است، یا واژه «Malayalam» که نام یکی از زبانهای محلی جنوب غربی هندوستان است ویا واژه «داد» از این قاعده پیروی می‌کنند(ویکیپدیا).

واروخوانه لیست پیوندی در جاوا

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

پیش نیاز واروخوانه لیست پیوندی در جاوا

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

import java.util.Iterator;

public class SingleLinkedList<Item> {

     private Node<Item> first;
     private int size;

     public SingleLinkedList() {
          size = 0;
          first = null;
     }

     public boolean isEmpty() {
          return first == null;
     }

     public int size() {
          return size;
     }

     public void add(Item item) {
          Node<Item> oldfirst = first;
          first = new Node<Item>(item, oldfirst);
          size++;
     }

     public Iterator<Item> iterator() {
          return new ListIterator<Item>(first);
     }

}

public class Node<Item> {

     private Item data;
     private Node next_node;

     public Node(Item data, Node next_node) {
          this.data = data;
          this.next_node = next_node;
     }

     public Item getData() {
          return data;
     }

     public Node getNext_node() {
          return next_node;
     }



}

public class ListIterator<Item> implements Iterator<Item> {
     private Node<Item> current;

     public ListIterator(Node<Item> first) {
          current = first;
     }

     public boolean hasNext() {
          return current != null;
     }


     public Item next() {
          if (!hasNext())
              throw new NoSuchElementException();
          Item item = current.getData();
          current = current.getNext_node();
          return item;
     }
}

پیاده سازی واروخوانه لیست پیوندی در جاوا

پیاده سازی واروخوانه لیست پیوندی را از روش لیست پیوندی معکوس استفاده میکنیم. بدین معنی که ابتدا یک لیست پیوندی معکوس با استفاده از لیست پیوندی اصلی میسازیم و سپس عناصر این دو لیست را با هم مقایسه میکنیم اگر با هم برابر بودند متد واروخانه لیست پیوندی در جاوا مقدار true برمیگرداند در غیر این صورت false برمیگرداند. کد آن به صورت زیر است(متد زیر در کلاس SingleLinkedList قرار میدهیم):

   public boolean isPalindrome() {
          Node head = first;
          Node prev = new Node<Item>(first.getData(), null);

          while (head.getNext_node() != null) {
              Node temp = new Node<Item>((Item) head.getNext_node().getData(), prev);
              prev = temp;
              head = head.getNext_node();
          }

          head = first;
          Node reverse = prev;
          while (head != null) {
              if (reverse.getData() != head.getData()) {
                   return false;
              }
              head=head.getNext_node();
              reverse = reverse.getNext_node();
          }
          return true;
     }

در کد بالا یک while نوشتیم برای ساخت لیست معکوس(منظور while اول است).در while دوم عناصر دو لیست را با هم بررسی میکنیم.

تست واروخوانه لیست پیوندی در جاوا

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

 public static void main(String[] args) {
          SingleLinkedList<Integer> list = new SingleLinkedList<>();

          list.add(1);
          list.add(2);
          list.add(1);
          list.add(2);
          list.add(1);

          System.out.println("is list palindrome? "+ list.isPalindrome());

     }

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

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

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