امروز میخوام در مورد تفاوت لیست و لینکد لیست ها باهاتون صحبت کنم .
با یه مثال خیلی ریز شروع میکنیم و کم کم میرسیم به تفاوت این دو تا موضوع جالبمون :)
فرض کنید با سه تا از دوستاتون تو سینما نشستید و دارید فیلم میبینید یه دفعه دوست دیگتون از راه میرسه و میخواد پیش شما بشینه اما کنار شما جا نیست که بشینه خب در این مواقع چیکار میکنید ؟
مجبور میشید جا به جا بشید تا دوستتونم پیش شما بشینه !
تفاوت اصلی لیست و لینکدلیست هم همینجا مطرح میشه ، یه لیست تو حافظه به صورت پیوسته ذخیره میشه به این معنی که عناصر در یک بلوک از حافظه ذخیره میشه ، به عکس زیر یه نگاهی بندازید :
اما لینکدلیست ها اینشکلی نیستند ، قبل اینکه بگم لینکدلیست ها چه جوری در حافظه ذخیره می شوند میخوام شما رو با شکل و شمایلشون اشنا کنم ، به عکس زیر یه نگاهی بندازید .:
همونطور که میبینید هر عنصر در یک لیست پیوندی یک Node شناخته میشه که هر Node از دو بخش تشکیل شده :
1 - Data
2 - Next
هر node در یک لیست پیوندی به نود دیگه در لیست اشاره میکنه پس اینجا next درواقع اشاره گر ماست .
حالا برگردیم به نحوه ی ذخیره شدنشون در حافظه ، ایتم ها در لیست پیوندی میتونند در هرجای حافظه ذخیره بشوند ، هر ایتم ادرس ایتم بعدی خودش رو حفظ میکنه برای همین هر ایتم میتونه در هرجایی از حافظه ذخیره بشه مثل لیست ها به صورت پیوسته در حافظه ذخیره نمیشوند .
فرض کنید شما میخوایید دنبال یه ادرس بگردید اطلاع دارید خونه ای که دنبالش میگردید در حوالی میدان A واقع شده است ، به میدان A میرید و اطلاع پیدا میکنید باید برای رسیدن به ادرس موردنظرتون برید به خیابان B بعد مراجعه به خیابان B مطلع میشید که باید به کوچه ی C مراجعه کنید . لیست های پیوندی هم همین مفهوم رو میرسونند !!!
همونطور که در شکل میبینید ایتم A به ایتم B اشاره میکنه پس ایتم A میدونه که ایتم بعدی در کجای حافظه قرار داره .
با استفاده از لیست های پیوندی شما میتونید ایتم هارو به راحتی ادد کنید چون اخرین نود ادرس نود بعدی رو نگه میداره !
تا اینجا تنها یکی از تفاوت ها رو متوجه شدیم که مربوط به ذخیره شدنشون در حافظه بود ، حالا میخوایم در مورد یکی از مهمترین تفاوت ها حرف بزنیم Time Complexity .
پیچیدگی زمانی لیست و لیست پیوندی رو میتونید در شکل زیر مشاهده کنید :
همونطور که دیدید پیچیدگی زمانی لیست پیوندی زمانی که ایتمی رو ادد کنیم O(1) اما پیچیدگی زمانی لیست ها O(n) هست. چرا ؟؟
چون برای لیست های پیوندی مهم نیست که اخرین ایتم کجای حافظه قرار داره و ایا بعد اخرین ایتم ، بلوک حافظه خالی هست تا ایتم بعدی رو ادد کنه یا نه . اخرین ایتم میاد به ایتمی که قراره به لیست ادد بشه اشاره میکنه و ادرس اون رو در حافظه حفظ میکنه به همین دلیل پیچیدگی زمانیش O(1) هست !
اما در لیست ها از اونجایی که به صورت پیوسته در حافظه ذخیره میشوند اگر بلوک حافظه خالی نبود باید المان هارو به بلوک حافظه ای منتقل کنند که جا برای ادد کردن ایتم جدید باشه برای همین پیچیدگی زمانیش O(n) . به همین راحتی !
امیدوارم که این موضوع رو به راحتی توضیح داده باشم تا مقاله ی بعدی به درود :)
References:
Grokking Algorithms Book
www.realpython.com
