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

ساختارهای داده های مختلف برای اهداف مختلف ایجاد می شوند. شما ممکن است در مورد ArrayList بدانید (اگر هنوز نمی دانید، توصیه می کنیم ابتدا در مورد آن مطالعه کنید). در این مقاله قصد داریم با LinkedList آشنا شویم و متوجه شویم این مجموعه برای چه کاری مفید است. اگر به منبع کد کلاس LinkedList Java 8 (یا نسخه جدیدتر زبان) (در وب سایت Oracle یا IDE خود، در مورد IDEA: crtl+B در نام کلاس) نگاه کنید، اعلان بعدی را خواهید دید:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

در حال حاضر مهمترین اطلاعات از کد این واقعیت است که LinkedList رابط های List و Deque را پیاده سازی می کند . رابط List توالی افزودن آیتم ها را حفظ می کند و امکان دسترسی به آیتم بر اساس فهرست را فراهم می کند. صف "معمولی" از افزودن عناصر به انتها و استخراج آنها از ابتدا پشتیبانی می کند. Deque یک صف دو طرفه است و از افزودن و حذف عناصر از هر دو طرف پشتیبانی می کند. ممکن است آن را ترکیبی از پشته و صف در نظر بگیرید. بنابراین، LinkedList پیاده‌سازی این دو است و به ما اجازه می‌دهد یک صف دو طرفه متشکل از هر شیء از جمله null ایجاد کنیم. LinkedList مجموعه ای از عناصر است. ما می توانیم آن را در منبع کد کلاس مشاهده کنیم، این بار به فیلدها توجه کنید:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

هر عنصر، معمولاً آن را Node می نامیم ، حاوی یک شی و ارجاع به دو شیء همسایه - قبلی و بعدی است. از این رو از نظر استفاده از حافظه چندان موثر نیست. از آنجایی که LinkedList در واقع یک ساختار دو طرفه است، ما به راحتی می توانیم عناصر را از هر دو طرف اضافه یا حذف کنیم.

سازنده های لینکدلیست

با بازگشت به منبع کد، می‌توانیم متوجه شویم که LinkedList دو سازنده دارد

• LinkedList() بدون پارامتر برای ساخت یک لیست خالی استفاده می شود.
• >LinkedList(Collection<? extensions E> c) برای ایجاد لیستی است که حاوی عناصر مجموعه مشخص شده است، به ترتیب آنها توسط تکرار کننده مجموعه برگردانده می شوند.

اعلامیه LinkedList

در واقع، یک لیست پیوندی (جاوا یا به هر زبان دیگر) از دنباله ای از گره ها تشکیل شده است. هر گره برای ذخیره یک شی از یک نوع تعریف شده در هنگام ایجاد طراحی شده است. بنابراین برای ایجاد LinkedList ، کد جاوا به صورت زیر است:

LinkedList<Integer> myList = new LinkedList<>();

ما یک شی داریم که دنباله ای از اعداد صحیح و پیوندها را به همسایگان نگه می دارد. با این حال، در حال حاضر خالی است.

عملیات اصلی LinkedList

طبق معمول، در مورد مجموعه‌ها، می‌توانید عناصر را در LinkedList (تا آخر یا وسط آن) قرار دهید، از آنجا حذف کنید و یک عنصر را به فهرست دریافت کنید. بنابراین در اینجا آنها هستند:

• add(E element) عنصر مشخص شده را به انتهای این لیست اضافه می کند.
• add(int index, E element) عنصر را در نمایه موقعیت مشخص شده درج می کند .
• get(int index) عنصر را در موقعیت مشخص شده در این لیست برمی گرداند.
• remove(int index) عنصری را که در شاخص موقعیت قرار دارد حذف می کند.
• remove(Object o) اولین رخداد ? اگر عنصر o از این لیست وجود داشته باشد.
• remove() اولین عنصر لیست را بازیابی و حذف می کند.

پیاده سازی لیست پیوندی در جاوا، افزودن و حذف عناصر. مثال

بیایید این عملیات را در عمل امتحان کنیم. اول، اجرای LinkedList جاوا: ایجاد یک LinkedList از رشته ها، اضافه کردن 3 عنصر به آنجا. سپس یکی را بردارید، سپس یکی را از وسط اضافه کنید.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

نتیجه اجرای این برنامه:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList بخشی از چارچوب مجموعه است، می‌توانید از Iterator برای حذف عناصر و همچنین یک تکرارکننده ویژه برای لیست‌ها استفاده کنید - ListIterator . حتی بیشتر، عملیات با iterator مزایای اصلی کلاس LinkedList را ارائه می دهد : عملکرد خوب عملیات درج/حذف. با استفاده از Iterator ممکن است یک زمان ثابت برای آنها دریافت کنید. در ادامه این مقاله، یک مثال کد برای مقایسه ArrayList و LinkedList+Iterator خواهیم نوشت.

• Iterator.remove() آخرین عنصر بازگشتی توسط این تکرارکننده را حذف می کند.
• ListIterator.add(E عنصر) یک عنصر را در لیست قرار می دهد

Java LinkedList مثال: Iterator چگونه کار می کند

در اینجا ما یک کد نمونه کوچک Java LinkedList داریم که سعی می کنیم آن را از طریق Iterator اضافه و حذف کنیم.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);

       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);

   }
}

نتیجه اجرای این برنامه:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

عملیات بیشتر Java LinkedList :

• addFirst() ، addLast() یک عنصر را به ابتدا/پایان لیست اضافه می کنند
• clear() تمام عناصر را از لیست حذف می کند
• contain(Object o) اگر لیست حاوی عنصر o باشد مقدار true را برمی گرداند.
• indexOf(Object o) اندیس اولین رخداد عنصر o یا -1 را اگر در لیست نباشد برمی گرداند.
• set (int index، عنصر E) عنصر را در موقعیت شاخص با عنصر جایگزین می کند
• size() تعداد عناصر موجود در لیست را برمی گرداند.
• ()toArray آرایه ای را برمی گرداند که شامل تمام عناصر لیست از اول تا آخرین عنصر است.

BTW یک صف دو اندازه است، LinkedList در جاوا دارای عملیات خاصی است:

• pop() که عنصری را از پشته بیرون می آورد (که توسط لیست نشان داده می شود)
• push(E e) که یک عنصر را روی پشته هل می دهد (که توسط این لیست ارائه می شود)

نحوه معکوس کردن LinkedList: مثال

در اینجا یک مثال کوچک، یک کار محبوب و در عین حال آسان برای مبتدیان آورده شده است. ما یک LinkedList داریم و باید آن را معکوس کنیم. ساده ترین الگوریتم این است که از LinkedList به ترتیب معکوس عبور کنید و هر عنصر را در عنصر جدید قرار دهید. با این حال، شاید شما راه بهتری پیدا کنید؟ در اینجا کد برنامه جاوا لیست پیوند معکوس آمده است:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

نتیجه:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList در مقابل ArrayList: چه زمانی از اولین مورد استفاده کنیم

LinkedList و ArrayList هر دو پیاده سازی رابط List هستند . LinkedList آن را با یک لیست دارای پیوند دوگانه پیاده سازی می کند. ArrayList آن را با استفاده از یک آرایه تغییر اندازه پویا پیاده سازی می کند. همانطور که می دانید، هر گره LinkedList حاوی آبجکت ها و دو مرجع به همسایگان است. این به معنای هزینه های اضافی حافظه برای ذخیره مراجع بین عناصر در مورد Java LinkedList است . ArrayList آن را با یک آرایه تغییر اندازه پویا پیاده سازی می کند. برخی از عملیات LinkedList و ArrayList یکسان به نظر می رسند، اما به روشی متفاوت عمل می کنند. در مورد ArrayList ، شما با آرایه های داخلی دستکاری می کنید، در LinkedList - با ارجاعات. ArrayList محبوب ترین پیاده سازی لیست است . شما قطعاً باید از ArrayList در زمانی که دسترسی به فهرست در اولویت است استفاده کنید زیرا این عملیات در زمان ثابت انجام می شود. افزودن به انتهای لیست به طور متوسط ​​نیز در زمان ثابت انجام می شود. حتی بیشتر، ArrayList هزینه های اضافی برای ذخیره یک دسته از عناصر ندارد. شما ممکن است سرعت درج و حذف عملیات را زمانی که در انتهای لیست انجام نشده است، به عنوان منفی در نظر بگیرید. LinkedList در مورد عملکرد عملیات درج و حذف از برخی جهات مفیدتر است: اگر از تکرار کننده استفاده کنید در زمان ثابتی رخ می دهد. عملیات دسترسی بر اساس شاخص با جستجو از ابتدای انتهای (هر کدام نزدیکتر) به عنصر مورد نظر انجام می شود. با این حال، در مورد هزینه های اضافی برای ذخیره مراجع بین عناصر فراموش نکنید. بنابراین در اینجا عملیات استاندارد LinkedList و ArrayList با زمان اجرا الگوریتمی انجام می شود. N به تعداد مواردی که قبلاً در لیست هستند اشاره دارد. O(N) به این معنی است که در بدترین حالت باید در کل لیست "راه برویم" تا زمانی که موقعیت مورد نیاز پیدا شود، به عنوان مثال، برای درج عنصر جدید در لیست. O(1) به این معنی است که عملیات در زمان ثابت و مستقل از تعداد آیتم ها انجام می شود.

پیچیدگی زمانی LinkedList

پیچیدگی زمانی ArrayList

زمان استفاده از LinkedList: مثال

قطعا ArrayList محبوب ترین پیاده سازی لیست است . با این حال، ممکن است با شرایطی روبرو شوید که عملیات افزودن/حذف اغلب اوقات مورد نیاز است. در این صورت، LinkedList به همراه Iterator می تواند مفید باشد. به عنوان مثال. ما یک لیست طولانی داریم و باید هر عنصر را از این لیست حذف کنیم. بیایید این کار را با ArrayList و LinkedList + Iterator انجام دهیم . ما زمان هر عملیات را مقایسه می کنیم و آن را در کنسول چاپ می کنیم. اینجا کد:

import java.util.*;
import java.util.function.BiPredicate;

public class ListTest2 {

   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());

       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }

   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);

           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }

   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }

   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

نتیجه برای ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

نتیجه برای LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

همانطور که می بینید در این مورد LinkedList بسیار موثرتر است. اجازه دهید صادقانه باشد. در توسعه نرم افزار واقعی، استفاده از LinkedList نوعی رویداد نادر است. با این وجود، یک متخصص باید در مورد وجود این ساختار داده و مزایای آن بداند. اگر در کد واقعی LinkedList یک مهمان نادر است، در مصاحبه های Java Junior بسیار محبوب است. و با این حال، در اینجا چیزی است که جاشوا بلوخ در مورد LinkedList نوشت :

AddOn: جاوا لیست پیوندی منفرد

در میان مجموعه های کلاسیک در جاوا لیست پیوندی منفرد وجود ندارد ، لیست پیوندی منفرد ساختاری است که در آن هر گره حاوی یک شی و ارجاع به گره بعدی است، اما نه برای گره قبلی. Java LinkedList دو پیوندی است، اما هیچکس برای ایجاد ساختار داده خود، مانند Singly,code>Linked List، با شما دخالت نمی کند. در اینجا چند مرحله برای حل این وظایف وجود دارد:

1. یک کلاس Node با دو ویژگی داده و next ایجاد کنید. بعد ارجاع به گره بعدی است.
2. کلاس FirstLast را با دو ویژگی head و tail ایجاد کنید .
3. یک متد add() برای افزودن یک گره جدید به لیست ایجاد کنید. ابتدا بررسی کنید که آیا لیست خالی است ( head == null ). اگر چنین است، سر و دم به گره جدید مراجعه کنید. اگر لیست خالی نباشد، گره جدید به انتها اضافه می شود، بنابراین ویژگی بعدی دنباله به گره اضافه شده اشاره دارد و گره جدید به دنباله لیست تبدیل می شود.

به هر حال ممکن است سعی کنید LinkedList خود را نیز به عنوان تمرین ایجاد کنید. در یادگیری موفق باشید