>> [השמעת מוסיקה]
דאג LLOYD: בסדר.
אז אם אתה רק סיימת ש וידאו ברשימות ביחידות צמודות מצטער
עזבתי אותך ב קצת סחרור מסוכן.
אבל אני שמח שאתה כאן כדי לסיים הסיפור של רשימות כפולים צמודות.
>> אז אם אתה זוכר מ וידאו ש, דיברנו
על איך ביחידות צמודות רשימות לעשות להשתתף היכולת שלנו
כדי להתמודד עם מידע שבו מספר האלמנטים
או את מספר הפריטים ב רשימה יכולה לגדול או להתכווץ.
כעת אנו יכולים להתמודד עם משהו כזה, שבו
אנו לא יכולים להתמודד עם זה עם מערכים.
>> אבל הם סובלים מאחד מגבלה קריטית ש
הוא שעם יחידים צמודים רשימה, אנחנו יכולים רק פעם לעבור
בכיוון אחד ברשימה.
ואת המצב האמיתי רק איפה זה יכול להיות בעיה
היה כאשר אנחנו מנסים למחוק אלמנט בודד.
ואנחנו אפילו לא לדון איך לעשות את זה ברשימה ביחידות צמודה בפסאודו קוד.
זה בהחלט אפשרי, אבל זה יכול להיות קצת טרחה.
אז אם אתה מוצא את עצמך במצב שבו
אתה מנסה למחוק אלמנטים יחידים מהרשימה
או שזה הולך להיות נדרשת כי אתה תהיה מחיקה
אלמנטים יחידים מ הרשימה, ייתכן שתרצי
לשקול שימוש כפול צמוד רשימה במקום רשימת יחידות צמודה.
בגלל רשימות כפולים צמודות תאפשר לך כדי להזיז את שני קדימה ואחורה
ברשימה במקום רק קדימה דרך list--
רק על ידי הוספת אלמנט אחד נוסף להגדרת המבנה שלנו
לצומת הרשימה כפליים צמודה.
>> שוב, אם אתה לא הולך ל להיות מחיקת אלמנטים בודדים
מlist-- כי אנו מוסיפים שדה נוסף למבנה שלנו
הגדרה, בלוטות עצמם לרשימות כפולים צמודות
הולכים להיות גדול יותר.
הם הולכים לקחת יותר בתים של זיכרון.
ולכן אם זה לא משהו אתה הולך צריך לעשות,
אולי אתה מחליט שזה לא שווה את הסחר מ
צריך להשקיע נוסף בתים של זיכרון הנדרש
לרשימה כפליים צמודה אם אתה לא הולכים להיות מחיקת אלמנטים בודדים.
אבל הם גם מגניבים לדברים אחרים גם.
>> אז כמו שאמרתי, אנחנו רק צריכים להוסיף שדה אחד למבנה שלנו
definition-- הרעיון הזה של מצביע קודם.
אז עם רשימה ביחידות צמודה, אנחנו יש ערך והמצביע הבא,
כך הרשימה כפליים צמודה רק ל דרך להעביר אחורה גם כן.
>> עכשיו בצמוד ליחידים וידאו רשימה, שדברנו
על אלה חמש דברים עיקריים שאתה צריך להיות
תוכל לעשות כדי לעבוד עם רשימות מקושרות.
ועבור רוב אלה, העובדה שזה רשימה כפליים צמודה
הוא לא ממש קפיצה גדולה.
אנחנו עדיין יכולים לחפש דרך רק על ידי לנוע קדימה מהתחלה ועד סופו.
אנחנו עדיין יכולים ליצור צומת מ אוויר דליל, פחות או יותר באותה צורה.
אנחנו יכולים למחוק את הרשימות די בדרך הדומה מדי.
הדברים היחידים ש הם שונים בעדינות,
באמת, מכניסים בלוטות חדשות לרשימה,
ואנחנו סוף הסוף מדברים על מחיקה אלמנט יחיד מהרשימה גם כן.
שוב, פחות או יותר שלוש האחרים, אנחנו
לא הולך לדבר עליהם עכשיו בגלל שהם פשוט
tweaks קטן מאוד על הרעיונות שנדון בוידאו רשימת יחידות הצמודות.
>> אז בואו נכניס צומת חדשה לרשימה כפליים צמודה.
דברנו על לעשות את זה ל ביחידים צמודים רשימות, כמו גם,
אבל יש כמה נוסף תופס עם רשימות כפולים צמודות.
אנחנו [? עובר?] בראש רשימה כאן וכמה ערך שרירותי,
ואנחנו רוצים לקבל את הראש החדש הרשימה מתוך פונקציה זו.
זו הסיבה לכך שהוא חוזר לכוכב dllnode.
אז מה הם השלבים?
הם, שוב, מאוד דומים ליחידים צמודים רשימות
עם תוספת אחת נוספת.
אנחנו רוצים מקצה מקום לחדש צומת וסימון כדי לוודא שהוא תקף.
אנחנו רוצים למלא את הצומת ש עם כל מידע שאנו
רוצה לשים את זה.
הדבר האחרון שאנחנו צריכים do-- דבר נוסף שאנחנו צריכים לעשות, rather--
הוא לתקן את המצביע הקודם של ראש הרשימה הישן.
זכור כי בגלל רשימות של כפליים צמודות,
אנחנו יכולים להתקדם וbackwards-- ש
משמעות הדבר היא כי כל צומת מצביעה למעשה לשני צמתים אחרים רק במקום אחד.
ולכן אנחנו צריכים לתקן ראש הרשימה הישן
להצביע אחורה לראש החדש של הרשימה המקושרת, שהיה משהו
אנו לא צריכים לעשות לפני.
וכמו בעבר, אנחנו פשוט לחזור מצביע לראש החדש של הרשימה.
>> אז הנה רשימה.
אנחנו רוצים להכניס 12 לרשימה זו.
שים לב שהתרשים הוא מעט שונה.
כל צומת מכיל שלוש fields-- הנתונים, ומצביע הבא באדום,
ומצביע קודם בכחול.
שום דבר לא בא לפני הצומת 15, כך המצביע הקודם שלה הוא null.
זוהי תחילתה של הרשימה.
אין שום דבר לפני זה.
ושום דבר לא בא אחרי 10 הצומת, ו אז זה המצביע הבא הוא null גם כן.
>> אז בואו נוסיף 12 לרשימה זו.
אנחנו צריכים [לא ברורים] מקום לצומת.
אנחנו שמים 12 בתוכו.
ואז שוב, אנחנו צריכים להיות באמת היזהר שלא לשבור את השרשרת.
אנחנו רוצים לארגן מחדש את מצביעים בסדר הנכונה.
ולפעמים שעשוי mean-- כפי שנראה במיוחד
עם delete-- שיש להם כמה אנחנו מצביעים מיותרים, אבל זה בסדר.
>> אז מה אנחנו רוצים לעשות קודם?
אני ממליץ דברים שאתה כנראה צריך
לעשות הם למלא את המצביעים של 12 צומת לפני שתיגע אף אחד אחר.
אז מה הוא 12 הולכים להצביע הבא?
15.
מה בא לפני 12?
לא כלום.
עכשיו אנחנו כבר מילאתי מידע נוסף ב -12
כך יש לו, בשלב הבא, וערך קודמים.
>> עכשיו אנחנו יכולים להיות 15-- זה נוסף צעד שאנחנו מדברים על--
יכול להיות 15 נקודות בחזרה ל -12.
ועכשיו אנחנו יכולים להזיז את ראש הרשימה המקושרת להיות גם 12.
אז זה די דומה למה ש עושים עם רשימות ביחידות צמודות,
פרט לצעד הנוסף של חיבור ראש הרשימה הישן
לגבות לראש החדש של הרשימה.
>> עכשיו בואו סוף סוף להסיר צומת מרשימה מקושרת.
אז בואו נגיד שיש לנו תפקיד אחר ש
הוא מציאת צומת אנחנו רוצים למחוק ונתן לנו מצביע בדיוק
הצומת שאנחנו רוצים למחוק.
אנחנו אפילו לא אומרים need-- הראש עדיין הכריז באופן גלובלי.
אנחנו לא צריכים את הראש כאן.
כל פונקציה זו עושה היא שיש לנו מצאתי מצביע בדיוק אנחנו הצומת
רוצה להיפטר מ.
בואו להיפטר ממנו.
זה הרבה יותר קל עם כפליים צמוד רשימות.
First-- זה בעצם רק כמה דברים.
אנחנו רק צריכים לתקן מקיפים מצביעים 'בלוטות, כך שהם לדלג על
הצומת שאנחנו רוצים למחוק.
ואז אנחנו יכולים למחוק את הצומת.
אז שוב, אנחנו רק עוברים כאן.
אנחנו החלטנו כנראה ש אנחנו רוצים למחוק את X. הצומת
ושוב, מה שאני עושה כאן-- על ידי way--
הוא מקרה כללי ל צומת שנמצאת באמצע.
יש כמה אזהרות נוספות ש
צריך לקחת בחשבון כאשר אתה מוחק תחילתה של הרשימה מאוד
או הסוף של הרשימה.
יש כמה מיוחד מקרי פינה להתמודד עם שם.
>> אז זה עובד למחיקה כל צומת באמצע list-- אחד ש
יש מצביע לגיטימי קדימה ומצביע לגיטימי לאחור,
המצביע קודם והבא לגיטימי.
שוב, אם אתה עובד עם הקצוות,
צריך לטפל באותם בצורה קצת שונה,
ואנחנו לא הולכים ל לדבר על זה עכשיו.
אבל כנראה שאתה יכול להבין את מה שצריך
להיעשות רק על ידי צפייה בסרטון זה.
>> X X. אז אנחנו כבר מבודדים הוא הצומת אנחנו רוצים למחוק מהרשימה.
מה אנחנו עושים?
ראשית, אנחנו צריכים לארגן מחדש המצביעים מחוץ.
אנחנו צריכים לארגן מחדש 9 של הבא כדי לדלג מעל 13
ונקודה ל10-- ש מה בדיוק עשינו.
ואנחנו גם צריכים לארגן מחדש 10 של קודם
כדי להצביע על 9 במקום להצביע על 13.
>> אז שוב, זה היה תרשים להתחיל עם.
זה היה השרשרת שלנו.
אנחנו צריכים לדלג מעל 13, אבל אנחנו צריכים גם לשמר
השלמות של הרשימה.
אנחנו לא רוצים לאבד את כל מידע בכל כיוון.
אז אנחנו צריכים לארגן מחדש המצביעים בזהירות
ולכן אנחנו לא לשבור את השרשרת בכל.
>> אז אנו יכולים לומר המצביע הבא של 9 מצביע לאותו המקום
כי של שלושה עשר הבא מצביע מצביע עכשיו.
כי אנחנו סופו של דבר הולך רוצה לדלג על 13.
אז בכל מקום בי 13 נקודות הבאות, ש רוצה תשע להצביע במקום שם.
אז זהו זה.
ולאחר מכן בכל מקום 13 נקודות בחזרה ל, כל מה שבא לפני 13,
אנחנו רוצים 10 להצביע שלבמקום 13.
עכשיו שמו לב, אם אתה מבין החיצים, אנחנו יכולים להוריד 13
מבלי לאבד את כל מידע.
אנחנו שמרנו על שלמות הרשימה, נע גם קדימה ואחורה.
ואז אנחנו יכולים רק סוג של לנקות אותו קצת
על ידי משיכת הרשימה יחד.
אז אנחנו מחדש מצביעים מכל צד.
ואז אנחנו משוחררים X צומת שהכילה 13,
ואנחנו לא לשבור את השרשרת.
אז עשינו טוב.
>> ההערה אחרונה כאן ברשימות מקושרות.
אז שני singly- וכפליים צמוד רשימות, כפי שראינו,
החדרה באמת יעילה תמיכה ומחיקה של אלמנטים.
אתה פחות או יותר יכול לעשות זה בזמן קבוע.
מה שאנחנו צריכים לעשות כדי למחוק אלמנט רק שנייה לפני?
עברנו מצביע אחד.
עברנו מצביע אחר.
אנחנו שחררתי X-- לקח שלושה ניתוחים.
זה תמיד לוקח שלושה ניתוחים ל למחוק node-- שלשחרר צומת.
>> איך להכניס?
ובכן, אנחנו פשוט תמיד tacking על תחילת
אם אנחנו מכניסים ביעילות.
אז אנחנו צריכים rearrange-- תלוי אם זה
singly- או כפול צמוד רשימה, שאולי צריך לעשות שלוש
או מקסימום ארבע פעולות.
אבל שוב, זה תמיד שלוש או ארבעה.
זה לא משנה כמה אלמנטים נמצאים ברשימה שלנו,
זה תמיד שלוש או ארבעה operations-- בדיוק כמו מחיקה היא תמיד
שלוש או ארבע פעולות.
זה זמן קבוע.
אז זה ממש נהדר.
>> עם מערכים, אנחנו עושים משהו כמו מיון הכנסה.
אתה בטח זוכר הכנסה ש סוג הוא לא אלגוריתם זמן קבוע.
זה בעצם די יקר.
אז זה הרבה יותר טוב להוספת.
אבל כפי שציינתי ב ביחידים צמודים וידאו רשימה,
יש לנו חסרון גם כאן, נכון?
איבדנו את היכולת באופן אקראי לגשת אלמנטים.
אנחנו לא יכולים להגיד, אני רוצה מספר אלמנט ארבעה או מספר אלמנט של 10 רשימה מקושרת
באותו אופן שאנחנו יכולים לעשות את זה עם מערך
או שאנחנו יכולים רק ישירות מדד לאלמנט של המערך שלנו.
>> וכך מנסה למצוא אלמנט בlist-- קשור
אם החיפוש הוא important-- אולי עכשיו ייקח זמן ליניארי.
כרשימה מתארכת, זה עלול לקחת צעד אחד נוסף
לכל אלמנט ברשימה ב כדי למצוא את מה שאנחנו מחפשים.
אז יש מחיקות סחר.
יש קצת פרו ואלמנט קון כאן.
>> ורשימות כפולים צמודות אינן סוג אחרון של שילוב מבנה נתונים
שנדברנו על, לוקח את כל הבניין הבסיסי
בלוקים של C לשים יחד.
כי למעשה, אנחנו יכולים אפילו לעשות יותר טוב מזה
כדי ליצור מבנה נתונים ש ייתכן שתוכל לחפש ב
גם בזמן קבוע.
אבל עוד על כך בוידאו אחר.
>> אני דאג לויד.
זה CS50.