מדריך לרשימת Java LinkedList

1. הקדמה

רשימה מקושרת הוא יישום רשימת קישורים כפול של ה- רשימה ו דק ממשקים. הוא מיישם את כל פעולות הרשימה האופציונליות ומאפשר את כל האלמנטים (כולל ריק).

2. תכונות

להלן תוכל למצוא את המאפיינים החשובים ביותר של רשימה מקושרת:

  • פעולות שמתווספות לרשימה יחצו את הרשימה מההתחלה או הסוף, הקרוב לאינדקס שצוין
  • זה לא מסונכרן
  • שֶׁלָה איטרטור ו ListIterator איטרטורים מהירים (מה שאומר שלאחר יצירת האיטרטור, אם הרשימה משתנה, א ConcurrentModificationException ייזרק)
  • כל אלמנט הוא צומת, השומר על התייחסות לבאים ולקודמים
  • זה שומר על צו הכניסה

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

רשימת רשימה = Collections.synchronizedList (חדש LinkedList (...));

3. השוואה ל רשימת מערך

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

3.1. מִבְנֶה

An רשימת מערך הוא מבנה נתונים מבוסס אינדקס המגובה על ידי מַעֲרָך. הוא מספק גישה אקראית לאלמנטים שלו עם ביצועים שווים ל- O (1).

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

3.2. פעולות

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

3.3. שימוש בזיכרון

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

4. שימוש

להלן מספר דוגמאות קוד המראות כיצד ניתן להשתמש רשימה מקושרת:

4.1. יצירה

LinkedList linkedList = חדש LinkedList ();

4.2. הוספת אלמנט

רשימה מקושרת מכשירים רשימה ו דק ממשק, מלבד תקן לְהוֹסִיף() ו הוסף הכל() שיטות שתוכלו למצוא addFirst () ו addLast (), שמוסיף אלמנט בהתחלה או בסוף, בהתאמה.

4.3. הסרת אלמנט

בדומה לתוספת אלמנטים הרשימה הזו מציעה יישום removeFirst () ו removeLast ().

כמו כן, יש שיטה נוחה removeFirstOccurence () ו removeLastOccurence () המחזיר בוליאני (נכון אם האוסף הכיל רכיב שצוין).

4.4. פעולות תור

דק ממשק מספק התנהגויות כמו תור (למעשה דק מרחיב תוֹר מִמְשָׁק):

linkedList.poll (); linkedList.pop ();

שיטות אלה מאחזרות את האלמנט הראשון ומסירות אותו מהרשימה.

ההבדל בין מִשׁאָל() ו פּוֹפּ() האם זה פּוֹפּ יזרוק NoSuchElementException () ברשימה ריקה, ואילו מִשׁאָל מחזיר אפס. ממשקי ה- API pollFirst () ו pollLast () זמינים גם כן.

הנה למשל איך ה לִדחוֹף API עובד:

linkedList.push (אובייקט o);

מה שמכניס את האלמנט כראש האוסף.

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

את התיעוד המלא תוכלו למצוא כאן.

5. מסקנה

רשימת מערך הוא בדרך כלל ברירת המחדל רשימה יישום.

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

ניתן למצוא דוגמאות קוד ב- GitHub.