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

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

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

---

---

כיצד פועלת רשימה מקושרת?

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

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

יצירת רשימה מקושרת ב- Java

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

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

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

---

---

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

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

---

---

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

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


public class Node {
private int Data;
private Node NextNode;
//constructor
public Node() {
Data = 0;
NextNode = null;
}
//getters and setters
public int getData() {
return Data;
}
public void setData(int data) {
Data = data;
}
public Node getNextNode() {
return NextNode;
}
public void setNextNode(Node nextNode) {
NextNode = nextNode;
}
}

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

דוגמה לרשימה מקושרת

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

public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = null;
}
}


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

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

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

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

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

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

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

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

//insert node at front method
public void insertAtFront(int key) {
//create a new node using the node class
Node Temp = new Node();
//check if the Temp node was successfully created
//assign the data that was provides by the user to it
if(Temp != null) {
Temp.setData(key);
Temp.setNextNode(null);

//check if the head of the linked list is empty
//assign the node that was just created to the head position
if(Head == null) {
Head = Temp;
}
//if a node is already at the head position
//add the new node to it and set it as the head
else {
Temp.setNextNode(Head);
Head = Temp;
}
}
}


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

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

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

public class Driver {
//executes the program
public static void main(String[] args) {
//create a new linked list called List
LinkedList List = new LinkedList();
//add each value to the front of the linked list as a new node
List.insertAtFront(10);
List.insertAtFront(8);
List.insertAtFront(6);
List.insertAtFront(4);
List.insertAtFront(2);
}
}


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

כיצד לתקן כפתור בית שבור

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

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

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

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

//display all nodes method
public void displayAllNodes() {
//create a new node call Temp and assign it to the head of the linked list
//if the head has a null value then the linked list is empty
Node Temp = Head;
if (Head == null){
System.out.println('The list is empty.');
return;
}
System.out.println('The List:');

while(Temp != null) {
//print the data in each node to the console(starting from the head)
System.out.print(Temp.getData() + ' ');
Temp = Temp.getNextNode();
}
}

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

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

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

//print the nodes in a linked list
List.displayAllNodes();

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

הרשימה:

2 4 6 8 10

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

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

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

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

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

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

//search for a single node using a key
public boolean findNode(int key) {
//create a new node and place it at the head of the linked list
Node Temp = Head;
//while the current node is not empty
//check if its data matches the key provided by the user
while (Temp != null) {
if (Temp.getData() == key) {
System.out.println('The node is in the list');
return true;
}
//move to the next node
Temp = Temp.getNextNode();
}
//if the key was not found in the linked list
System.out.println('The node is not in the list');
return false;
}

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

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

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

//check if a node is in the linked list
List.findNode(4);


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

The node is in the list

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

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

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

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

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

public void findAndDelete(int key) {
Node Temp = Head;
Node prev = null;
//check if the head node holds the data
//and delete it
if (Temp != null && Temp.getData() == key) {
Head = Temp.getNextNode();
return;
}
//search the other nodes in the list
//and delete it
while (Temp != null) {
if (Temp.getNextNode().getData() == key ) {
prev = Temp.getNextNode().getNextNode();
Temp.setNextNode(prev);
return;
}
Temp = Temp.getNextNode();
}
}

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

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

חלונות 10 לא מצליח להגיע לשולחן העבודה

//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();

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

The List:
2 6 8 10

כעת תוכל ליצור רשימות מקושרות ב- Java

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

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

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

לַחֲלוֹק לַחֲלוֹק צִיוּץ אימייל כיצד ליצור ולבצע פעולות במערכים בג'אווה

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

קרא הבא נושאים קשורים

• תִכנוּת
• ג'אווה
• תִכנוּת
• טיפים לקידוד

על הסופר קדישא קין(פורסמו 21 מאמרים)

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

עוד מ- Kadeisha Kean

הירשם לניוזלטר שלנו

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

לחצו כאן להרשמה