Java LinkedList

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

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

פלט: [שלום עולם! שמי ארל, אני אוהב את ג'אווה, אני גר בקנדה] כך נראית הרשימה שלנו: בוא נראה איך מוסיפים אלמנט חדש. זה נעשה באמצעות שיטת add() .

earlBio.add(str2);

בנקודה בקוד, הרשימה שלנו מורכבת מאלמנט אחד: String str1 . בואו נראה מה קורה בהמשך בתמונה: כתוצאה מכך, str2 ו- str1 הופכים מקושרים דרך הקישורים הבאים והקודמים המאוחסנים בצמתים זה של הרשימה: כעת עליכם להבין את הרעיון המרכזי של רשימה מקושרת כפולה. שרשרת הקישורים הזו היא בדיוק מה שהופך את רכיבי LinkedList לרשימה אחת. שלא כמו ArrayList , ל-LinkedList אין מערך או משהו דמוי מערך בפנים. כל עבודה (טוב, רוב) עם ArrayList מסתכמת בעבודה עם המערך הפנימי. כל עבודה עם Java LinkedList מסתכמת בשינוי קישורים. ניתן לראות זאת בבהירות רבה על ידי הוספת אלמנט לאמצע הרשימה:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

כפי שאתה יכול לראות, שיטת add() העמוסה מאפשרת לך לציין אינדקס ספציפי עבור פריט חדש. במקרה זה, אנו רוצים להוסיף String str2 בין str1 ל- str3 . זה מה שיקרה פנימית: לאחר שינוי הקישורים הפנימיים, str2 נוסף בהצלחה לרשימה: כעת כל 3 האלמנטים מחוברים. ניתן לעבור דרך הקישור הבא מהאלמנט הראשון בשרשרת אל האחרון וחוזר חלילה. אז, אנחנו די נוחים עם ההכנסה, אבל מה לגבי הסרת אלמנטים? העיקרון זהה לחלוטין. אנו רק מעדכנים את הקישורים בשני האלמנטים "משמאל וימין" של האלמנט המוסר:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

זה מה שקורה אם נמחק את הפריט עם אינדקס 1 (הוא באמצע הרשימה): לאחר עדכון הקישורים נקבל את התוצאה הרצויה: בניגוד לפעולת ההסרה ב- ArrayList , כאן אין צורך להזיז רכיבי מערך או לעשות כל דבר מהסוג. אנחנו רק מעדכנים את הקישורים עבור str1 ו- str3 . כעת הם מצביעים זה על זה, ו- str2 " נשר " משרשרת הקישורים ואינו עוד חלק מהרשימה.

סקירה כללית של שיטות

ל-LinkedList יש הרבה שיטות משותפות עם ArrayList . לדוגמה, לשתי המחלקות יש שיטות כגון add() , remove() , indexOf() , clear() , contains() (מציין אם פריט נמצא ברשימה), set() (מחליף אלמנט קיים), וכן גודל() . למרות שרבים מהם פועלים באופן שונה באופן פנימי (כפי שמצאנו עם add() ו- remove() ), התוצאה הסופית זהה. עם זאת, ל-LinkedList יש שיטות נפרדות לעבודה עם ההתחלה והסוף של הרשימה, שאין ל- ArrayList :

• addFirst() , addLast() : שיטות אלו להוספת אלמנט לתחילת/סוף הרשימה

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

פלט: [מכונית{model='Ferrari 360 Spider'}, רכב{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] [Car{model='Ford Mondeo'}, Car{model=' פרארי 360 ספיידר'}, רכב{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] אנחנו מסיימים עם "פורד" בראש הרשימה, ו"פיאט" בסוף.

• peekFirst() , peekLast() : המתודות מחזירות את האלמנט הראשון/אחרון ברשימה. הם מחזירים null אם הרשימה ריקה.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

פלט: מכונית{model='Ferrari 360 Spider'} מכונית{model='Lamborghini Diablo'}

• pollFirst() , pollLast() : שיטות אלו מחזירות את האלמנט הראשון/אחרון ברשימה ומסירות אותו מהרשימה. הם מחזירים null אם הרשימה ריקה

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

פלט: מכונית{model='Ferrari 360 Spider'} מכונית{model='Lamborghini Diablo'} מה נשאר ברשימה? [מכונית{model='Bugatti Veyron'}]

• toArray() : שיטה זו מחזירה מערך המכיל את פריטי הרשימה

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

פלט: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] עכשיו אנחנו יודעים איך LinkedList עובד ובמה הארגון שלה שונה מ- ArrayList . מהם היתרונות של השימוש ב-LinkedList ? מעל הכל, אנחנו מרוויחים כשעובדים באמצע הרשימה. פעולות הכנסה והסרה באמצע LinkedList הן הרבה יותר פשוטות מאשר ב- ArrayList . אנחנו פשוט מעדכנים את הקישורים של אלמנטים שכנים, והאלמנט הלא רצוי "נושר" משרשרת הקישורים. אבל ב- ArrayList , אנחנו חייבים

• בדוק אם יש מספיק מקום (בעת הכנסת)
• אם לא, אז אנחנו יוצרים מערך חדש ומעתיקים את הנתונים לשם (בעת ההוספה)
• אנחנו מסירים/מכניסים את האלמנט, ומעבירים את כל שאר האלמנטים ימינה/שמאלה (בהתאם לסוג הפעולה). והמורכבות של תהליך זה תלויה במידה רבה בגודל הרשימה. זה דבר אחד להעתיק/להזיז 10 אלמנטים, ודבר אחר לגמרי לעשות את אותו הדבר עם מיליון אלמנטים.

במילים אחרות, אם פעולות הכנסה/הסרה באמצע הרשימה הן הנפוצות ביותר בתוכנית שלך, LinkedList צריכה להיות מהירה יותר מ- ArrayList .

בתיאוריה

public class Main {

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

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

פלט: זמן שנלקח על ידי LinkedList (במילישניות) = 1873

public class Main {

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

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

פלט: הזמן שלוקח ArrayList (במילישניות) = 181 זה היה בלתי צפוי! ביצענו פעולה שבה LinkedList צריכה להיות הרבה יותר יעילה: הכנסת 100 פריטים באמצע רשימה. והרשימה שלנו ענקית: 5,000,000 אלמנטים. ArrayList היה צריך להעביר כמה מיליון פריטים עם כל הכנסה! איך זה זכה? ראשית, הזמן הנדרש עבור ArrayList לגשת לאלמנטים קבוע (קבוע). כשאתה כותב

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

אז ArrayList [2_000_000] היא כתובת זיכרון ספציפית (אחרי הכל, לרשימה יש מערך פנימי). אבל, ל- LinkedList אין מערך. הוא יחפש אלמנט מספר 2_000_000 לאורך שרשרת הקישורים. עבור LinkedList, זו לא כתובת זיכרון, אלא קישור שעדיין צריך להגיע אליו: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. הבא.הבא.הבא.הבא.הבא.הבא.הבא.הבא _ , ArrayList כבר יודע את כתובת הזיכרון המדויקת שיש לגשת אליה, אבל LinkedList עדיין צריך "להגיע לשם". שנית, יש את המבנה של ArrayList עצמו. פונקציה פנימית מיוחדת ( System.arrayCopy() ) מרחיבה את המערך הפנימי, ומעתיקה ומזיזה את כל האלמנטים. זה מהיר מאוד, מכיוון שהוא מותאם לעבודה ספציפית זו. אבל כאשר אתה לא צריך "להגיע" לאינדקס מסוים, LinkedList הוא המנצח. נניח שנוסיף ממש בתחילת הרשימה. בוא ננסה להכניס לשם מיליון אלמנטים:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

פלט: התוצאה באלפיות שנייה: 43448 התוצאה באלפיות שנייה: 107 כעת אנו מקבלים תוצאה שונה לחלוטין! ArrayList השקיע יותר מ-43 שניות בהכנסת מיליון פריטים בחזית הרשימה, בעוד LinkedList הצליח לעשות זאת תוך 0.1 שניות! LinkedList הרוויח כאן, כי הוא לא היה צריך לרוץ דרך שרשרת הקישורים לאמצע הרשימה בכל פעם. הוא מוצא מיד את האינדקס הדרוש בתחילת הרשימה, כך שהאלגוריתם השונה הוא כבר יתרון. :) למעשה, הדיון " ArrayList לעומת LinkedList " נפוץ מאוד, ולא נצלול לעומקו ברמה הנוכחית. הדבר העיקרי שאתה צריך לזכור הוא זה:

• לא כל היתרונות התיאורטיים של כל אוסף מסוים תמיד עובדים במציאות (ראינו את זה עם הדוגמה הכוללת את אמצע הרשימה)
• אל תאמץ עמדה קיצונית בכל הנוגע לבחירת אוסף (" ArrayList תמיד מהיר יותר. השתמש בו ואי אפשר לטעות. אף אחד לא משתמש ב-LinkedList כבר הרבה זמן").

למרות שאפילו הסופר של LinkedList , ג'ושוע בלוך, אומר שזה המקרה. :) ובכל זאת, הפרספקטיבה הזו רחוקה מלהיות נכונה ב-100%, ושכנענו את עצמנו בכך. בדוגמה הקודמת שלנו, LinkedList היה מהיר פי 400 (!). דבר נוסף הוא שבאמת יש מעט מצבים שבהם LinkedList היא הבחירה הטובה ביותר. אבל הם קיימים, וברגע הנכון LinkedList יכולה לתגמל אותך בצורה יפה. אל תשכח את מה שאמרנו בתחילת השיעור: מבני הנתונים היעילים ביותר שונים עבור משימות שונות. זה בלתי אפשרי להיות בטוח ב-100% איזה מבנה נתונים יהיה הטוב ביותר עד שאתה יודע את כל התנאים של המשימה שלך. תוכל לדעת יותר על האוספים האלה מאוחר יותר, מה שיקל על הבחירה. אבל האפשרות הפשוטה והיעילה ביותר היא תמיד זהה: נסה את שתיהן על הנתונים בפועל המשמשים בתוכנית שלך. אז תוכל לראות בעצמך איך שני סוגי הרשימות מתפקדים ובהחלט לא תטעו. :) כדי לחזק את מה שלמדת, אנו מציעים לך לצפות בשיעור וידאו מקורס ג'אווה שלנו