آرایه ها در مقابل فهرست های پیوندی
آرایه ها رایج ترین ساختار داده ای هستند که برای ذخیره مجموعه عناصر استفاده می شود. اکثر زبان های برنامه نویسی روش هایی را ارائه می دهند تا به راحتی آرایه ها و عناصر دسترسی به آرایه ها را اعلام کنند. لیست پیوندی، به‌طور دقیق‌تر فهرست پیوندی، یک ساختار داده‌ای است که می‌تواند برای ذخیره مجموعه‌ای از عناصر استفاده شود. از دنباله ای از گره ها تشکیل شده است و هر گره مرجعی به گره بعدی در دنباله دارد.
نشان داده شده در شکل 1، یک قطعه کد است که معمولاً برای اعلام و تخصیص مقادیر به یک آرایه استفاده می شود. شکل 2 نشان می دهد که یک آرایه در حافظه چگونه به نظر می رسد.
کد بالا آرایه‌ای را تعریف می‌کند که می‌تواند 5 عدد صحیح را ذخیره کند و با استفاده از شاخص‌های 0 تا 4 به آنها دسترسی پیدا می‌کند. یکی از ویژگی‌های مهم آرایه این است که کل آرایه به عنوان یک بلوک از حافظه اختصاص داده می‌شود و هر عنصر فضای مخصوص به خود را دارد. در آرایه هنگامی که یک آرایه تعریف می شود، اندازه آن ثابت می شود. بنابراین اگر در زمان کامپایل در مورد اندازه آرایه مطمئن نیستید، باید یک آرایه به اندازه کافی بزرگ برای قرار گرفتن در قسمت امن تعریف کنید. اما، بیشتر اوقات ما در واقع از تعداد عناصر کمتری نسبت به آنچه که اختصاص داده ایم استفاده می کنیم. بنابراین مقدار قابل توجهی از حافظه در واقع هدر می رود. از سوی دیگر، اگر "آرایه به اندازه کافی بزرگ" در واقع به اندازه کافی بزرگ نباشد، برنامه از کار می افتد.
یک لیست پیوندی حافظه را به عناصر خود به طور جداگانه در بلوک حافظه خود اختصاص می دهد و ساختار کلی با پیوند دادن این عناصر به عنوان پیوندهایی در یک زنجیره به دست می آید.هر عنصر در یک لیست پیوندی دارای دو فیلد است که در شکل 3 نشان داده شده است. فیلد داده، داده های ذخیره شده واقعی و فیلد بعدی ارجاع به عنصر بعدی در زنجیره را نگه می دارد. اولین عنصر لیست پیوندی به عنوان سر فهرست پیوندی ذخیره می شود.
| داده | بعدی |
شکل 3: عنصر یک لیست پیوندی
شکل 4 یک لیست پیوندی را با سه عنصر نشان می دهد. هر عنصر داده های خود را ذخیره می کند و همه عناصر به جز آخرین عنصر، مرجعی به عنصر بعدی ذخیره می کنند. آخرین عنصر یک مقدار null را در فیلد بعدی خود نگه می دارد. هر عنصر در لیست را می توان با شروع از سر و دنبال کردن نشانگر بعدی تا زمانی که عنصر مورد نیاز را برآورده کرد، قابل دسترسی است.
اگرچه آرایه‌ها و لیست‌های پیوندی مشابه هستند به این معنا که هر دوی آنها برای ذخیره مجموعه‌ای از عناصر استفاده می‌شوند، به دلیل استراتژی‌هایی که برای تخصیص حافظه به عناصر آن استفاده می‌کنند، دارای تفاوت‌هایی هستند. آرایه ها حافظه را به تمام عناصر خود به عنوان یک بلوک اختصاص می دهند و اندازه آرایه باید در زمان اجرا تعیین شود. این باعث می شود آرایه ها در موقعیت هایی که اندازه آرایه را در زمان کامپایل نمی دانید، ناکارآمد شوند. از آنجایی که یک لیست پیوندی حافظه را به طور جداگانه به عناصر خود اختصاص می دهد، در شرایطی که اندازه لیست را در زمان کامپایل نمی دانید بسیار کارآمد خواهد بود. اعلام و دسترسی به عناصر در یک لیست پیوندی در مقایسه با نحوه دسترسی مستقیم به عناصر در یک آرایه با استفاده از شاخص‌های آن ساده نیست.
