لیست پیوندی

فهرست پیوندی یا لیست پیوندی (به انگلیسی: Linked list) ساختاری شامل دنباله‌ای از عناصر است که هر عنصر دارای اشاره‌گری به عنصر بعدی در دنباله است. فهرست پیوندی از جملهٔ ساده‌ترین و رایج‌ترین داده‌ساختارها است و در پیاده‌سازی از داده‌ساختارها پشته (Stack)، صف (Queue) و جدول درهم‌سازی (Hash table) استفاده می‌شود. مزیت مهم فهرست پیوندی نسبت به آرایه‌ها این است که ترتیب قرار گرفتن داده‌ها در آن با ترتیب قرار گرفتن آن‌ها در حافظه متفاوت است. به همین دلیل فهرست پیوندی دارای این ویژگی است که درج و حذف گره‌ها در هر نقطه‌ای از فهرست، با تعداد ثابتی از عملیات امکان‌پذیر است. از طرف دیگر فهرست پیوندی اجازه دستیابی تصادفی به داده یا هرگونه اندیس‌گذاری را نمی‌دهد. در نتیجه بسیاری از اعمال ابتدایی نظیر به دست آوردن آخرین عنصر فهرست، پیدا کردن عنصر شامل داده مورد نظر، یا مشخص کردن مکان درج یک عنصر جدید ممکن است نیازمند بررسی اکثر عناصر فهرست باشد.

مفاهیم ابتدایی

هر عنصر در یک فهرست پیوندی گره نامیده می‌شود. هر گره شامل یک فیلد کلید و یک فیلد اشاره‌گر است.

فهرست دایره‌ای و فهرست خطی

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

فهرست دوپیوندی

در یک فهرست دوپیوندی، هرگره علاوه بر اشاره‌گری به عنصر بعدی دارای اشاره‌گری به عنصر قبلی خود نیز می‌باشد. در این نوع ساختمان داده هر گره یا node دو پوینتر دارد به نام‌های back,front که برای اتصال گره‌ها استفاده می گردد..

گره sentinel

در بعضی پیاده سازی‌ها یک گره اضافی به نام sentinel قبل از اولین گره فهرست یا بعد از آخرین گره آن اضافه می‌شود. این عمل باعث سادگی و تسریع برخی از الگوریتم‌های مرتبط با فهرست پیوندی می‌شود.

سنجش فهرست پیوندی

فهرست دوپیوندی در مقابل فهرست تک‌پیوندی

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

فهرست دایره‌ای در مقابل فهرست خطی

در یک فهرست خطی اشاره گری به آخرین گره امکان دسترسی به گره اول فهرست را نیز فراهم می‌سازد. در نتیجه در مواردی که دسترسی به دو سر فهرست نیاز است، یک ساختار مدور تنها با یک اشاره گر امکان مدیریت کردن عناصر را فراهم می‌کند. ساده‌ترین نحوه نمایش یک فهرست دایره‌ای خالی هنگامی است که فهرست هیچ گرهی ندارد و با یک اشاره گر به null نشان داده می‌شود. با توجه به این مسئله، در بسیاری از الگوریتم‌ها باید این حالت خاص در نظر گرفته شود و به‌طور جداگانه مورد بررسی قرار گیرد. در مقابل، استفاده از null برای نشان دادن یک فهرست خطی قابل درک تر است و حالت‌های خاص کمتری را ایجاد می‌کند.

استفاده از گره sentinel

استفاده از گره sentinel باعث می‌شود که کاربر مطمئن شود که همه عناصر موجود در فهرست، دارای عناصر قبل و بعد هستند. به همین دلیل برخی از عملیات مربوط به فهرست ساده‌تر می‌شوند. با این حال استفاده از sentinel نیازمند فضای بیشتر است. به خصوص در برنامه‌هایی که از تعداد زیادی فهرست کوتاه استفاده می‌شود. همچنین استفاده از sentinel ممکن است باعث پیچیدگی برخی اعمال شود. مانند ساختن یک فهرست خالی.

اعمال فهرست پیوندی

این بخش شبه کدهایی را برای درج و حذف عناصر در انواع فهرست‌های پیوندی ارائه می‌دهد.

فهرست پیوندی خطی

فهرست تک‌پیوندی

داده ساختار گره استفاده شده در کد دارای دو فیلد است. همچنین یک متغیر firstNode در نظر گرفته شده‌است که همواره به عنصر اول فهرست اشاره می‌کند و در صورت خالی بودن فهرست دارای مقدار null است.

 record Node {
    data // The data being stored in the node
    next // A reference to the next node, null for last node
 }

 record List {
     Node firstNode   // points to first node of list; null for empty list
 }

پیمایش یک فهرست تک پیوندی به این صورت است که از گره اول شروع کرده و اشاره گر به عنصر بعدی را دنبال می‌کنیم تا به ته فهرست برسیم.

 node := list.firstNode
 while node not null {
     (do something with node.data)
     node := node.next
 }

شبه کد زیر گره جدیدی را بعد از یک گره موجود داده شده درج می‌کند. شکل نحوهٔ درج را نشان می‌دهد.

 function insertAfter(Node node, Node newNode) { // insert newNode after node
     newNode.next := node.next
     node.next    := newNode
 }

همچنین برای درج یک عنصر در ابتدای فهرست کد زیر مورد استفاده قرار می‌گیرد.

 function insertBeginning(List list, Node newNode) { // insert node before current first node
     newNode.next   := list.firstNode
     list.firstNode := newNode
 }

به‌طور مشابه توابعی برای حذف گره بعدی یک گره داده شده و همچنین گره ابتدایی فهرست وجود دارند. شکل نحوه حذف را نشان می‌دهد.

 function removeAfter(node node) { // remove node past this one
     obsoleteNode := node.next
     node.next := node.next.next
     destroy obsoleteNode
 }

 function removeBeginning(List list) { // remove first node
     obsoleteNode := list.firstNode
     list.firstNode := list.firstNode.next          // point past deleted node
     destroy obsoleteNode
 }

از آنجا که در این نوع فهرست امکان پیمایش به سمت ابتدای فهرست وجود ندارد، توابع ()insertBefore و ()insertAfter وجود ندارند.

فهرست پیوندی دایره‌ای

در یک فهرست پیوندی دایره‌ای همه گره‌ها در یک دایره پیوسته به هم پیوند دارند. اشاره گر عنصر آخر فهرست به عنصر ابتدای آن اشاره دارد. برای داده ساختاری مانند صف، با داشتن اشاره گری به عنصر آخر فهرست، عناصر می‌توانند از آخر در فهرست درج شوند و از ابتدای فهرست حذف شوند. فهرست پیوندی دایره‌ای می‌تواند تک‌پیوندی یا دوپیوندی باشد. هر دو نوع فهرست دایره‌ای قابلیت پیمایش همه عناصر فهرست، با شروع از هر یک از گره‌ها را دارند. این ویژگی باعث می‌شود که نیازی به ذخیره کردن اشاره گرهای fisrtNode و lastNode نداشته باشیم.گر چه اگر فهرست خالی باشد، به یک نمایش خاص برای نشان دادن فهرست نیاز است. در اینجا از یک متغیر lastNode استفاده شده که در صورت خالی بودن فهرست به null اشاره می‌کند.این نمایش باعث ساده‌تر شدن درج و حذف عناصر در یک فهرست غیر خالی می‌شود. اما یک حالت خاص برای فهرست‌های خالی ایجاد می‌شود.

فهرست پیوندی دایره‌ای

با فرض اینکه someNode یکی از عناصر موجود در فهرست می‌باشد کد زیر پیمایش روی عناصر فهرست را با شروع از someNode پیاده‌سازی می‌کند.

 function iterate(someNode)
   if someNode  ≠ null
     node := someNode
     do
       do something with node.value
       node := node.next
     while node ≠ someNode

توجه داشته باشید که بخش «while node ≠ someNode» باید در انتهای حلقه قرار گیرد. در غیر این صورت، در صورتی که فهرست تنها یک عنصر داشته باشد، پیمایش به درستی صورت نمی‌گیرد. تابع زیر نحوه درج عنصر جدید newNOde را در جایگاه بعد از عنصر node در یک فهرست دایره‌ای پیاده‌سازی می‌کند. در صورت null بودن node فرض شده که فهرست خالی است.

 function insertAfter(Node node, Node newNode)
     if node = null
       newNode.next := newNode
     else
       newNode.next := node.next
       node.next := newNode

فرض کنید "L" متغیری است که به عنصر آخر فهرست مدور اشاره می‌کند. برای درج عنصر جدید newNode در انتهای فهرست از کد زیر استفاده می‌شود.

 insertAfter(L, newNode)
   L = newNode

همچنین برای درج newNode در ابتدای فهرست کد زیر مورد استفاده قرار می‌گیرد.

 insertAfter(L, newNode)
   if L = null
     L = newNode

داده‌ساختارهای مرتبط

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

منابع

• http://en.wikipedia.org/wiki/Linked_list
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introductions to Algorithms (2003). MIT Press. ISBN 0-262-03293-7, pp. 205–213, 501–505

پیوند به بیرون

• الگوریتمستان، لیست پیوندی