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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

הרשימה מורכבת מחוליות. כל חוליה נראית כך:

# A data structure that describes a link which has a value, and can
#	be connected to a following and previous link.
Link
	# The next Link.
1	next
	# The value at this link.
2	value

להלן הפסוודו-קוד לרשימה עצמה:

# A data structure that describes a (doubly-linked) list of values.
List
        # The leftmost link.
1      front
        # The size (number of links).
2      size

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

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