יצירת רשימה מקושרת בלי שימוש בcollections

[bdoron]

היום נשאלתי בראיון עבודה בjava לעשות רשימה מקושרת בלי שימוש בcollection

הייתי רוצה לקבל הצעות איך אתם הייתם מממשים את המחלקה הזאת ?

אני עשיתי את זה אם array רגיל, שאני מגדיר לו את הsize והtype של המערך הזה עשיתי אותו כאובייקט מסוג person למשל

מה דעתכם?

פתאום הבנתי שיש הרבה מקומות שבודקים לוגיקה שלי, אז אני צריך לדעת לממש הרבה דברים שjava או c# מוכנים

האם זה הדרך היחידה שעושים רשימה מקושרת בלי collections? או שיש עוד דרכים

אשמח אם יהיה פה הצעות לפיתרון...

[שניצל]

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

http://he.wikipedia.org/wiki/%D7%A8%D7%A9%D7%99%D7%9E%D7%94_%D7%9E%D7%A7%D7%95%D7%A9%D7%A8%D7%AA

מדובר בחומר בסיסי של מדעי המחשב (משהו שלומדים בתיכון).

[bdoron]

יואב אני יודע איך רשימה מקושרת עובדת, אני רק לא יודע איך מממשים את זה בלי list

אתה מתכוון שעושים struct? ולמה המרצה שלי פעם עשה את זה בarray רגיל, פשוט אמר לתת למערך גודל גדול..

[שניצל]

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

אם אתה רוצה דוגמה ב-#C אז חפש C# linked list implementation בגוגל.

[Gil28]

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

[bdoron]

אני זוכר שבהנדסאים היינו מממשים רשימה מקושרת בעזרת struct , זה אותו מימוש בסי שארפ או ג'אווה?

גם להשתמש בסטרק?

- - - תגובה אוחדה: - - -

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

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

סיבוכיות אני מכיר אבל אני לא יודע מה קשור לעובדה שמימשתי את זה במערך, אני לא מדבר על סיבוכיות פה אני מדבר על העובדה שלפי מה שהמרצה שלי עשה הוא לא מימש רשימה מקושרת, אלא מערך שהוא בדמוי רשימה מקושרת, ומה זה ADT?

[Gil28]

ADT = Abstract Data Type.

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

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

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

[bdoron]

הבנתי, בעיקרון אז אני יכול לממש את זה בstruct כמו בשפת סי , רק שאני יכול גם לערבב עם זה אובייקטים בתוך הnode

נכון?

ומה ההבדל בין class ל struct? זה יוצא אותו דבר? זאת אומרת ראיתי אנשים שמממשים את זה ויוצרים את הצומת באמצעות class וראיתי כאלה שבחרו לממש את הצומת באמצעות struct

מה עדיף , ובעצם מה יותר נכון?

[Gil28]

ב-java אין struct.

ב-C יש רק struct, ב-++C זה כמעט אותו דבר - struct זה class רק שהכל בברירת מחדל (אם לא ציינת במפורש) public לעומת private ב-class.

[bdoron]

c# גם יש, אז מה בעצם עדיף לי

[Gil28]

לא הבנתי את השאלה

[שניצל]

ב-#C יש הבדל משמעותי בין struct ו-class (בניגוד ל-++C, שם ההבדל הוא רק בנראות ברירת המחדל).

struct ב-#C הוא value type, כמו הטיפוסים הפרימיטיביים (int, bool וכו'). זה אומר כמה דברים:

א. הוא לא יכול להיות null, בניגוד ל-class.

ב. כשאתה מבצע השמה, אז זה מעתיק את התוכן של האובייקט, ולא רק את המצביע - כמו ב-++C.

בקיצור - אל תשתמש ב-struct ב-#C, אלא רק ב-class.