Java ArrayList לעומת LinkedList

1. סקירה כללית

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

במדריך זה, נראה כיצד מיושמים למעשה שני אלה. לאחר מכן נעריך יישומים שונים לכל אחד.

2. רשימת מערך

כְּלַפֵּי פְּנִים, רשימת מערך משתמש במערך ליישום ה- רשימה מִמְשָׁק. מכיוון שמערכים הם בגודל קבוע ב- Java, רשימת מערך יוצר מערך עם יכולת התחלתית מסוימת. בדרך, אם נצטרך לאחסן יותר פריטים מקיבולת ברירת המחדל ההיא, הוא יחליף את המערך במערך חדש ומרווח יותר.

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

2.1. לְהוֹסִיף

כשאנחנו יוצרים ריק רשימת מערך, הוא מאתחל את מערך הגיבוי שלו עם קיבולת ברירת מחדל (כיום 10):

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

backingArray [size] = newItem; גודל ++;

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

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

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

2.2. גישה באמצעות אינדקס

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

2.3. הסר לפי אינדקס

נניח שנסיר את אינדקס 6 מה- רשימת מערך, המתאים לאלמנט 15 במערך הגיבוי שלנו:

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

2.4. יישומים ומגבלות

בְּדֶרֶך כְּלַל, רשימת מערך היא בחירת ברירת המחדל עבור מפתחים רבים כאשר הם זקוקים ל- רשימה יישום. למעשה, זו למעשה בחירה הגיונית כאשר מספר הקריאות הוא הרבה יותר ממספר הכותבים.

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

int possibleUpperBound = 10_000; פריטי רשימה = ArrayList חדש (possibleUpperBound);

הערכה זו עשויה למנוע המון העתקות והקצאות מיותרות.

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

3. רשימה מקושרת

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

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

שוב, בואו ונעריך יישום זה ביחס לאותן פעולות בסיסיות.

3.1. לְהוֹסִיף

כדי להוסיף צומת חדש, ראשית עלינו לקשר את הצומת האחרון הנוכחי לצומת החדש:

ואז עדכן את המצביע האחרון:

מכיוון ששתי הפעולות הללו אינן טריוויאליות, מורכבות הזמן לפעולת ההוספה היא תמיד O (1).

3.2. גישה באמצעות אינדקס

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

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

3.3. הסר לפי אינדקס

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

3.4. יישומים

LinkedLists מתאימים יותר כאשר קצב התוספת גבוה בהרבה משיעור הקריאה.

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

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

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

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

כמו כן, היינו קוראים את כל הפריטים, כך שלא נוכל לנצח את עַל) גבול עליון.

4. מסקנה

במדריך זה, ראשית, צללנו כיצד רשימת מערך ו רשימות קישורים מיושמים בג'אווה.

הערכנו גם מקרי שימוש שונים עבור כל אחד מאלה.


$config[zx-auto] not found$config[zx-overlay] not found