لیست پیوندی

فهرست پیوندی یا لیست پیوندی ساختاری شامل دنباله‌ای از عناصر است که هر عنصر دارای اشاره‌گری به عنصر بعدی در دنباله است. فهرست پیوندی از جمله ساده‌ترین و رایج‌ترین داده‌ساختارها است و در پیاده‌سازی از داده‌ساختارها پشته (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
شبه کد زیر گره جدیدی را بعد از یک گره موجود داده شده درج می‌کند. شکل نحوه درج را نشان می‌دهد.
center
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
به‌طور مشابه توابعی برای حذف گره بعدی یک گره داده شده و همچنین گره ابتدایی فهرست وجود دارند. شکل نحوه حذف را نشان می‌دهد.
center
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
داده‌ساختارهای مرتبط
داده‌ساختارهای پشته و صف معمولا با استفاده از فهرست پیوندی پیاده‌سازی می‌شوند.
درخت دودویی می‌تواند به عنوان نوعی فهرست پیوندی که هر کدام از عناصر آن خود یک فهرست پیوندی است مورد بررسی قرار گیرد. در نتیجه هر گره می‌تواند اشاره گری به اولین گره یک یا دو فهرست پیوندی دیگر داشته باشد که زیر درخت‌های آن گره را تشکیل می‌دهند.
فهرست پیوندی باز شده( ) نوعی فهرست پیوندی است که هر گره آن شامل آرایه‌ای از داده‌ها است. این ساختار باعث افزایش کارایی حافظه نهان می‌شود. زیرا تعداد بیشتری از عناصر فهرست در حافظه پشت سر هم قرار می‌گیرند و سر جمع حافظه کاهش می‌یابد. زیرا فراداده کمتری باید برای هر عنصر فهرست ذخیره شود.
جدول در هم‌سازی برای ساختن زنجیره‌ای از عناصر که در یک خانه جدول قرار می‌گیرند از فهرست پیوندی استفاده می‌کند.