מבני נתונים ואלגוריתמים ב- Java, חלק 4: רשימות מקושרות יחידה

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

 class Employee { private int empno; private String name; private double salary; public Employee next; // Other members. }

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

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

הורד קבל את הקוד הורד את שלושת היישומים לדוגמה למאמר זה. נוצר על ידי ג'ף פרייזן עבור JavaWorld.

מהי רשימה מקושרת יחידה?

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

איור 1 מציג רשימה מקושרת יחידה עם שלושה צמתים.

להלן פסאוד-קוד לרשימה המקושרת יחידה.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

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

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

אתה יוצר רשימה המקושרת יחידה על ידי צירוף Nodeאובייקט יחיד . ה- Pseudocode הבא יוצר Nodeאובייקט, מקצה את התייחסותו topלאתחל את שדה הנתונים שלו ומקצה NULLלשדה הקישור שלו:

 top = NEW Node top.name = "A" top.next = NULL 

איור 2 מציג את הרשימה הראשונית המקושרת יחידה העולה מפסאוד-קוד זה.

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

הכנסת צמתים לרשימה המקושרת יחידה

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

  • הכנסה לפני הצומת הראשון.
  • הכנסה אחרי הצומת האחרון.
  • הכנסה בין שני צמתים.

הכנסה לפני הצומת הראשון

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

 DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp 

הרשימה שתתקבל Nodeמופיעה באיור 3.

לפעולה זו מורכבות זמן של O (1).

הכנסה אחרי הצומת האחרון

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

 temp = NEW Node temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // We assume top (and temp2) are not NULL // because of the previous pseudocode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 now references the last node. temp2.next = temp 

איור 4 חושף את הרשימה בעקבות הכנסת NodeC אחרי NodeA.

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

הכנסה בין שני צמתים

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

 temp = NEW Node temp.name = "D" temp2 = top // We assume that the newly created Node inserts after Node // A and that Node A exists. In the real world, there is no // guarantee that any Node exists, so we would need to check // for temp2 containing NULL in both the WHILE loop's header // and after the WHILE loop completes. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 now references Node A. temp.next = temp2.next temp2.next = temp 

איור 5 מציג את הרשימה בעקבות הכנסת NodeD בין Nodes A ו- C.

לפעולה זו מורכבות זמן של O ( n ).

מחיקת צמתים מרשימה מקושרת יחידה

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

  • מחיקת הצומת הראשון.
  • מחיקה של כל צומת מלבד הצומת הראשון.

מחיקת הצומת הראשון

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

 IF top NE NULL THEN top = top.next; // Reference the second Node (or NULL when there's only one Node). END IF 

איור 6 מציג לפני ואחרי תצוגות של רשימה שבה הראשונה Nodeנמחקה. הצומת Bנעלם ו- NodeA הופך לראשון Node.

לפעולה זו מורכבות זמן של O (1).

מחיקה של כל צומת מלבד הצומת הראשון

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

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // We assume that temp references Node A. temp.next = temp.next.next // Node D no longer exists. END IF 

איור 7 מציג תצוגות לפני ואחרי של רשימה שבה Nodeנמחק ביניים . NodeD נעלמת.

This operation has a time complexity of O(n).

Example #1: Create, insert, and delete in a singly linked list

I've created a Java application named SLLDemo that demonstrates how to create, insert, and delete nodes in a singly linked list. Listing 1 presents this application's source code.

Listing 1. Java application demo for singly linked lists (SSLDemo.java, version 1)

 public final class SLLDemo { private static class Node { String name; Node next; } public static void main(String[] args) { Node top = null; // 1. The singly linked list does not exist. top = new Node(); top.name = "A"; top.next = null; dump("Case 1", top); // 2. The singly linked list exists and the node must be inserted // before the first node. Node temp; temp = new Node(); temp.name = "B"; temp.next = top; top = temp; dump("Case 2", top); // 3. The singly linked list exists and the node must be inserted // after the last node. temp = new Node(); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump("Case 3", top); // 4. The singly linked list exists and the node must be inserted // between two nodes. temp = new Node(); temp.name = "D"; temp2 = top; while (temp2.name.equals("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump("Case 4", top); // 5. Delete the first node. top = top.next; dump("After first node deletion", top); // 5.1 Restore node B. temp = new Node(); temp.name = "B"; temp.next = top; top = temp; // 6. Delete any node but the first node. temp = top; while (temp.name.equals("A") == false) temp = temp.next; temp.next = temp.next.next; dump("After D node deletion", top); } private static void dump(String msg, Node topNode) { System.out.print(msg + " "); while (topNode != null) { System.out.print(topNode.name + " "); topNode = topNode.next; } System.out.println(); } } 

Compile Listing 1 as follows:

 javac SLLDemo.java 

Run the resulting application as follows:

 java SLLDemo 

You should observe the following output:

 Case 1 A Case 2 B A Case 3 B A C Case 4 B A D C After first node deletion A D C After D node deletion B A C 

Concatenating singly linked lists

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Assume code that creates top1-referenced singly linked list. // Assume code that creates top2-referenced singly linked list. // Concatenate top2-referenced list to top1-referenced list. IF top1 EQ NULL top1 = top2 END END IF // Locate final Node in top1-referenced list. DECLARE Node temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Concatenate top2 to top1. temp.next = top2 END 

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2's value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there's no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list's links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list's links:

 DECLARE Node p = top1 // Top of original singly linked list. DECLARE Node q = NULL // Top of reversed singly linked list. DECLARE Node r // Temporary Node reference variable. WHILE p NE NULL // For each Node in original singly linked list ... r = q // Save future successor Node's reference. q = p // Reference future predecessor Node. p = p.next // Reference next Node in original singly linked list. q.next = r // Link future predecessor Node to future successor Node. END WHILE top1 = q // Make top1 reference first Node in reversed singly linked list. END 

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

יצרתי גרסה שנייה של SLLDemoיישום Java המדגימה שרשור והיפוך. רישום 2 מציג את קוד המקור של היישום הזה.