מבוא לשימוש ברשימות מקושרות ב- Java

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

אבל איך יוצרים רשימה מקושרת ב- Java? בואו נסתכל.

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

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

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

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

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

קָשׁוּר: למד כיצד ליצור שיעורים ב- Java

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

דוגמת מחלקת צומת

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

צומת בכיתה ציבורית {
נתוני פרטיות;
צומת פרטי NextNode;
//constructor
צומת ציבורית () {
נתונים = 0;
NextNode = null;
}
// גטרים וסטרים
public int getData () {
החזר נתונים;
}
public void setData (int data) {
נתונים = נתונים;
}
צומת ציבורית getNextNode () {
החזר את NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

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

להלן דוגמה לרשימה מקושרת ב- Java.

מחלקה ציבורית LinkedList {
ראש צומת פרטי;
//constructor
public LinkedList () {
ראש = אפס;
}
}

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

• הכנס בחזית.
• הכנס באמצע.
• הכנס מאחור.

קָשׁוּר: כיצד לבנות מבני נתונים באמצעות שיעורי ES6 של JavaScript

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

שימוש בשיטת הוספה בחזית

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

הכנס בדוגמה של השיטה הקדמית

להלן דוגמה לאופן בו היית מוסיף נתונים חדשים בחזית הרשימה שלך.

 // הכנס צומת בשיטה הקדמית
public void insert insertAtFront (int key) {
// צור צומת חדש באמצעות מחלקת הצמתים
הצומת Temde = הצומת החדש ();
// בדוק אם צומת הטמפ 'נוצר בהצלחה
// הקצה לו את הנתונים שסיפק המשתמש
אם (טמפ '! = null) {
Temp.setData (מפתח);
Temp.setNextNode (null);
// בדוק אם ראש הרשימה המקושרת ריק
// הקצה את הצומת שנוצר זה עתה למיקום הראש
אם (ראש == null) {
ראש = טמפ ';
}
// אם צומת כבר נמצא במיקום הראש
// הוסף אליו את הצומת החדש והגדר אותו כראש
אחר {
Temp.setNextNode (ראש);
ראש = טמפ ';
}
}
}

ה insertAtFront השיטה בדוגמה למעלה מאפשרת למשתמש להוסיף צמתים חדשים לרשימה מקושרת נתונה.

החלת הכנס בדוגמה הקדמית

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

נהג בכיתה ציבורית {
// מבצע את התוכנית
פוסט סטטי ציבורי ריק (String [] args) {
// צור רשימה מקושרת חדשה בשם List
רשימת LinkedList = LinkedList חדש ();
// הוסף כל ערך לחזית הרשימה המקושרת כצומת חדש
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

ה נהג class (שהוא השם המוקצה לרוב למחלקת ההפעלה ב- Java), משתמש במחלקה LinkedList ליצירת רשימה מקושרת של חמישה מספרים זוגיים. אם מסתכלים על הקוד למעלה צריך להיות קל לראות שהמספר "2" נמצא במיקום הראש ברשימה המקושרת. אבל איך אתה יכול לאשר זאת?

שימוש בשיטת הצגת כל הצמתים

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

הצג דוגמא לשיטת כל הצמתים

להלן דוגמה לשימוש בשיטת הצגת כל ההערות ב- Java.

// להציג את כל שיטות הצמתים
public void displayAllNodes () {
// צור שיחת טמפ חדשה לצומת והקצה אותה לראש הרשימה המקושרת
// אם לראש יש ערך null אז הרשימה המקושרת ריקה
Node Temp = ראש;
אם (ראש == null) {
System.out.println ("הרשימה ריקה.");
לַחֲזוֹר;
}
System.out.println ("הרשימה:");
while (Temp! = null) {
// הדפס את הנתונים בכל צומת לקונסולה (החל מהראש)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

עכשיו כי ה displayAllNodes השיטה נוספה ל- רשימה מקושרת class אתה יכול להציג את הרשימה המקושרת על ידי הוספת שורה אחת של קוד למחלקת הנהגים.

שימוש בדוגמה של שיטת הצגת כל הצמתים

להלן תראה כיצד תשתמש בשיטת הצגת כל הצמתים.

// הדפס את הצמתים ברשימה מקושרת
List.displayAllNodes (); 

ביצוע שורת הקוד למעלה יפיק את הפלט הבא במסוף:

הרשימה:

2 4 6 8 10

שימוש בשיטת Find Node

יהיו מקרים בהם משתמש ירצה למצוא צומת ספציפי ברשימה מקושרת.

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

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

מצא דוגמא לשיטת הצומת

להלן דוגמה לשימוש בשיטת הצומת Find.

// חפש צומת יחיד באמצעות מקש
FindNode בוליאני ציבורי (int key) {
// צור צומת חדשה והנח אותו בראש הרשימה המקושרת
Node Temp = ראש;
// בעוד שהצומת הנוכחי אינו ריק
// לבדוק אם הנתונים שלו תואמים את המפתח שמספק המשתמש
while (Temp! = null) {
אם (Temp.getData () == מפתח) {
System.out.println ("הצומת ברשימה"); 
להחזיר נכון;
}
// לעבור לצומת הבא
Temp = Temp.getNextNode ();
}
// אם המפתח לא נמצא ברשימה המקושרת
System.out.println ("הצומת אינו ברשימה"); 
להחזיר שקר;
}

עם ה displayAllNodes שיטה, אישרת כי רשימה מקושרת מכיל 5 מספרים זוגיים מ -2 עד 10. ה findNode הדוגמא לעיל יכולה לאשר אם אחד מאותם זוגיות הוא הספרה 4 פשוט על ידי קריאה לשיטה במחלקת הנהגים ומתן המספר כפרמטר.

שימוש בדוגמת שיטת הצומת Find

להלן דוגמה לאופן שבו היית משתמש בשיטת הצומת Find בפועל.

// בדוק אם צומת נמצא ברשימה המקושרת
List.findNode (4);

הקוד למעלה יפיק את הפלט הבא במסוף:

הצומת נמצא ברשימה

שימוש בשיטת מחיקת צומת

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

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

מחק דוגמה לשיטת הצומת

להלן דוגמה לשיטת הצומת מחק.

public void findAndDelete (int key) { 
Node Temp = ראש; 
הצומת prev = null; 
// בדוק אם צומת הראש מחזיק את הנתונים 
// ולמחוק אותו 
אם (Temp! = null && Temp.getData () == מפתח) { 
Head = Temp.getNextNode (); 
לַחֲזוֹר; 
} 
// חפש את הצמתים האחרים ברשימה 
// ולמחוק אותו 
while (Temp! = null) { 
אם (Temp.getNextNode (). getData () == מפתח) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (הקודם); 
לַחֲזוֹר; 
} 
Temp = Temp.getNextNode (); 
} 
} 

שימוש בדוגמה של מחיקת צומת

להלן דוגמא לשימוש בשיטת הצומת מחק בפועל.

// מחק את הצומת שמחזיק את הנתונים 4
List.findAndDelete (4);
// הדפס את כל הצמתים ברשימה המקושרת
List.displayAllNodes ();

שימוש בשתי שורות הקוד שלמעלה במחלקת מנהלי התקנים הקיימים יפיק את הפלט הבא במסוף:

הרשימה:
2 6 8 10

אם הגעת לסוף מאמר ההדרכה הזה, למדת:

• כיצד ליצור מחלקת צומת.
• כיצד ליצור מחלקת רשימה מקושרת.
• כיצד לאכלס מחלקת רשימה מקושרת בשיטות שהוגדרו מראש.
• כיצד ליצור מחלקת נהגים ולהשתמש בשיטות הרשימה המקושרות השונות כדי להשיג את התוצאה הרצויה.

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

כיצד ליצור ולבצע פעולות במערכים בג'אווה

לומדים ג'אווה? תן למערכים לטפל בנתונים שלך בקלות.

קרא הבא

על הסופר