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

java cast int למחרוזת

מהו מערך?

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

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

הצהרת מערך

ניתן להכריז על מערך כ:

 data_type name of the array[no of elements] 

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

בואו נבין דרך דוגמה.

 int a[5]; 

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

מהי רשימה מקושרת?

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

הבדלים בין מערך לרשימה מקושרת

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

1. עלות גישה לאלמנט

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

מיון בועות באלגוריתם

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

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

2. עלות הכנסת אלמנט

יכולים להיות שלושה תרחישים בהוספה:

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

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

הכנסת אלמנט בסוף

אם המערך אינו מלא, אז נוכל להוסיף ישירות את האלמנט החדש דרך האינדקס. במקרה זה, מורכבות הזמן תהיה קבועה, כלומר, O(1). אם המערך מלא, ראשית עלינו להעתיק את המערך למערך אחר ולהוסיף אלמנט חדש. במקרה זה, מורכבות הזמן תהיה O(n).

כדי להוסיף אלמנט בסוף הרשימה המקושרת, עלינו לעבור את כל הרשימה. אם הרשימה המקושרת מורכבת מ-n אלמנטים, אז מורכבות הזמן תהיה O(n).

הכנסת אלמנט באמצע

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

פקודת sed

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

הרשימה המקושרת שנוצרה היא:

קלות שימוש

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

דינמי בגודל

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

3. דרישות זיכרון

כפי שהאלמנטים במערך מאחסנים בבלוק אחד רציף של זיכרון, כך המערך הוא בגודל קבוע. נניח שיש לנו מערך בגודל 7, והמערך מורכב מ-4 אלמנטים ואז שאר החלל אינו בשימוש. הזיכרון שנכבש על ידי 7 האלמנטים:

שטח זיכרון = 7*4 = 28 בתים

כאשר 7 הוא מספר האלמנטים במערך ו-4 הוא מספר הבתים מסוג מספר שלם.

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

מנהל אינטרנט

שטח זיכרון = 8*4 = 32 בתים

הרשימה המקושרת תהיה בחירה טובה יותר אם חלק הנתונים גדול יותר בגודלו. נניח שהנתונים הם של 16 בתים. שטח הזיכרון שתפוס על ידי המערך יהיה 16*7=112 בתים בעוד שהרשימה המקושרת תופסת 20*4=80, כאן ציינו 20 בתים כ-16 בתים עבור גודל הנתונים ועוד 4 בתים עבור משתנה המצביע. אם אנו בוחרים בגודל גדול יותר של נתונים, אזי הרשימה המקושרת תצרוך פחות זיכרון; אחרת, זה תלוי בגורמים שאנו מאמצים כדי לקבוע את הגודל.

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