מערכים דינמיים ב-Java

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

מערכים דינמיים בקורס JavaRush

נושא זה מכוסה בצורה מאוד מובנת וברורה ברמה 7 וחלקית ברמה 8 של קורס JavaRush ב-Java Syntax Quest. במהלך מספר הרצאות ועד 18 בעיות, נסקרים נושאים מרכזיים, סוגי מערכים דינמיים וההבדל ביניהם, כולל ביצועים. נושא זה חשוב ביותר, שכן מערכים דינמיים מקלים על המפתח דיכאון, כאבי ראש וחוסכים כמות מדהימה של זמן.

מהו מערך דינמי?

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

למה אנחנו צריכים מערך דינמי?

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

1. צור מערך גדול שיש לו 100% סיכוי לכסות את הצורך;
2. צור מערך סטטי שיפעל כמאגר;
3. החל מבנים דינמיים אחרים, כגון סטים.

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

מה עושה מערך דינמי ב-Java?

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

ArrayList, LinkedList - מושגים וכללי הפעלה

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

• בדיוק כמו מערך סטטי, הוא מתווסף מ-0;
• ההכנסה בסוף והגישה לפי אינדקס מהירים מאוד - O(1);
• כדי להוסיף אלמנט בהתחלה או באמצע, תצטרך להעתיק את כל הרכיבים תא אחד ימינה, ולאחר מכן להדביק אלמנט חדש במיקום הנדרש;
• גישה לפי ערך תלויה במספר האלמנטים - O(n);
• שלא כמו מערך קלאסי, הוא יכול לאחסן null;

במקרה של LinkedList, הכל קצת יותר מסובך: הוא מבוסס על רשימה מקושרת כפולה. כלומר, מבחינה מבנית, מערך ג'אווה דינמי זה הוא מספר אובייקטים מפוזרים שמתייחסים זה לזה. קל יותר להסביר עם תמונות. בתוך LinkedList יש לנו אובייקט ראשי Head, המאחסן מידע על מספר האלמנטים, וכן קישור לאלמנט הראשון והאחרון: כעת השדה size = 0הוא , firstו last = null. כל אלמנט שמתווסף לרשימה זו הוא תוכן של אובייקט פנימי נפרד. בואו נוסיף אלמנט Johnny: עכשיו יש לנו צומת עם הערך "ג'וני". עבור האלמנט הראשי, הקישורים לאלמנט הראשון והאחרון מצביעים על הצומת החדש. לאובייקט זה יש גם קישורים לאלמנטים הקודמים והבאים. הקישור לקודם תמיד יהיה null, מכיוון שזהו האלמנט הראשון, והקישור אל הבא תמיד יהיה null, כי הוא עדיין לא קיים. בואו נתקן את זה: הוסיף אלמנט חדש עם הערך "Watson", שהפך לשני. שימו לב שלאלמנט הראשון יש שדה nextשמצביע על האלמנט הבא, ולאלמנט החדש יש שדה previousשמצביע על הקודם. עבור האלמנט הראשי, הקישור לאלמנט האחרון מצביע כעת על הצומת החדש. התרשים הבא מראה כיצד להוסיף אלמנטים לאמצע הרשימה: אלמנט חדש "חמיש" נוסף. כדי להכניס אותו לאמצע הרשימה, פשוט הקצה מחדש את הקישורים לאלמנטים, כפי שמוצג באיור. איורים אלו מסבירים את התהליך של רשימה מקושרת כפולה ברמה העליונה, מבלי להיכנס לפרטים. כדי לסכם את הסיפור על LinkedList, אנו יכולים לגזור מספר כללים לפעולתה:

• בדיוק כמו מערך, הוא מתווסף מ-0;
• הגישה לאלמנט הראשון והאחרון אינה תלויה במספר האלמנטים - O(1);
• קבלת אלמנט לפי אינדקס, הכנסה או מחיקה מאמצע רשימה תלוי במספר האלמנטים - O(n);
• אתה יכול להשתמש במנגנון האיטרטור: אז הכנסה ומחיקה יתרחשו בזמן קבוע;
• שלא כמו מערך קלאסי, הוא יכול לאחסן null.

דוגמאות קוד

בואו נעבור על כמה דוגמאות. קטעי הקוד כוללים דוגמאות הן עבור ArrayList והן עבור LinkedList.

יצירה

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

הוספת אלמנט

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

במבט ראשון, שיטות ה- add()AND addLast()מבצעות את אותה פונקציונליות, אך השיטה add()הגיעה ל-LinkedList מהממשק List, והשיטה addLastהגיעה מהממשק Deque. LinkedList מיישמת את שני הממשקים הללו. תרגול טוב במקרה זה יהיה להשתמש בשיטה המתאימה ביותר להקשר. אם LinkedList משמש כתור, עדיף להשתמש ב- addLast. אם LinkedList משמש כרשימה, יהיה מתאים להשתמש ב- add().

הסרת אלמנט

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

אם אובייקט נמחק על ידי אינדקס, השיטה מחזירה את האובייקט שנמחק. אם אובייקט נמחק לפי ערך (או שהרכיבים הראשונים או האחרונים של LinkedList נמחקים), השיטה מחזירה true אם האובייקט נמצא ונמחק, אחרת false .

גישה לפריט וחיפוש ברשימה

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

הליכה בלופ

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

כאן כדאי לומר כמה מילים על החיפוש. מפתחים מתחילים רבים, כאשר מחפשים אלמנט ברשימה, מתחילים את החיפוש בלולאה, ומשווים את כל האלמנטים לאחד שחיפשו, למרות נוכחותן של שיטות indexOf()ו- lastIndexOf(). אתה יכול גם להשתמש בשיטה contains()כדי לקבל את העובדה שאלמנט נמצא ברשימה:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

קישורים לקריאה נוספת

1. יש כאן מאמר מצוין על הסרת אלמנטים מ-ArrayList. בשל העובדה שמדובר במערך Java דינמי , ישנן דקויות רבות בהסרת אלמנטים.
2. פעולתו של ArrayList מומחשת בפירוט כאן .
3. קצת יותר על LinkedList.
4. כמה מאמרים מהאבר על ArrayList ו- LinkedList .