آرایهها و لیستهای پیوندی
آرایهها و لیستهای پیوندی دو روش اساسی برای ذخیره یک دنباله مرتب از عناصر هستند: آرایهها آنها را در حافظه پیوسته برای دسترسی نمایه شده با زمان ثابت قرار میدهند، در حالی که لیستهای پیوندی آنها را از طریق اشارهگرها برای درج و حذف ارزان به هم متصل میکنند.
Definition
یک آرایه عناصر را در مکانهای حافظه پیوسته که با موقعیت نمایه شدهاند ذخیره میکند و امکان دسترسی تصادفی با زمان ثابت را فراهم میآورد؛ یک لیست پیوندی عناصر را در گرههای جداگانه ذخیره میکند که هر کدام یک ارجاع به گره بعدی (و احتمالاً قبلی) را نگه میدارند و امکان درج یا حذف با زمان ثابت را با داشتن یک ارجاع به گره فراهم میآورد.
Scope
این موضوع ساختارهای خطی و مبتنی بر دنباله و انواع داده انتزاعی ساخته شده بر روی آنها را پوشش میدهد — آرایههای ایستا و پویا، لیستهای پیوندی یکطرفه و دوطرفه، و ADTهای پشته و صف. این موضوع هزینههای دسترسی، درج و حذف آنها را مقایسه میکند، تغییر اندازه آرایه پویا و تحلیل مستهلک شده آن را پوشش میدهد، و پیامدهای چیدمان حافظه مانند محلیت کش را توضیح میدهد. این موضوع ساختارهای انجمنی و سلسله مراتبی را که تحت جداول هش و درختان جستجو پوشش داده میشوند، مستثنی میکند.
Core questions
- چه زمانی ذخیرهسازی پیوسته (آرایه) بهتر از ذخیرهسازی پیوندی با اشارهگر (لیست) عمل میکند؟
- چگونه یک آرایه پویا با وجود تغییر اندازه گاه به گاه، الحاق با زمان ثابت مستهلک شده را به دست میآورد؟
- مبادلات هزینه آرایهها در مقابل لیستهای پیوندی برای درج، حذف و دسترسی چیست؟
- پشتهها و صفها چگونه بر روی این ساختارها پیادهسازی میشوند؟
- چیدمان حافظه چگونه از طریق رفتار کش بر عملکرد واقعی تأثیر میگذارد؟
Key concepts
- حافظه پیوسته
- دسترسی نمایه شده
- تغییر اندازه آرایه پویا
- لیستهای پیوندی یکطرفه و دوطرفه
- پشتهها (LIFO)
- صفها (FIFO)
- هزینه مستهلک شده
- محلّیت کش
Key theories
- دسترسی تصادفی در مقابل پیوند ترتیبی
- آرایهها از دسترسی نمایه شده O(1) پشتیبانی میکنند اما درج یا حذف O(n) در وسط، در حالی که لیستهای پیوندی از اتصال O(1) با داشتن یک گره پشتیبانی میکنند اما دسترسی O(n) بر اساس موقعیت؛ انتخاب صحیح به ترکیب عملیات بستگی دارد.
- رشد مستهلک شده آرایههای پویا
- یک آرایه پویا که ظرفیت خود را در زمان پر شدن دو برابر میکند، کپیهای O(n) گاه به گاه انجام میدهد اما به O(1) به ازای هر الحاق در هر دنبالهای از عملیات، با روش تجمعی یا پتانسیل، مستهلک میشود.
Clinical relevance
آرایهها و لیستها زیربنای تقریباً هر برنامهای هستند: آرایههای پویا انواع لیست/بردار پیشفرض را در اکثر زبانها پیادهسازی میکنند، صفها زیربنای زمانبندی و جستجوی اول سطح هستند، پشتهها زیربنای مدیریت فراخوانی تابع و ارزیابی عبارت هستند، و مبادله آرایه در مقابل لیست یک تصمیم طراحی عملی معمول است که بر عملکرد تأثیر میگذارد.
History
آرایهها از اولین ساختارهای داده هستند که در اولین زبانهای برنامهنویسی وجود داشتند، و لیستهای پیوندی برای پردازش نمادین و لیست (به ویژه در IPL نیول، شاو و سایمون و بعدها لیسپ) در اواخر دهه ۱۹۵۰ معرفی شدند. بررسی سیستماتیک کنوت در «هنر برنامهنویسی کامپیوتر» تحلیل متعارف آنها را تثبیت کرد.
Key figures
- Donald Knuth
- Robert Sedgewick
Related topics
Seminal works
- knuth1997vol1
- cormen2009
Frequently asked questions
- چرا اگر آرایهها از دسترسی تصادفی سریع پشتیبانی میکنند، از لیست پیوندی استفاده کنیم؟
- لیستهای پیوندی امکان درج یا حذف را در زمان ثابت با داشتن یک ارجاع به یک گره فراهم میکنند، بدون جابجایی عناصر دیگر، کاری که آرایهها نمیتوانند در وسط انجام دهند. آنها زمانی مفید هستند که دنباله به طور مکرر تغییر میکند و دسترسی تصادفی موقعیتی مورد نیاز نیست.
- چرا الحاق آرایه با زمان ثابت در نظر گرفته میشود در حالی که تغییر اندازه همه چیز را کپی میکند؟
- تغییر اندازه به ندرت اتفاق میافتد زیرا ظرفیت معمولاً دو برابر میشود، بنابراین کل کار کپی در طول n الحاق متناسب با n است. با توزیع این کار بر روی تمام الحاقها، این امر یک هزینه ثابت مستهلک شده به ازای هر الحاق را فراهم میکند، حتی اگر تغییر اندازههای فردی O(n) باشند.