توی این قسمت از سری ساختار داده میخوام درباره ی لینک لیست صحبت کنم. بر خلاف آرایه ها که به random-access بودن مشهورن و آیتم ها توی مموری کنار هم قرار میگیرن لینک لیست ها از نود های جدا از هم تشکیل شدن و با pointer به هم وصل میشن.
معمولا آرایه جزو اولین ساختار داده هایی هست که باهاش آشنا میشین چون تو اکثر زبان ها وجود دارن. توی آرایه شما میتونین با ایندکس به آیتم ها دسترسی داشته باشین و نیاز نیست حتما iterate کنین. توی لینک لیست شما به هیچ عنوان نمیتونین به یک آیتم بصورت مستقیم اشاره کنین ( مثلا با ایندکس ) و برای اینکه به یک آیتم خاص برسین باید اصطلاحا از Head شروع کنین و iterate کنین. منظور از Head همون اولین نود هست.
دقیق تر بخواییم بررسی کنیم شما زمانی که آیتمِ وسطِ یک آرایه رو حذف میکنین (یا اضافه کنین) ایندکس ها تغییر میکنین و همین باعث میشه O(n) رو داشته باشه چون بسته به طول آرایه بقیه آیتم ها باید جاشون تغییر کنه. توی لینک لیست عملیات اضافه و حذف کردن O(1) رو دارن و چرا؟ چون همه ی نود ها به هم لینک شدن و اصلا اهمیتی نداره کجا مموری قرار دارن و در این صورت مثلا اگه بخواییم یک آیتم رو به هر جای لیست اضافه کنیم فقط کافیه با لینک کردن نود ها با هم سر و کار داشته باشیم. بریم سراغ تخته سیاه :)
همونطور که میبینین بعد از اینکه Item 3 رو حذف کردم، Item 4 مجبور شد بیاد تو ایندکس ۲ و حالا فرض کن آرایت چند هزار تا آیتم داشته باشه :) بیاین ببینم تو لینک لیست چه اتفاقی میوفته!
چه باحال، توی لینک لیست برای حذف item 3 بدون هیچ عملیات اضافه ای فقط item 2 به item 4 لینک شد و همینطور که معلومه از آرایه ها بهینه تر هست.
لطفا این نکته رو در نظر داشته باشین که هر ساختار داده ای یکجا کاربرد داره و اینکه من دارم آرایه ها رو با لینک لیست مقایسه میکنم صرفا برای اینه که شما بهتر درکش کنین. اگه بخوام صادق باشم خودم تاحالا نیاز نشده بخوام از لینک لیست ها استفاده کنم :)
لینک لیست ها معمولا به یک شکل نیستن و انواع مختلفی دارن. چیزی که من براتون توضیح دادم اصطلاحا Singly Linked-List هستن که یعنی کی طرفه ان (یک نود فقط به نود بعدیش لینک شده). Doubly Linked-List ها به لینک لیست هایی گفته میشن که یک نود هم به نود بعدی لینک شده و هم به نود قبلی :) و در آخر یک نوع مشهور دیگه هست که به Circular Linked-List ها مشهورن که یعنی آخرین نود (tail) همیشه به اولین نود (head) لینک شده (یک ساختار دایره ای رو فرض کنین).
بیاین یک لینک لیست بنویسیم یا دقیق ترش یک singly linked-list تا بفهمیم دقیقا داستان چیه :) هرچند که من تصمیم دارم با جاوااسکریپت بنویسم اما اگه برنامه نویسی رو درک کرده باشین این نباید براتون مسئله ی خاصی باشه ( زبان های برنامه نویسی صرفا یکسری ابزار هستن ).
اول از همه ما به یک نود احتیاج داریم که بتونه یک مقدار تو خودش ذخیره کنه و ریفرنسِ نودِ بعدی رو تو خودش داشته باشه.
حالا یک کلاس احتیاج داریم که Head رو تو خودش نگه داره و همچنین عملیات حذف و اضافه کردن رو انجام بده.
بیاین اول یک متد برای اضافه کردن آیتم به لیستمون بنویسیم. روند کار به این صورته که باید از Head شروع کنیم و خودمون رو به آخر لیست برسونیم ( هروقت next مقدار null داشته باشه یعنی نود دیگه ای وجود نداره ) و یک نود جدید به آخرین نود لینک کنیم.
و حالا یک متد نیاز داریم برای حذف یک آیتم. برای اینکار ما به نود قبل و بعدِ نودی که میخواییم حذف کنیم احتیاج داریم تا این دوتارو لینک کنیم به همدیگه.
و در آخر به یک متد نیاز داریم تا آیتم های لیستمون رو برامون پرینت کنه.
خیلی متد های متنوعی میشه نوشت که خودتون میتونین بر اساس نیازتون بنویسین و اگه از کدهایی که زدم چیزی سر در نمیارین ایرادی نداره، سعی کنین خودتون هم بنویسین و باهاش کار کنین تا دستتون بیاد. یک توصیه ی دیگه ای که دارم اینه که روی کاغذ بکشین لینک لیستتون رو، اینجوری قشنگ میفهمین کجای کارین.
برای اینکه از نظر بهینه بودن لینک لیست هارو بررسی کنیم بیاین از دسترسی به آیتم ها حرف بزنیم. برخلاف آرایه برای دسترسی به یک آیتم (نود) توی لینک لیست مجبورم از Head شروع کنم و تا جایی که لازم باشه iterate کنم و از این نظر O(n) رو خواهیم داشت.
اما برای حذف و اضافه کردن چی؟ لینک لیست برای این دوتا عملیات خیلی بهینه هست و O(1) رو داره. همونطور که دیدیم فقط با لینک کردن میشه یک آیتم به لیست اضافه کرد یا حذف کرد.
لینک لیست ها یک مزیت دیگه ای هم دارن اگه دقت کرده باشین محدودیتی از نظر طول ندارن. حتی لازم به resize کردن هم نیست (تو زبان های سطح پایین آرایه ها طولی از قبل تعریف شده دارن) که خب از این نظر هم هرچقدر هم سایز لینک لیست تغییر کنه نیاز به عملیات خاصی نیست و O(1) رو داره.
و در آخر برای ساختار داده هایی مثل Queue و Stack از لینک لیست استفاده میشه که تو نوشته های بعدیم دربارشون حرف میزنم.
بازم به آخر داستان رسیدیم :) امیدوارم این مقاله هم براتون مفید بوده باشه. توصیه همیشگیم اینه که خودتون درباره ی چیزها بخونین و سرچ کنین. هیچ مقاله یا منبع مشخصی همیشه کامل نبوده و نیست. موفق باشین!
https://www.freecodecamp.org/news/how-linked-lists-work/
https://www.youtube.com/watch?v=Hj_rA0dhr2I&pp=ygULbGlua2VkIGxpc3Q%3D
