شما از لیستهای پیوندی استفاده نمیکنید، اما آنها نیمی از نرمافزار شما را اجرا میکنند.
احتمالاً هرگز در یک پروژه جاوااسکریپت عملیاتی (production)، یک لیست پیوندی نخواهید نوشت. آرایههای داخلی زبان شما، تغییر اندازه پویا را سریعتر مدیریت میکنند. مصاحبهکنندگان به شما یاد میدهند که آنها را روی تختهسفید رسم کنید، اما این کار یک مدل ذهنی اشتباه ایجاد میکند.
شما نباید لیستهای پیوندی را صرفاً برای پیادهسازی کردنشان یاد بگیرید. شما آنها را یاد میگیرید تا ابزارهایی را که هر روز استفاده میکنید، درک کنید.
آنها همهجا هستند: • دکمههای عقب و جلو در مرورگر. • تاریخچه Undo در ویرایشگرهای متن. • کشهای LRU در وبسرورها و پایگاههای داده. • دستورات لیست در Redis. • زمانبند فرآیند (process scheduler) در هسته لینوکس.
آنها آثار باستانی نیستند؛ آنها زیرساخت هستند.
دلیل اصلی ضعف لیستهای پیوندی، عدم محلیسازی حافظه پنهان (cache locality) است. پردازنده شما رم (RAM) را تکتک بایتها نمیخواند؛ بلکه یک قطعه ۶۴ بایتی به نام cache line را فراخوانی میکند.
آرایهها سریع هستند چون در حافظه در کنار هم قرار میگیرند. پردازنده اولین عنصر را میخواند و ۱۵ عنصر بعدی را به صورت رایگان دریافت میکند.
لیستهای پیوندی این مزیت را از بین میبرند. هر گره (node) در نقطه متفاوتی از حافظه قرار دارد. دنبال کردن یک اشارهگر (pointer)، پردازنده را مجبور میکند به آدرس جدیدی بپرد. این کار باعث یک فراخوانی جدید از رم میشود که صدها چرخه پردازنده (CPU cycles) هزینه دارد.
در سختافزارهای مدرن، پیمایش آرایه میتواند ۱۰ تا ۱۰۰ برابر سریعتر از پیمایش لیست پیوندی باشد. نمادگذاری Big-O این هزینه ثابت را نادیده میگیرد.
پس چه زمانی از آنها استفاده میکنیم؟
از یک لیست پیوندی تکگوشته (singly linked list) برای پشتهها (stacks) یا صفهای وظایف ساده استفاده کنید، جایی که فقط از یک طرف اضافه یا حذف میکنید.
زمانی که به حذف با پیچیدگی O(1) از طریق ارجاع مستقیم به گره نیاز دارید، از یک لیست پیوندی دوگوشته (doubly linked list) استفاده کنید. این رازِ کش LRU است.
یک کش LRU به موارد زیر نیاز دارد:
- جستجو (lookup) با پیچیدگی O(1).
- درج (insertion) با پیچیدگی O(1).
- حذف (eviction) با پیچیدگی O(1).
- ارتقا (promotion) با پیچیدگی O(1).
یک آرایه نمیتواند این کار را انجام دهد، زیرا جابهجایی آیتمها مستلزم جابهجا کردن تمام موارد دیگر است. یک هشمپ (hash map) به تنهایی هم نمیتواند این کار را انجام دهد زیرا ترتیب خاصی ندارد.
راه حل، استفاده از ترکیبی از آنهاست. یک هشمپ قابلیت جستجو را فراهم میکند و یک لیست پیوندی دوگوشته ترتیب را حفظ میکند. هشمپ ارجاع به گره را ذخیره میکند. وقتی به یک کلید دسترسی پیدا میکنید، گره را مستقیماً از لیست برمیدارید و به ابتدای لیست منتقل میکنید. بدون جستجو. بدون جابهجایی.
یادگیری ساختارهای داده را فقط برای موفقیت در مصاحبهها متوقف کنید. آنها را یاد بگیرید تا بفهمید نرمافزار چگونه با سختافزار تعامل دارد.
Source: https://dev.to/islamhafez0/you-dont-use-linked-lists-but-theyre-running-half-your-software-4b37