מבנה נתונים של רשימה מקושרת ב-Java

מבני נתונים שונים נוצרים למטרות שונות. אולי אתה יודע על ArrayList (אם עדיין לא, אנו ממליצים לך לקרוא על זה קודם). במאמר זה, אנו הולכים ללמוד על LinkedList ולהבין למה האוסף הזה טוב. אם תסתכל על מקור קוד הכיתה של LinkedList Java 8 (או גרסה מאוחרת יותר של השפה) (באתר אורקל או ב-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() ללא פרמטרים משמש לבניית רשימה ריקה.
• >LinkedList(Collection<? extends E> c) מיועדת ליצירת רשימה המכילה את האלמנטים של האוסף שצוין, לפי הסדר שהם יוחזרו על ידי האיטרטור של האוסף.

הצהרת LinkedList

למעשה, רשימה מקושרת (Java או בכל שפה אחרת) מורכבת מרצף של צמתים. כל צומת נועד לאחסן אובייקט מסוג שהוגדר בעת היצירה. אז כדי ליצור LinkedList , קוד Java הוא הבא:

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

יש לנו מטרה לשמור רצף של מספרים שלמים וקישורים לשכנים. עם זאת, הוא ריק כרגע.

LinkedList פעולות עיקריות

כרגיל, במקרה של Collections אתה יכול להכניס אלמנטים ל- LinkedList (לקצהו או לאמצע), להסיר משם ולקבל אלמנט לפי אינדקס. אז הנה הם:

• add(E element) מוסיף את האלמנט שצוין לסוף רשימה זו;
• add(int index, E element) הוספת האלמנט באינדקס המיקום שצוין ;
• get(int index) מחזירה את האלמנט במיקום שצוין ברשימה זו;
• remove(int index) מסיר את האלמנט שנמצא באינדקס המיקום;
• remove(Object o) מסיר את המופע הראשון של ? o אלמנט מהרשימה הזו אם הוא קיים.
• remove() מאחזר ומסיר את האלמנט הראשון ברשימה.

יישום רשימה מקושרת ב-Java, הוספה והסרה של אלמנטים. דוגמא

בוא ננסה את הפעולות האלה על תרגול. ראשית, יישום Java 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 הוא חלק ממסגרת האוסף , אתה יכול להשתמש באיטרטור כדי להסיר אלמנטים, כמו גם איטרטור מיוחד לרשימות - ListIterator . אפילו יותר, פעולות עם איטרטור מספקות את היתרונות העיקריים של מחלקה LinkedList : ביצועים טובים של פעולות הוספה/מחיקה. באמצעות Iterator אתה עשוי לקבל זמן קבוע עבורם. בהמשך מאמר זה, נכתוב דוגמה לקוד כדי להשוות בין ArrayList לבין LinkedList+Iterator

• Iterator.remove() מסיר את האלמנט האחרון שהוחזר על ידי איטרטור זה.
• ListIterator.add(E element) מוסיף אלמנט לרשימה

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() מסיר את כל הרכיבים מהרשימה
• contains(Object o) מחזירה true אם הרשימה מכילה את האלמנט o.
• indexOf(Object o) מחזיר את האינדקס של ההופעה הראשונה של אלמנט o, או -1 אם הוא לא ברשימה.
• set(int index, E element) מחליף את האלמנט במיקום האינדקס באלמנט
• size()מחזיר את כמות האלמנטים ברשימה.
• toArray() מחזיר מערך המכיל את כל האלמנטים של הרשימה מהאלמנט הראשון ועד האחרון.

אגב, בהיותו תור בגודל שני, ל-LinkedList ב-Java יש פעולות ספציפיות לחסימה:

• pop() שמקפיץ אלמנט מהמחסנית (מיוצג על ידי הרשימה)
• push(E e) שדוחף אלמנט אל הערימה (מיוצג על ידי רשימה זו)

כיצד להפוך LinkedList: דוגמה

הנה דוגמה קטנה, משימה פופולרית אך קלה למתחילים. יש לנו LinkedList וצריך להפוך אותה. האלגוריתם הקל ביותר הוא לעבור על ה- LinkedList בסדר הפוך ולהכניס כל אלמנט לחדש. עם זאת, אולי תמצא דרך טובה יותר? להלן הקוד של תוכנית Java ברשימה מקושרת הפוכה:

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 הוא היישום הפופולרי ביותר של List . אתה בהחלט צריך להשתמש ב-ArrayList כאשר הגישה לאינדקס היא בעדיפות מכיוון שפעולות אלו מבוצעות בזמן קבוע. הוספה לסוף הרשימה בממוצע נעשית גם היא בזמן קבוע. יתרה מכך, ל- ArrayList אין עלויות נוספות עבור אחסון חבורה של אלמנטים. אתה יכול לספור כחסרונות את מהירות פעולות ההכנסה וההסרה כאשר היא נעשית לא בסוף הרשימה. LinkedList שימושי יותר במקרה של ביצועי פעולות הוספה ומחיקה במובנים מסוימים: אם אתה משתמש באיטרטורים זה מתרחש בזמן קבוע. פעולות גישה לפי אינדקס מבוצעות על ידי חיפוש מתחילת הסוף (מה שקרוב מביניהם) לאלמנט הרצוי. עם זאת, אל תשכח עלויות נוספות עבור אחסון הפניות בין אלמנטים. אז הנה פעולות LinkedList ו- ArrayList סטנדרטיות עם זמני ריצה אלגוריתמיים. N מתייחס למספר הפריטים שכבר נמצאים ברשימה. O(N) פירושו שבמקרה הגרוע עלינו "לעבור" על כל הרשימה עד שנמצא המיקום הדרוש, למשל, להכנסת האלמנט החדש לרשימה. O(1) פירושו שהפעולה מתרחשת בזמן קבוע, ללא תלות במספר הפריטים.

מורכבות זמן של LinkedList

מורכבות זמן ArrayList

מתי להשתמש ב-LinkedList: דוגמה

בהחלט, ArrayList הוא היישום הפופולרי ביותר של List . עם זאת, אתה עלול לפגוש את המצבים שבהם יש צורך בפעולות ההוספה/הסרה לעתים קרובות מדי. במקרה כזה, 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

אין רשימה מקושרת יחידה בין האוסף הקלאסי בג'אווה, רשימה מקושרת יחידה היא מבנה שבו כל צומת מכיל אובייקט והפניה לצומת הבא, אך לא עבור הצומת הקודם. Java LinkedList היא דו-קישורית, אבל אף אחד לא מפריע לך ליצור מבנה נתונים משלך, כגון Singly ,code>Linked List. להלן מספר שלבים לפתרון המשימות הללו:

1. צור מחלקת Node עם שתי תכונות, נתונים והבא. הבא הוא הפניה לצומת הבא.
2. צור מחלקה FirstLast עם שתי תכונות, ראש וזנב.
3. צור שיטה add() כדי להוסיף צומת חדש לרשימה. בדוק אם הרשימה ריקה תחילה ( head == null ). אם כן, ראש וזנב מתייחסים לצומת החדש. אם הרשימה לא ריקה, הצומת החדש יתווסף לסוף, כך שהתכונה הבאה של הזנב מתייחסת לצומת שנוסף והצומת החדש הופך לזנב הרשימה.

אגב, אתה יכול לנסות ליצור LinkedList משלך כתרגיל. בהצלחה בלימודך.