Java ArrayList בתמונות

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

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

ראשית, בואו נסתכל כיצד נראית הוספת אלמנט חדש. קודם כל בודקים האם יש מספיק מקום במערך הפנימי והאם יתאים עוד אלמנט אחד. אם יש מקום, הרכיב החדש נוסף לסוף הרשימה. כשאנחנו אומרים "עד הסוף", אנחנו לא מתכוונים לתא האחרון של המערך (זה יהיה מוזר). זה מתייחס לתא שליד האלמנט הנוכחי האחרון. המדד שלו יהיה שווה ל cars.size(). הרשימה שלנו ריקה כרגע ( cars.size() = 0). בהתאם, יתווסף אלמנט חדש לתא עם index 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

הכל ברור כאן. מה יקרה אם ההחדרה תתבצע באמצע, כלומר בין מספר אלמנטים?

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

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);

   cars.add(1, ford);//добавляем ford в ячейку 1, которая уже занята
}

שוב, הוא בודק תחילה אם יש מספיק מקום במערך. אם יש מספיק מקום, האלמנטים מוזזים ימינה החל מהתא שבו אנו מכניסים את האלמנט החדש. אנו מדביקים לתוך התא עם אינדקס 1. כלומר, האלמנט מתא 3 מועתק לתא 4, אלמנט 2 לתא 3, אלמנט 1 לתא 2. לאחר מכן, האלמנט החדש שלנו מודבק למקומו. הרכיב הקודם ( bugatti) כבר הועתק משם למיקום חדש. עכשיו בואו נבין איך התהליך הזה היה קורה אם לא היה מקום להכנסה במערך. ראשית, כמובן, בודקים אם יש מספיק מקום. אם מתברר שאין מספיק מקום, ArrayListנוצר מערך חדש של גודל (גודל של OldArray * 1.5) + 1 בתוך 'a. במקרה שלנו, למערך החדש יהיה גודל של 16 תאים. כל הרכיבים הנוכחיים יועתקו לשם מיד. המערך הישן יימחק על ידי אספן האשפה, ורק החדש והמורחב יישאר. כעת יש מקום פנוי לאלמנט החדש. אנחנו מדביקים אותו לתוך תא 3, שהוא תפוס. כעת מתחיל ההליך המוכר. כל האלמנטים שמתחילים באינדקס 3 מוזזים תא אחד ימינה, ואלמנט חדש נוסף בשקט. ועכשיו ההכנסה מוצלחת! סידרנו את ההכנסה. עכשיו בואו נדבר על הסרת אלמנטים . כזכור, כשעבדנו עם מערכים, נתקלנו בבעיה: כשמחקנו אותם, נשארו בו "חורים". הפתרון היחיד היה להעביר אלמנטים שמאלה בכל פעם שהם נמחקו, והיית צריך לכתוב את הקוד של המשמרת בעצמך. ArrayListעובד על אותו עיקרון, אבל בו המנגנון הזה כבר מיושם אוטומטית. כך זה נראה: ובסוף נקבל את התוצאה הרצויה: האלמנט lamboנמחק בהצלחה. כאן עשינו הסרה מהאמצע. ברור שהמחיקה מסוף הרשימה תהיה מהירה יותר, שכן האלמנט הרצוי מוסר מבלי להזיז את כל האחרים. בואו נסתכל שוב על גודל המערך הפנימי והאחסון שלו בזיכרון. הרחבת מערך היא תהליך שלוקח כמות מסוימת של משאבים. לכן, לא כדאי ליצור ArrayListעם גודל ברירת המחדל אם אתה יודע בוודאות שיהיו בו לפחות 100 אלמנטים. עד שתגיעו להכנסת האלמנט ה-100, המערך הפנימי יתרחב 6 פעמים , בכל פעם יעביר את כל האלמנטים.

• מ-10 אלמנטים ל-16
• מ-16 אלמנטים ל-25
• מגיל 25 עד 38
• מ-38 עד 58
• מ-58 עד 88
• מ-88 עד 133 (לפי הנוסחה (גודל המערך הישן * 1.5) + 1)

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

ArrayList<Car> cars = new ArrayList<>(100);

כעת יוקצה מיידית מערך של 100 אלמנטים בזיכרון, מה שיהיה יעיל יותר כי משאבים לא יבזבזו על הרחבה. יש גם את הצד השני של המטבע. כאשר אובייקטים מוסרים מהמערך ArrayListהפנימי, הגודל אינו מצטמצם אוטומטית. לדוגמה, יש לנו ArrayListמערך פנימי של 88 אלמנטים, שמתמלא לחלוטין: במהלך פעולת התוכנית, אנו מסירים ממנה 77 אלמנטים, ונשארים בו רק 11: כבר ניחשתם מה הבעיה? שימוש לא יעיל בזיכרון, כמובן! אנו משתמשים רק ב-11 תאים, בעוד שיש לנו זיכרון שהוקצה ל-88 אלמנטים - זה פי 8 יותר ממה שאנחנו צריכים! כדי לבצע אופטימיזציה במקרה זה, אתה יכול להשתמש בשיטת מחלקה מיוחדת ArrayList- trimToSize(). הוא "חותך" את אורך המערך הפנימי למספר האלמנטים המאוחסנים בו כעת. עכשיו מוקצה כמה שיותר זיכרון לפי הצורך! :)