فهرست پیوندی

{linked list} [رایانه و فنّاوری اطلاعات] فهرستی از اقلام داده ای که هریک از آنها دارای شناسه ای برای تعیین جای هر قلم داده در فهرست باشد

فهرستی از اقلام داده‏ای که هریک از آنها دارای شناسه‏ای برای تعیین جای هر قلم داده در فهرست باشد.

💡 مزیت مهم فهرست پیوندی نسبت به آرایه‌ها این است که ترتیب قرار گرفتن داده‌ها در آن با ترتیب قرار گرفتن آن‌ها در حافظه متفاوت است. به همین دلیل فهرست پیوندی دارای این ویژگی است که درج و حذف گره‌ها در هر نقطه‌ای از فهرست، با تعداد ثابتی از عملیات امکان‌پذیر است.

💡 فهرست پیوندی یا لیست پیوندی (به انگلیسی: Linked list) ساختاری شامل دنباله‌ای از عناصر است که هر عنصر دارای اشاره‌گری به عنصر بعدی در دنباله است. فهرست پیوندی از جملهٔ ساده‌ترین و رایج‌ترین داده‌ساختارها است و در پیاده‌سازی از داده‌ساختارها پشته (Stack)، صف (Queue) و جدول درهم‌سازی (Hash table) استفاده می‌شود.

💡 معمولاً در آخرین عنصر یک فهرست، فیلد اشاره گر اشاره گری به null است. null در زبان‌های برنامه‌نویسی به معنای عدم وجود یک عنصر است. این نوع فهرست، فهرست خطی نامیده می‌شود. در نوع دیگری از فهرست پیوندی، اشاره گر عنصر آخر به عنصر اول فهرست اشاره می‌کند. به این نوع فهرست، فهرست پیوندی دایره‌ای می‌گویند.

💡 پیاده‌سازی فهرست خود سازمان، دقیقاً مشابه فهرست پیوندی است و تمام توابع در هر دو یکسان اند و تنها تفاوت موجود میان این دو فهرست در نحوهٔ قرار گرفتن عناصر است که ترتیب عناصر در فهرست خودسازمان‌دهنده همان‌طور که بیان شد بر اساس احتمال دسترسی عناصر است.

💡 فهرست پیوندی باز شده(unrolled linked list) نوعی فهرست پیوندی است که هر گره آن شامل آرایه‌ای از داده‌ها است. این ساختار باعث افزایش کارایی حافظه نهان می‌شود؛ زیرا تعداد بیشتری از عناصر فهرست در حافظه پشت سر هم قرار می‌گیرند و سر جمع حافظه کاهش می‌یابد؛ زیرا فراداده کمتری باید برای هر عنصر فهرست ذخیره شود.

💡 در یک فهرست پیوندی دایره‌ای همه گره‌ها در یک دایره پیوسته به هم پیوند دارند. اشاره گر عنصر آخر فهرست به عنصر ابتدای آن اشاره دارد. برای داده ساختاری مانند صف، با داشتن اشاره گری به عنصر آخر فهرست، عناصر می‌توانند از آخر در فهرست درج شوند و از ابتدای فهرست حذف شوند.