linked list in java

لیست پیوندی در جاوا (linked list)

در این آموزش به توضیح و پیاده سازی لیست پیوندی می پردازیم. پیش نیازهای این آموزش:

  1. مفهوم Class
  2. Generic
  3. iterator

لیست پیوندی( LinkedList)

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

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

single linked list

در لیست  نود آخر همیشه ارجاع آن null است(البته در single linkedlist). نود اول را در لیست پیوندی head میگویند و ارجاع آن نگه داشته میشود.همان طور که گفته شد لیست پیوندی تعداد ثابتی نود ندارد و کاملا پویا است و به راحتی با داده های ما طول لیست اضافه و کم میشود. یکی از ایردهای لیست پیوندی نسبت به آرایه این است که اجازه دسترسی مستقیم به نود خاصی را نمی دهد پس برای دسترسی به یک نود خاص باید کل لیست به دنبال آن بگردیم.

انواع لیست

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

  1. Single linked list: هر نود شامل یک داده و یک ارجاع به نود بعدی هستند.
  2. Double linked List: هر نود علاوه بر ارجاع به نود بعدی، ارجاع به نود قبل هم دارند.
  3. Circular linked list: کاملا شبیه به single linked list هست فقط نود آخر ارجاعش به نود اول است.

انواع لیست پیوندی

پیاده سازی

این قسمت به پیاده سازی Single linked list پرداخته می شود.پیاده سازی لیست های پیوندی به صورت های مختفی است. ما یکی از آنها را بیان می کنیم. اول یک کلاس به نام Node نیاز داریم.در این کلاس یک data وجود دارد و یک next_node که به ترتیب به داده و نود بعدی اشاره می کنند.

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;

     }

}

 

 

مرحله بعد پیاده سازی خود لیست است. تا الان فقط نود را ساختیم.کلاس SingeLinkedList میسازیم که شامل :

  1. First: اولین عنصر لیست
  2. Size: سایز لیست ما
  3. ()Size: متدی که سایز لیست به ما میدهد
  4. ()Iterator: متدی که یک iterator برای لیست ما بر میگرداند.
  5. ()isEmpty: متدی که خالی بودن لیست را به میگوید
  6. ()Add: متدی که یک نود به خانه های لیست ما اضافه می کند.

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);

     }

}

کلاس ListIterator هم یک Iterator است برای SingleLinkedList

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;

     }

}

در آخر هم یک Main برای برنامه مینویسیم.

     public static void main(String[] args) {

          SingleLinkedList<String> list = new SingleLinkedList<String>();

          list.add(“apple”);

          list.add(“orange”);

          list.add(“banana”);

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

              String fruit = (String) iterator.next();

              System.out.println(fruit);

          }

    }

لینک های کمکی :

  1. آموزش لیست
  2. پیاده سازی لیست

یک دیدگاه برای “لیست پیوندی در جاوا (linked list)

پاسخ دهید

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