فهرست پیوندی منفرد در مقابل فهرست پیوندی دوگانه
لیست پیوندی یک ساختار داده خطی است که برای ذخیره مجموعه ای از داده ها استفاده می شود. یک لیست پیوندی حافظه را به عناصر خود به طور جداگانه در بلوک حافظه خود اختصاص می دهد و ساختار کلی با پیوند دادن این عناصر به عنوان پیوندهایی در یک زنجیره به دست می آید. یک لیست پیوندی منفرد از دنباله ای از گره ها تشکیل شده است و هر گره مرجعی به گره بعدی در دنباله دارد. یک لیست دارای پیوند دوگانه شامل دنباله ای از گره ها است که در آن هر گره حاوی ارجاع به گره بعدی و همچنین به گره قبلی است.
فهرست پیوندی مجرد
هر عنصر در یک لیست پیوندی منفرد دارای دو فیلد همانطور که در شکل 1 نشان داده شده است. اولین عنصر لیست پیوندی به عنوان سر فهرست پیوندی ذخیره می شود.
شکل 2 یک لیست پیوندی منفرد را با سه عنصر نشان می دهد. هر عنصر داده های خود را ذخیره می کند و همه عناصر به جز آخرین عنصر، مرجعی به عنصر بعدی ذخیره می کنند. آخرین عنصر یک مقدار null را در فیلد بعدی خود نگه می دارد. با شروع از سر و دنبال کردن نشانگر بعدی تا رسیدن به عنصر مورد نیاز، می توان به هر عنصری در لیست دسترسی داشت.
فهرست پیوندی دوگانه
هر عنصر در یک لیست دارای پیوند دوگانه دارای سه فیلد است که در شکل 3 نشان داده شده است.مانند لیست پیوندهای منفرد، فیلد داده اطلاعات واقعی ذخیره شده را در خود نگه می دارد و فیلد بعدی ارجاع به عنصر بعدی در زنجیره را نگه می دارد. علاوه بر این، فیلد قبلی ارجاع به عنصر قبلی در زنجیره را نگه می دارد. اولین عنصر لیست پیوندی به عنوان سر فهرست پیوندی ذخیره می شود.
شکل 4 یک لیست دوگانه با سه عنصر را نشان می دهد. تمام عناصر میانی ارجاع به عناصر اول و قبلی را ذخیره می کنند. آخرین عنصر در لیست یک مقدار null را در فیلد بعدی خود و اولین عنصر در لیست مقدار null را در قسمت قبلی خود نگه می دارد. فهرست پیوندی دوگانه را می توان با دنبال کردن مراجع بعدی در هر عنصر به جلو و به طور مشابه با استفاده از مراجع قبلی در هر عنصر به عقب پیمایش کرد.
تفاوت بین فهرست پیوندی تکی و فهرست پیوندی دوگانه چیست؟
هر عنصر در لیست پیوندهای منفرد حاوی ارجاع به عنصر بعدی در لیست است، در حالی که هر عنصر در لیست پیوند دوگانه حاوی ارجاعاتی به عنصر بعدی و همچنین عنصر قبلی در لیست است. لیست های دارای پیوند دوگانه به فضای بیشتری برای هر عنصر در لیست نیاز دارند و عملیات ابتدایی مانند درج و حذف پیچیده تر است زیرا آنها باید با دو مرجع سروکار داشته باشند. اما لیست‌های پیوند مضاعف امکان دستکاری آسان‌تر را فراهم می‌کنند، زیرا امکان پیمایش فهرست در جهت‌های جلو و عقب را فراهم می‌کند.
