ArrayList בתמונות

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

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

ראשית, בואו נראה איך נראית הוספת אלמנטים חדשים. הצו הראשון של העסק הוא לבדוק האם למערך הפנימי יש מספיק מקום במערך הפנימי והאם אלמנט אחד נוסף יתאים. אם יש מקום, אז האלמנט החדש נוסף לסוף הרשימה. כשאנחנו אומרים "עד הסוף", אנחנו לא מתכוונים למיקום האחרון במערך (זה יהיה מוזר). אנו מתכוונים למיקום העוקב אחר האלמנט הנוכחי האחרון. המדד שלו יהיה cars.size(). הרשימה שלנו ריקה כרגע ( cars.size() == 0). בהתאם לכך, האלמנט החדש יתווסף בעמדה 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);// add ford to cell 1, which is already occupied
}

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

• מ-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(). שיטה זו "מקצצת" את אורך המערך הפנימי עד למספר האלמנטים המאוחסנים בו כעת. עכשיו הקצנו רק כמה זיכרון שאנחנו צריכים! :)