מבני נתונים ואלגוריתמים ב- Java, חלק 5: רשימות מקושרות כפליים

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

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

רשימות המקושרות כפליים

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

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

פעולות CRUD ברשימות המקושרות כפליים

יצירה, הוספה ומחיקה של צמתים הם פעולות נפוצות ברשימה המקושרת כפליים. הם דומים לפעולות שלמדת עבור רשימות המקושרות יחידה. (זכרו שרשימה מקושרת כפול היא רק זוג רשימות המקושרות יחדיו המחברות את אותם צמתים.) הפסאוד-קוד הבא מדגים את יצירת והכנסת הצמתים לרשימה המקושרת כפליים המוצגת באיור 1. הפסאוד-קוד גם מדגים את הצומת. מְחִיקָה:

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward.name = "C" // Create forward singly-linked list topForward.next = temp temp.next = topBackward topBackward.next = NULL // Create backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Delete Node B. temp.prev.next = temp.next; // Bypass Node B in the forward singly-linked list. temp.next.prev = temp.prev; // Bypass Node B in the backward singly-linked list. END 

יישום לדוגמא: CRUD ברשימה המקושרת כפליים

יישום Java לדוגמה DLLDemoמדגים כיצד ליצור, להוסיף ולמחוק צמתים ברשימה המקושרת כפליים. קוד המקור של היישום מוצג ברשימה 1.

רישום 1. יישום Java המדגים CRUD ברשימה המקושרת כפליים

 public final class DLLDemo { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Reference node B. temp = topForward.next; // Delete node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump forward singly-linked list. System.out.print("Forward singly-linked list (after deletion): "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list (after deletion): "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } } 

הידר את רישום 4 באופן הבא:

 javac DLLDemo.java 

הפעל את היישום שהתקבל באופן הבא:

 java DLLDemo 

עליכם להתבונן בפלט הבא:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA 

דשדוש ברשימות המקושרות כפליים

מסגרת אוספי הג'אווה כוללת Collectionsסוג של שיטות שירות, המהווה חלק java.utilמהחבילה. מחלקה זו כוללת void shuffle(List list)שיטה ש"מאפשרת באופן אקראי לרשימה שצוינה באמצעות מקור ברירת מחדל לאקראיות . " לדוגמה, ייתכן שתשתמש בשיטה זו כדי לדשדש את חפיסת הקלפים המתבטאת כרשימה המקושרת כפליים ( java.util.LinkedListהמחלקה היא דוגמה). בפסאודוקוד למטה, תוכל לראות כיצד אלגוריתם הדשדוש עשוי לדשדש רשימה מקושרת כפליים:

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap(topForward, i - 1, rnd.nextInt(i)) END FOR FUNCTION swap(Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Locate ith node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Locate jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Perform the swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END 

אלגוריתם ה- Shuffle משיג מקור לאקראיות ואז עובר את הרשימה לאחור, מהצומת האחרון ועד השני. הוא מחליף שוב ושוב צומת שנבחרה באופן אקראי (שהוא למעשה רק שדה השם) ל"מיקום הנוכחי ". צמתים נבחרים באופן אקראי מחלק הרשימה שעובר מהצומת הראשון למיקום הנוכחי, כולל. שים לב שאלגוריתם זה מוצג בערך void shuffle(List list)מקוד המקור.

אלגוריתם ה- Shuffle pseudocode הוא עצלן מכיוון שהוא מתמקד רק ברשימה המקושרת יחידה. זו החלטה עיצובית סבירה, אבל אנחנו משלמים עליה מחיר במורכבות הזמן. מורכבות הזמן היא O ( n 2). ראשית, יש לנו את לולאת ה- O ( n ) שמתקשרת swap(). שנית, בתוכנו swap(), יש לנו שני לולאות O ( n ) עוקבות . זכור את הכלל הבא מחלק 1:

 If f1(n) = O(g(n)) and f2(n) = O(h(n)) then (a) f1(n)+f2(n) = max(O(g(n)), O(h(n))) (b) f1(n)*f2(n) = O(g(n)*h(n)). 

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

שים לב שמורכבות החלל של Shuffle היא O (1), כתוצאה מהמשתנים המסייעים המוצהרים.

יישום לדוגמא: דשדוש ברשימה המקושרת כפליים

Shuffleהיישום ברישום 2 הוא הפגנה של האלגוריתם ערבב.

רישום 2. אלגוריתם הדשדוש בג'אווה

 import java.util.Random; public final class Shuffle { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Shuffle list. Random rnd = new Random(); for (int i = 3; i > 1; i--) swap(topForward, i - 1, rnd.nextInt(i)); // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } public static void swap(Node top, int i, int j) { // Locate ith node. Node nodei = top; for (int k = 0; k < i; k++) nodei = nodei.next; // Locate jth node. Node nodej = top; for (int k = 0; k < j; k++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; } } 

הידור רישום 5 כדלקמן:

 javac Shuffle.java 

הפעל את היישום שהתקבל באופן הבא:

 java Shuffle 

עליך להתבונן בפלט הבא מריצה אחת:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list: BAC Backward singly-linked list: CAB 

רשימות מקושרות מעגליות

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

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

רשימות מקושרות מול מערכים

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

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

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

לעומת זאת, מערכים מציעים את היתרונות הבאים על פני רשימות מקושרות:

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