LinkedList ב-Java

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

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

סיכום:

[Hello World! My name is Earl, I love Java, I live in Moscow]

כך ייראה המבנה של הרשימה שלנו: בואו נראה איך מוסיפים אלמנט חדש. זה נעשה באמצעות add().

earlBio.add(str2);

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

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

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

public class Main {

   public static void main(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 Moscow");

       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()(הכנסת אלמנט עם תחליף) size()קיימות בשתי המחלקות. אמנם (כפי שגילינו בדוגמה 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 + '\'' +
               '}';
   }
}

סיכום:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{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());
}

סיכום:

Car{model='Ferrari 360 Spider'}
Car{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 left on the list?");
   System.out.println(cars);
}

סיכום:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{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 to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

סיכום:

Время работы для LinkedList (в мorсекундах) = 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 to run for 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 לאורך שרשרת הקישורים. מבחינתו זו לא כתובת בזיכרון, אלא קישור שעדיין צריך להגיע אליו:

fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.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("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

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

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

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