لیست های پیوندی ( Linked List ) در ساختمان داده ها

[بانوثریا]

يکی از کاربردهای ليست حلقوی در اشتراک زمانی است که سيستم عامل ليستی از کاربران را دارد و به طور تناوبی به هر کاربر برش کوچکی از وقت پردازنده را اختصاص می دهد. هر بار يک کاربر را انتخاب می کند و مقداری از وقت پردازنده را می دهد سپس به کاربر بعدی منتقل می شود.

[بانوثریا]

ليست پيوندی دوطرفه

در ليست يک طرفه فقط می توانيم در يک جهت پيمايش کنيم. گاهی پيمايش روی ليست از هردوطرف مورد نياز است. بنابراين در هر گره به دو فيلد اشاره گر نياز است؛ برای اشاره به گره بعدی و گره قبلی که اغلب اشاره گرهای Left و Right ناميده می شوند. ليستی که شامل اين نوع گره باشد را ليست پيوندی دوطرفه (doubly-linked list) می نامند. شکل زير ساختار گره را نشان می دهد.

اگر ليست به صورت افقی ترسيم شود اشاره گرهای Right برای پيمايش ليست از چپ به راست (از ابتدا به انتها) استفاده می شوند. توسط اشاره گرهای Left می توان در صورت نياز به گره قبلی برگشت. بنابراين امکان پيمايش ليست در هردو جهت وجود دارد.

همين طور که در شکل ديده می شود اشاره گر Left اولين گره و اشاره گر Right آخرين گره ليست NULL هستند که نشان دهنده ابتدای هر جهت می باشند.

[بانوثریا]

پیاده سازی لیست پیوندی دو طرفه

[بانوثریا]

مقايسه ليست پيوندی و آرايه

مزيـ اصلی آرايه نسبت به ليست پيوندی اين است که آرايه امکان دسترسی تصادفی را می دهد و می توان به هر عنصر مستقيما توسط انديس آن مراجعه کرد. به همين دليل در يک آرايه مرتب می توانيد از جستجوی باينری به جای جستجوی خطی استفاده کنيد. اما با وجوديکه آرايه امکان دسترسی سريعتر به عناصر را می دهد در عمليات درج و حذف ضعيف است و عمليات درج و حذف ممکن است باعث شيفت دادن عناصر زياد ديگری شود. درحاليکه درج و حذف در ليست راحت تر است و درحقيقت تنها با تغيير اشاره گرها صورت می پذيرد. بنابراين احتمالا زمانی که عمليات درج و حذف زياد انجام می شود روش بهتری است. تفاوت ديگر ميزان فضای موردنياز دو روش است. آرايه يک ساختمان داده ايستا است. هنگام تعريف، اگر اندازه آرايه را کوچک بگيريم از قدرت برنامه کاسته می شود بنابراين ناگزيريم بيشترين فضای ممکن را درنظر بگيريم که در نتيجه آرايه خيلی بزرگ تعريف می شود و حافظه زيادی مصرف می شود. درحاليکه ليست پيوندی ساختمان داده پويا است يعنی می تواند به راحتی رشد کند يا تحليل برود يا تغيير کند. البته فضائی از حافظه برای ذخيره بايد اشاره گرها صرف شود.
کلا ليست های پيوندی اغلب برای نمايش اطلاعاتی که ويژگی های زير را دارند بکار می روند:

• تعداد کلی عناصر داده ای از قبل شناخته شده نيست.
• ممکن است عمليات اضافه و حذف زياد انجام شوند.
• داده ها در يک طريق مرتب يا متوالی ذخيره شوند.
• با داده ذخيره شده به طور وسيع کار شود نه موردی.