Data Structures - Linked List

Introتوی این قسمت از سری ساختار داده میخوام درباره ی لینک لیست صحبت کنم. بر خلاف آرایه ها که به random-access بودن مشهورن و آیتم ها توی مموری کنار هم قرار میگیرن لینک لیست ها از نود های جدا از هم تشکیل شدن و با pointer به هم وصل میشن.Array vs Linked ListLet's go deeper!معمولا آرایه جزو اولین ساختار داده هایی هست که باهاش آشنا میشین چون تو اکثر زبان ها وجود دارن. توی آرایه شما میتونین با ایندکس به آیتم ها دسترسی داشته باشین و نیاز نیست حتما iterate کنین. توی لینک لیست شما به هیچ عنوان نمیتونین به یک آیتم بصورت مستقیم اشاره کنین (‌ مثلا با ایندکس )‌ و برای اینکه به یک آیتم خاص برسین باید اصطلاحا از Head شروع کنین و iterate کنین. منظور از Head همون اولین نود هست. دقیق تر بخواییم بررسی کنیم شما زمانی که آیتمِ وسطِ یک آرایه رو حذف میکنین (یا اضافه کنین) ایندکس ها تغییر میکنین و همین باعث میشه O(n) رو داشته باشه چون بسته به طول آرایه بقیه آیتم ها باید جاشون تغییر کنه. توی لینک لیست عملیات اضافه و حذف کردن O(1) رو دارن و چرا؟‌ چون همه ی نود ها به هم لینک شدن و اصلا اهمیتی نداره کجا مموری قرار دارن و در این صورت مثلا اگه بخواییم یک آیتم رو به هر جای لیست اضافه کنیم فقط کافیه با لینک کردن نود ها با هم سر و کار داشته باشیم. بریم سراغ تخته سیاه :)حذف یک آیتم از آرایههمونطور که میبینین بعد از اینکه Item 3 رو حذف کردم، Item 4 مجبور شد بیاد تو ایندکس ۲ و حالا فرض کن آرایت چند هزار تا آیتم داشته باشه :) بیاین ببینم تو لینک لیست چه اتفاقی میوفته!چه باحال، توی لینک لیست برای حذف item 3 بدون هیچ عملیات اضافه ای فقط item 2 به item 4 لینک شد و همینطور که معلومه از آرایه ها بهینه تر هست.لطفا این نکته رو در نظر داشته باشین که هر ساختار داده ای یکجا کاربرد داره و اینکه من دارم آرایه ها رو با لینک لیست مقایسه میکنم صرفا برای اینه که شما بهتر درکش کنین. اگه بخوام صادق باشم خودم تاحالا نیاز نشده بخوام از لینک لیست ها استفاده کنم :)Types of Linked listلینک لیست ها معمولا به یک شکل نیستن و انواع مختلفی دارن. چیزی که من براتون توضیح دادم اصطلاحا Singly Linked-List هستن که یعنی کی طرفه ان (یک نود فقط به نود بعدیش لینک شده). Doubly Linked-List ها به لینک لیست هایی گفته میشن که یک نود هم به نود بعدی لینک شده و هم به نود قبلی :) و در آخر یک نوع مشهور دیگه هست که به Circular Linked-List ها مشهورن که یعنی آخرین نود (tail) همیشه به اولین نود (head) لینک شده (یک ساختار دایره ای رو فرض کنین).Let's codeبیاین یک لینک لیست بنویسیم یا دقیق ترش یک singly linked-list تا بفهمیم دقیقا داستان چیه :) هرچند که من تصمیم دارم با جاوااسکریپت بنویسم اما اگه برنامه نویسی رو درک کرده باشین این نباید براتون مسئله ی خاصی باشه ( زبان های برنامه نویسی صرفا یکسری ابزار هستن ).اول از همه ما به یک نود احتیاج داریم که بتونه یک مقدار تو خودش ذخیره کنه و ریفرنسِ نودِ بعدی رو تو خودش داشته باشه.Node Classحالا یک کلاس احتیاج داریم که Head رو تو خودش نگه داره و همچنین عملیات حذف و اضافه کردن رو انجام بده. Linked List Classبیاین اول یک متد برای اضافه کردن آیتم به لیستمون بنویسیم. روند کار به این صورته که باید از Head شروع کنیم و خودمون رو به آخر لیست برسونیم (‌ هروقت next مقدار null داشته باشه یعنی نود دیگه ای وجود نداره ) و یک نود جدید به آخرین نود لینک کنیم.Add a new item to linked listو حالا یک متد نیاز داریم برای حذف یک آیتم. برای اینکار ما به نود قبل و بعدِ نودی که میخواییم حذف کنیم احتیاج داریم تا این دوتارو لینک کنیم به همدیگه. ًRemove an item from linked listو در آخر به یک متد نیاز داریم تا آیتم های لیستمون رو برامون پرینت کنه.Print itemsخیلی متد های متنوعی میشه نوشت که خودتون میتونین بر اساس نیازتون بنویسین و اگه از کدهایی که زدم چیزی سر در نمیارین ایرادی نداره‌، سعی کنین خودتون هم بنویسین و باهاش کار کنین تا دستتون بیاد. یک توصیه ی دیگه ای که دارم اینه که روی کاغذ بکشین لینک لیستتون رو،‌ اینجوری قشنگ میفهمین کجای کارین.Performanceبرای اینکه از نظر بهینه بودن لینک لیست هارو بررسی کنیم بیاین از دسترسی به آیتم ها حرف بزنیم. برخلاف آرایه برای دسترسی به یک آیتم (نود) توی لینک لیست مجبورم از Head شروع کنم و تا جایی که لازم باشه iterate کنم و از این نظر O(n) رو خواهیم داشت.اما برای حذف و اضافه کردن چی؟ لینک لیست برای این دوتا عملیات خیلی بهینه هست و O(1) رو داره. همونطور که دیدیم فقط با لینک کردن میشه یک آیتم به لیست اضافه کرد یا حذف کرد.لینک لیست ها یک مزیت دیگه ای هم دارن اگه دقت کرده باشین محدودیتی از نظر طول ندارن. حتی لازم به resize کردن هم نیست (تو زبان های سطح پایین آرایه ها طولی از قبل تعریف شده دارن) که خب از این نظر هم هرچقدر هم سایز لینک لیست تغییر کنه نیاز به عملیات خاصی نیست و O(1) رو داره. و در آخر برای ساختار داده هایی مثل Queue و Stack از لینک لیست استفاده میشه که تو نوشته های بعدیم دربارشون حرف میزنم.Endبازم به آخر داستان رسیدیم :) امیدوارم این مقاله هم براتون مفید بوده باشه. توصیه همیشگیم اینه که خودتون درباره ی چیزها بخونین و سرچ کنین. هیچ مقاله یا منبع مشخصی همیشه کامل نبوده و نیست. موفق باشین!Google Data Structurehttps://www.freecodecamp.org/news/how-linked-lists-work/https://www.youtube.com/watch?v=Hj_rA0dhr2I&amp;pp=ygULbGlua2VkIGxpc3Q%3D