در علوم رایانه، لیست پیوندی دوطرفه یک ساختار دادهی به هم پیوسته است که از یک سری رکوردها و اطلاعات به هم پیوسته که گره نامیده میشوند، تشکیل شدهاست. هرگره از دو بخش تشکیل شده که یک مرجع به گره قبل و گره بعد در سری گرهها است که به آن پیوند میگویند. قسمتهای next (بعدی) و previous (قبلی) در گرههای ابتدایی و انتهایی گره که به ترتیب به یک نوعی از مخرب اشاره میکنند و به منظور تسهیل در پیمایش لیست بهطور معمول یک گرۀ نگهبان (Sentinel node) یا تهی است. اگر تنها یک گرۀ نگهبان باشد، آنگاه یک لیست پیوندی حلقوی با گرهٔ نگهبان داریم. میتوان به این شکل درک کرد که دو لیست پیوندی یک طرفه با اطلاعات و مقادیر یکسان داریم که در جهت عکس یکدیگر هستند.
دو گرهٔ پیوند این امکان را میدهند که بتوانیم لیست را در هر دو جهت پیمایش کنیم. در هنگام اضافه کردن یا پاک کردن در لیست پیوندی دوطرفه ما به تغییرات بیشتری نسبت به عملیاتی که بروی لیست پیوندی یک طرفه انجام میدادیم نیازمندیم. این عملیات سادهتر و بهطور بالقوه کارآمدتر هستند (برای گرههایی غیر از گره اول) به دلیل اینکه نیازی به نگهداری از گره قبلی در هنگام پیمایش وجود ندارد یا هیچ نیازی به پیمایش لیست برای پیدا کردن گره قبلی وجود ندارد و به این صورت لیست میتواند اصلاح شود.
نامگذاری و پیادهسازی
اولین و آخرین گره به سرعت قابل دسترسی هستند (دسترسی بدون پیمایش) و بنابراین این اجازه را میدهند که لیست را هم از ابتدا و هم از انتهای آن پیمایش کرد و به ترتیب پیمایش لیست از انتها تا ابتدا یا از انتها تا ابتدا هنگام جستجوی لیست برای یافتن گره ایی که دارای مقدار مشخص است. هر گره ایی از لیست پیوندی دو طرفه هنگامی که بدست بیاید، میتوان از آن برای شروع یک پیمایش جدید در لیست استفاده کرد در هر دو جهت (به سمت ابتدا یا انتها).
قسمتهای پیوندی لیست پیوندی دو طرفه که اغلب بعدی وقبلی یا جلویی و عقبی نامیده میشوند. ارجاعاتی که در قسمتهای پیوندی گرهها موجود است اغلب توسط اشارهگر (علوم رایانه) پیادهسازی و اجرا میشوند. اما (مانند سایر دادهای پیوندی) آنها ممکن است میزان جابجایی آدرس یا شاخص آرایه ایی که گرهها در آن هستند را مشخص کنند.
الگوریتم پایه ایی
record{prev''// A reference to the previous node''next''// A reference to the next node''data''// Data or a reference to data''{record{''DoublyLinkedNode''firstNode''// points to first node of list''''DoublyLinkedNode''lastNode''// points to last node of list''{
پیمایش لیست
پیمایش یک لیست پیوندی دو طرفه میتواند در هر دو جهت انجام گیرد. در حقیقت جهت پیمایش میتواند بارها تغییر کند. در صورت لزوم، اغلب پیمایش تکرار نیز گفته میشود، اما این انتخاب اصطلاح مایه تاسف است برای تکرار که دارای معنا و مفهوم مشخص و تعریف شده ایی است.
یک نتیجه و دستآور ظریف روش بالا این است که پاک کردن گره انتهایی لیست، در هر دو گره اول و آخر مقدار تهی قرار میدهد. و به همین ترتیب پاک کردن گره آخر یک لیست با یک عنصر را مدیریت میکند. توجه شود که ما به دو تابع جدای "پاک کردن قبل از"("RemoveBefore") و "پاک کردن بعد از" ("RemoveAfter") نیازی نداریم زیرا در لیست پیوندی دو طرفه ما از "(remove(node.prev" یا "(remove(node.next" استفاده میکنیم چرا که اینها مجاز هستند. این همچنین فرض میکند که گره ایی که در حال پاک شدن است تضمین به موجود بودنشان شدهاست، اگر گره در لیست موجود نباشد آنگاه مدیریت خطاها لازم میشود.
لیست پیوندی حلقوی
پیمایش لیست
فرض میکنیم که گره ایی فرضی و دلخواه، یک گره در یک لیست غیر تهی است، کد زیر لیست را از گره فرضی و دلخواه پیمایش میکند:
لیست پیوندی دو طرفه نا متقارن مفهومی میان لیست پیوندی یک طرفه و لیست پیوندی دو طرفه معمولی است. آن ترکیبی از ویژگی لیست پیوندی یک طرفه (پیمایش یک طرفه) و ویژگیهای دیگر از لیست پیوندی دو طرفه (سهولت اصلاح) را داراست.
لیست پیوندی دو طرفه نا متقارن، لیستی است که در آن پیوند به گره قبل در هر گره به گرهٔ قبلی اشاره نمیکند بلکه به خود پیوند گره اشاره دارد.
در حالی که این مقداری تفاوت میان گرهها ایجاد میکند (تنها به اختلاف میان گرههای قبلی اشاره میکند)، با این حال ابتدای لیست را نیز تغییر میدهد، این ویژگی این اجازه را میدهد تا قسمت پیوند گره اول به آسانی تغییر کند.[۱][۲]
تا زمانی که یک گره در لیست موجود باشد گره قبل از آن هیچگاه تهی نخواهد بود.
اضافه کردن گره
برای اضافه کردن یک گره قبل از دیگری، با استفاده از گره قبلی(prev link) قسمت پیوندی که به گره قدیمی اشاره میکند را تغییر میدهیم، سپس قسمت بعدی (Next) گره جدید را به گره قدیمی پیوند میدهیم و به همین ترتیب قسمت قبلی (Prev) گره جدید را نیز تغییر میدهیم.
'''function'''insertBefore(''Node''node,''Node''newNode)'''if'''node.prev==null''' '''error''' "The node is not in a list" newNode.prev := node.prev atAddress(newNode.prev) := newNode newNode.next := node node.prev = addressOf(newNode.next) '''function''' insertAfter(''Node'' node, ''Node'' newNode) newNode.next := node.next '''if''' newNode.next != '''null'''newNode.next.prev=addressOf(newNode.next)node.next:=newNodenewNode.prev:=addressOf(node.next)
پاک کردن یک گره
برای پاک کردن یک گره به سادگی با اعمال تغییر در بخش پیوندی گره قبلی این کار را انجام میدهیم، صرف نظر از اینکه گره اول لیست باشد یا خیر.