موضوع مقاله: لیست پیوندی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # لیست پیوندی | مقدمه: فهرست پیوندی یا لیست پیوندی ساختاری شامل دنباله‌ای از عناصر است که هر عنصر دارای اشاره‌گری به عنصر بعدی در دنباله است. | ## بخش 1: لیست پیوندی | مزیت مهم فهرست پیوندی نسبت به آرایه‌ها این است که ترتیب قرار گرفتن داده‌ها در آن با ترتیب قرار گرفتن آن‌ها در حافظه متفاوت است. به همین دلیل فهرست پیوندی دارای این ویژگی است که درج و حذف گره‌ها در هر نقطه‌ای از فهرست، با تعداد ثابتی از عملیات امکان‌پذیر است. از طرف دیگر فهرست پیوندی اجازه دستیابی تصادفی به داده یا هرگونه اندیس‌گذاری را نمی‌دهد. در نتیجه بسیاری از اعمال ابتدایی نظیر به دست آوردن آخرین عنصر فهرست، پیدا کردن عنصر شامل داده مورد نظر، یا مشخص کردن مکان درج یک عنصر جدید ممکن است نیازمند بررسی اکثر عناصر فهرست باشد. فهرست دایره‌ای و فهرست خطی معمولاً در آخرین عنصر یک فهرست، فیلد اشاره گر اشاره گری به null است. فهرست دوپیوندی در یک فهرست دوپیوندی، هرگره علاوه بر اشاره‌گری به عنصر بعدی دارای اشاره‌گری به عنصر قبلی خود نیز می‌باشد. سنجش فهرست پیوندی فهرست‌های خطی پیوندی در مقایسه با سایر فهرست‌ها با وجود آن‌که فهرست‌های پیوندی دوسویه و حلقوی نسبت به فهرست‌های پیوندی خطی یک‌سویه مزایایی دارند، فهرست‌های خطی نیز دارای مزایایی هستند که در برخی موقعیت‌ها آن‌ها را به گزینه‌ای ترجیح‌دادنی تبدیل می‌کند. یک فهرست پیوندی خطی یک‌سویه، یک ساختار دادهٔ بازگشتی است، زیرا شامل اشاره‌گری به یک شیء کوچک‌تر از همان نوع خود است. به همین دلیل، بسیاری از عملیات روی فهرست‌های پیوندی خطی یک‌سویه (مانند ادغام دو فهرست یا پیمایش عناصر به ترتیب معکوس) معمولاً دارای الگوریتم‌های بازگشتی بسیار ساده‌ای هستند که از هر راه‌حل مبتنی بر دستورات تکراری ساده‌ترند. اگرچه این راه‌حل‌های بازگشتی را می‌توان برای فهرست‌های پیوندی دوسویه و حلقوی نیز تطبیق داد، اما این کار معمولاً به آرگومان‌های اضافی و شرایط پایهٔ پیچیده‌تری نیاز دارد. فهرست‌های پیوندی خطی یک‌سویه همچنین امکان اشتراک دُم (tail-sharing) را فراهم می‌کنند؛ یعنی استفاده از یک بخش پایانی مشترک به‌عنوان انتهای دو فهرست متفاوت. به‌طور خاص، اگر یک گرهٔ جدید به ابتدای یک فهرست اضافه شود، فهرست قبلی همچنان به‌عنوان دُم فهرست جدید در دسترس باقی می‌ماند. این قابلیت در سایر گونه‌ها وجود ندارد؛ زیرا یک گره هرگز نمی‌تواند هم‌زمان به دو فهرست حلقوی یا دوسویهٔ متفاوت تعلق داشته باشد. مزایای گونه‌های پیشرفته‌تر اغلب به پیچیدگی الگوریتم‌ها محدود می‌شود و الزاماً به معنای کارایی بیشتر نیست. به‌ویژه، یک فهرست حلقوی معمولاً می‌تواند با استفاده از یک فهرست خطی به‌همراه دو متغیر که به اولین و آخرین گره اشاره می‌کنند، و بدون هزینهٔ اضافی، شبیه‌سازی شود. فهرست دوپیوندی در مقابل فهرست تک‌پیوندی فهرست دوپیوندی برای هر گره به فضای بیشتری نیاز دارد و انجام عملیات اصلی بر روی آن هزینهٔ بیشتری دارد. با این حال، مدیریت این نوع فهرست ساده‌تر است، زیرا امکان دسترسی ترتیبی به عناصر را در هر دو جهت فراهم می‌کند. برای مثال، تنها با در اختیار داشتن نشانی یک گره می‌توان با تعداد ثابتی از عملیات، آن گره را در فهرست درج یا از آن حذف کرد. برای انجام همین عملیات در یک فهرست تک‌پیوندی، نشانی گرهٔ قبلی نیز مورد نیاز است. | ## بخش 2: لیست پیوندی | فهرست حلقوی در مقابل فهرست خطی یک فهرست پیوندی حلقوی می‌تواند گزینه‌ای مناسب برای نمایش آرایه‌ها یا مجموعه‌هایی باشد که ذاتاً ساختاری حلقوی دارند؛ برای مثال، گوشه‌های یک چندضلعی، مجموعه‌ای از بافرها که به ترتیب FIFO («اولین ورودی، اولین خروجی») مورد استفاده قرار گرفته و آزاد می‌شوند، یا مجموعه‌ای از فرایندها که باید به‌صورت گردشی (round-robin) زمان‌بندی شوند. در این کاربردها، یک اشاره‌گر به هر گره می‌تواند به‌عنوان دسترسی (handle) به کل فهرست عمل کند. در یک فهرست حلقوی، اشاره‌گر به آخرین گره امکان دسترسی آسان به اولین گره را نیز فراهم می‌کند، زیرا با دنبال کردن تنها یک پیوند می‌توان به ابتدای فهرست رسید. ازاین‌رو، در کاربردهایی که نیازمند دسترسی به هر دو انتهای فهرست هستند (برای نمونه، در پیاده‌سازی صف)، ساختار حلقوی اجازه می‌دهد که کل فهرست تنها با یک اشاره‌گر مدیریت شود، نه با دو اشاره‌گر جداگانه. یک فهرست حلقوی را می‌توان در زمان ثابت به دو فهرست حلقوی تقسیم کرد، به شرط آن‌که نشانی آخرین گرهٔ هر بخش مشخص باشد. انجام همین عملیات روی هر دو گره از دو فهرست مجزا، باعث اتصال آن دو فهرست و تشکیل یک فهرست واحد می‌شود. ساده‌ترین نمایش برای یک فهرست حلقویِ خالی (در مواردی که چنین مفهومی معنا داشته باشد)، استفاده از یک اشاره‌گر تهی (null pointer) است که نشان می‌دهد فهرست هیچ گره‌ای ندارد. در غیر این صورت، بسیاری از الگوریتم‌ها ناچارند این حالت ویژه را بررسی کرده و آن را به‌طور جداگانه مدیریت کنند. در مقابل، استفاده از مقدار تهی برای نمایش یک فهرست خطیِ خالی طبیعی‌تر است و معمولاً موارد استثنای کمتری ایجاد می‌کند. در برخی کاربردها، ممکن است استفاده از فهرست‌های پیوندی یک‌سویه‌ای مفید باشد که بتوانند بین حالت خطی و حلقوی تغییر کنند، یا حتی ساختاری داشته باشند که بخش ابتدایی آن خطی و بخش پایانی آن حلقوی باشد. الگوریتم‌های جست‌وجو یا سایر عملیات روی چنین فهرست‌هایی باید تدابیری بیندیشند تا از ورود ناخواسته به یک حلقهٔ بی‌پایان جلوگیری شود. یکی از روش‌های شناخته‌شده برای این کار، استفاده از اشاره‌گر دومی است که فهرست را با سرعتی نصف یا دو برابر اشاره‌گر اصلی پیمایش می‌کند؛ در صورتی که این دو اشاره‌گر در یک گره به هم برسند، وجود یک چرخه در فهرست تشخیص داده می‌شود. استفاده از گرهٔ نگهبان (sentinel) استفاده از گرهٔ نگهبان باعث می‌شود که کاربر مطمئن باشد همهٔ عناصر موجود در فهرست دارای عنصر قبل و بعد هستند. با این حال، استفاده از گرهٔ نگهبان به فضای بیشتری نیاز دارد، به‌ویژه در برنامه‌هایی که از تعداد زیادی فهرست کوتاه استفاده می‌کنند. همچنین استفاده از گرهٔ نگهبان ممکن است باعث پیچیده‌تر شدن برخی عملیات، مانند ایجاد یک فهرست خالی، شود. اعمال فهرست پیوندی این بخش شبه کدهایی را برای درج و حذف عناصر در انواع فهرست‌های پیوندی ارائه می‌دهد. فهرست پیوندی خطی فهرست تک‌پیوندی داده ساختار گره استفاده شده در کد دارای دو فیلد است. فهرست پیوندی دایره‌ای در یک فهرست پیوندی دایره‌ای همه گره‌ها در یک دایره پیوسته به هم پیوند دارند. برای داده ساختاری مانند صف، با داشتن اشاره گری به عنصر آخر فهرست، عناصر می‌توانند از آخر در فهرست درج شوند و از ابتدای فهرست حذف شوند. | ## بخش 3: لیست پیوندی | هر دو نوع فهرست دایره‌ای قابلیت پیمایش همه عناصر فهرست، با شروع از هر یک از گره‌ها را دارند. در غیر این صورت، در صورتی که فهرست تنها یک عنصر داشته باشد، پیمایش به درستی صورت نمی‌گیرد. در آرایه‌ها، عناصر به‌صورت پیوسته در حافظه ذخیره می‌شوند، در حالی که در لیست پیوندی هر عنصر می‌تواند در مکانی جداگانه از حافظه قرار گیرد و از طریق اشاره‌گرها به عنصر بعدی متصل شود. این ویژگی باعث می‌شود لیست‌های پیوندی برای ساختارهایی که اندازهٔ آن‌ها در طول زمان تغییر می‌کند مناسب‌تر باشند، زیرا نیازی به تخصیص مجدد یک بلوک بزرگ و پیوسته از حافظه ندارند. هزینهٔ دسترسی تصادفی در مقابل این مزیت، لیست‌های پیوندی دسترسی تصادفی کارآمدی ارائه نمی‌دهند. برای دسترسی به یک عنصر خاص در لیست پیوندی، لازم است عناصر قبلی به‌ترتیب پیمایش شوند، در حالی که آرایه‌ها امکان دسترسی مستقیم به هر عنصر را در زمان ثابت فراهم می‌کنند. به همین دلیل، عملیات جست‌وجو و دسترسی در لیست‌های پیوندی معمولاً پرهزینه‌تر از آرایه‌ها است، به‌ویژه زمانی که داده‌ها حجم زیادی داشته باشند. درج و حذف عناصر یکی از مهم‌ترین مزایای لیست‌های پیوندی نسبت به آرایه‌ها، کارایی عملیات درج و حذف عناصر است. در لیست پیوندی، افزودن یا حذف یک عنصر معمولاً تنها به تغییر چند اشاره‌گر محدود می‌شود و نیازی به جابه‌جایی سایر عناصر ندارد. در مقابل، در آرایه‌ها درج یا حذف یک عنصر می‌تواند مستلزم جابه‌جایی تعداد زیادی از عناصر بعدی باشد، که این امر هزینهٔ زمانی بالاتری به همراه دارد. سربار حافظه‌ای اشاره‌گرها با وجود انعطاف‌پذیری بالاتر، لیست‌های پیوندی سربار حافظه‌ای بیشتری نسبت به آرایه‌ها دارند. هر عنصر در لیست پیوندی علاوه بر دادهٔ اصلی، نیازمند فضای اضافی برای نگهداری یک یا چند اشاره‌گر است. این سربار می‌تواند در ساختارهای بزرگ قابل توجه باشد و در برخی کاربردها باعث شود استفاده از آرایه‌ها یا ساختارهای دادهٔ دیگر از نظر مصرف حافظه بهینه‌تر باشد. داده‌ساختارهای مرتبط داده‌ساختارهای پشته و صف معمولاً با استفاده از فهرست پیوندی پیاده‌سازی می‌شوند. درخت دودویی می‌تواند به عنوان نوعی فهرست پیوندی که هر کدام از عناصر آن خود یک فهرست پیوندی است مورد بررسی قرار گیرد. در نتیجه هر گره می‌تواند اشاره گری به اولین گره یک یا دو فهرست پیوندی دیگر داشته باشد که زیر درخت‌های آن گره را تشکیل می‌دهند. این ساختار باعث افزایش کارایی حافظه نهان می‌شود؛ زیرا تعداد بیشتری از عناصر فهرست در حافظه پشت سر هم قرار می‌گیرند و سر جمع حافظه کاهش می‌یابد؛ زیرا فراداده کمتری باید برای هر عنصر فهرست ذخیره شود. | ## جمع‌بندی | جدول در هم‌سازی برای ساختن زنجیره‌ای از عناصر که در یک خانه جدول قرار می‌گیرند از فهرست پیوندی استفاده می‌کند.