مفاهیم ابتدایی[ویرایش]

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

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

معمولاً در آخرین عنصر یک فهرست، فیلد اشاره گر اشاره گری به 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
}


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



Singly linked list insert after.png
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
}


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



Singly linked list delete after.png
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
}


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