שאלה במבני נתונים

[tamarhp]

למה לא?

הרי אם מחקתי איבר, אז עכשיו המצביע שבמקום ה-i במערך יצביע על איבר שלא קיים. לכן נצטרך שהאיבר במקום הi יצביע על האיבר הבא. ואז במקום הi+1 יצביע על הבא וכו' עד N!

 

[vinney]

פיספסת את כל הפואנטה ברשימה מקושרת

הוצאת איבר ברשימה מקושרת מתבצעת בO של 1.

 

[tamarhp]

בפורום שלנו המתרגל כתב

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

 

[tamarhp]

בעצם השאלה שלי היא כזו:

אם היה לי מערך A[1] = 3 A[2] = 4 A[3] = 5 ומחקתי את האיבר השני, אז עכשיו המערך יהיה A[1] = 3 A[2] = null A[3] = 5 >> (הוצאה של O(1) גם במערך רגיל, בלי להשתמש ברשימה מקושרת) או: A[1] = 3 A[2] = 5 >> (צמצום של המערך, וזה קורה גם במערך של מצביעים לרשימה מקושרת) ?

 

[vinney]

זה לא נכון

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

 

[tamarhp]

אז זה מחיקת תוכן, לא הוצאה!

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

 

[אדנדום]

ממערך פשוט אי אפשר להוציא איבר...