لیست پیوندی
فهرست پیوندی یا لیست پیوندی ساختاری شامل دنباله‌ای از عناصر است که هر عنصر دارای اشاره‌گری به عنصر بعدی در دنباله است. فهرست پیوندی از جملهٔ ساده‌ترین و رایج‌ترین داده‌ساختارها است و در پیاده‌سازی از داده‌ساختارها پشته (Stack)، صف (Queue) و جدول درهم‌سازی (Hash table) استفاده می‌شود. مزیت مهم فهرست پیوندی نسبت به آرایه‌ها این است که ترتیب قرار گرفتن داده‌ها در آن با ترتیب قرار گرفتن آن‌ها در حافظه متفاوت است. به همین دلیل فهرست پیوندی دارای این ویژگی است که درج و حذف گره‌ها در هر نقطه‌ای از فهرست، با تعداد ثابتی از عملیات امکان‌پذیر است. از طرف دیگر فهرست پیوندی اجازه دستیابی تصادفی به داده یا هرگونه اندیس‌گذاری را نمی‌دهد. در نتیجه بسیاری از اعمال ابتدایی نظیر به دست آوردن آخرین عنصر فهرست، پیدا کردن عنصر شامل داده مورد نظر، یا مشخص کردن مکان درج یک عنصر جدید ممکن است نیازمند بررسی اکثر عناصر فهرست باشد. هر عنصر در یک فهرست پیوندی گره نامیده می‌شود. هر گره شامل یک فیلد کلید و یک فیلد اشاره‌گر است.  معمولاً در آخرین عنصر یک فهرست، فیلد اشاره گر اشاره گری به null است. null در زبان‌های برنامه‌نویسی به معنای عدم وجود یک عنصر است. این نوع فهرست، فهرست خطی نامیده می‌شود. در نوع دیگری از فهرست پیوندی، اشاره گر عنصر آخر به عنصر اول فهرست اشاره می‌کند. به این نوع فهرست، فهرست پیوندی دایره‌ای می‌گویند. در یک فهرست دوپیوندی، هرگره علاوه بر اشاره‌گری به عنصر بعدی دارای اشاره‌گری به عنصر قبلی خود نیز می‌باشد. در این نوع ساختمان داده هر گره یا node دو پوینتر دارد به نام‌های back,front که برای اتصال گره‌ها استفاده می گردد..
در بعضی پیاده سازی‌ها یک گره اضافی به نام sentinel قبل از اولین گره فهرست یا بعد از آخرین گره آن اضافه می‌شود. این عمل باعث سادگی و تسریع برخی از الگوریتم‌های مرتبط با فهرست پیوندی می‌شود. فهرست دوپیوندی به ازای هر گره به فضای بیشتری نیاز دارد و انجام عملیات اصلی بر روی آن هزینه بیشتری را صرف می‌کند. با این حال اداره این نوع فهرست ساده‌تر است. به دلیل اینکه قابلیت دسترسی ترتیبی به عناصر را در هر دو جهت دارند. به عنوان مثال، تنها با در دست داشتن آدرس یک گره می‌توان با تعداد ثابتی از اعمال آن گره را از فهرست حذف یا در آن درج کرد. برای انجام همین اعمال در یک فهرست تک‌پیوندی آدرس گره قبل از گره مورد نظر نیز نیاز است.
در یک فهرست خطی اشاره گری به آخرین گره امکان دسترسی به گره اول فهرست را نیز فراهم می‌سازد. در نتیجه در مواردی که دسترسی به دو سر فهرست نیاز است، یک ساختار مدور تنها با یک اشاره گر امکان مدیریت کردن عناصر را فراهم می‌کند. ساده‌ترین نحوه نمایش یک فهرست دایره‌ای خالی هنگامی است که فهرست هیچ گرهی ندارد و با یک اشاره گر به null نشان داده می‌شود. با توجه به این مسئله، در بسیاری از الگوریتم‌ها باید این حالت خاص در نظر گرفته شود و به‌طور جداگانه مورد بررسی قرار گیرد. در مقابل، استفاده از null برای نشان دادن یک فهرست خطی قابل درک تر است و حالت‌های خاص کمتری را ایجاد می‌کند. استفاده از گره sentinel باعث می‌شود که کاربر مطمئن شود که همه عناصر موجود در فهرست، دارای عناصر قبل و بعد هستند. به همین دلیل برخی از عملیات مربوط به فهرست ساده‌تر می‌شوند. با این حال استفاده از sentinel نیازمند فضای بیشتر است. به خصوص در برنامه‌هایی که از تعداد زیادی فهرست کوتاه استفاده می‌شود. همچنین استفاده از sentinel ممکن است باعث پیچیدگی برخی اعمال شود. مانند ساختن یک فهرست خالی. این بخش شبه کدهایی را برای درج و حذف عناصر در انواع فهرست‌های پیوندی ارائه می‌دهد. داده ساختار گره استفاده شده در کد دارای دو فیلد است. همچنین یک متغیر firstNode در نظر گرفته شده‌است که همواره به عنصر اول فهرست اشاره می‌کند و در صورت خالی بودن فهرست دارای مقدار null است.
پیمایش یک فهرست تک پیوندی به این صورت است که از گره اول شروع کرده و اشاره گر به عنصر بعدی را دنبال می‌کنیم تا به ته فهرست برسیم.
شبه کد زیر گره جدیدی را بعد از یک گره موجود داده شده درج می‌کند. شکل نحوهٔ درج را نشان می‌دهد.
همچنین برای درج یک عنصر در ابتدای فهرست کد زیر مورد استفاده قرار می‌گیرد.
به‌طور مشابه توابعی برای حذف گره بعدی یک گره داده شده و همچنین گره ابتدایی فهرست وجود دارند. شکل نحوه حذف را نشان می‌دهد.
از آنجا که در این نوع فهرست امکان پیمایش به سمت ابتدای فهرست وجود ندارد، توابع ()insertBefore و ()insertAfter وجود ندارند.
در یک فهرست پیوندی دایره‌ای همه گره‌ها در یک دایره پیوسته به هم پیوند دارند. اشاره گر عنصر آخر فهرست به عنصر ابتدای آن اشاره دارد. برای داده ساختاری مانند صف، با داشتن اشاره گری به عنصر آخر فهرست، عناصر می‌توانند از آخر در فهرست درج شوند و از ابتدای فهرست حذف شوند. فهرست پیوندی دایره‌ای می‌تواند تک‌پیوندی یا دوپیوندی باشد. هر دو نوع فهرست دایره‌ای قابلیت پیمایش همه عناصر فهرست، با شروع از هر یک از گره‌ها را دارند. این ویژگی باعث می‌شود که نیازی به ذخیره کردن اشاره گرهای fisrtNode و lastNode نداشته باشیم.گر چه اگر فهرست خالی باشد، به یک نمایش خاص برای نشان دادن فهرست نیاز است. در اینجا از یک متغیر lastNode استفاده شده که در صورت خالی بودن فهرست به null اشاره می‌کند.این نمایش باعث ساده‌تر شدن درج و حذف عناصر در یک فهرست غیر خالی می‌شود. اما یک حالت خاص برای فهرست‌های خالی ایجاد می‌شود. با فرض اینکه someNode یکی از عناصر موجود در فهرست می‌باشد کد زیر پیمایش روی عناصر فهرست را با شروع از someNode پیاده‌سازی می‌کند.
توجه داشته باشید که بخش «while node ≠ someNode» باید در انتهای حلقه قرار گیرد. در غیر این صورت، در صورتی که فهرست تنها یک عنصر داشته باشد، پیمایش به درستی صورت نمی‌گیرد. تابع زیر نحوه درج عنصر جدید newNOde را در جایگاه بعد از عنصر node در یک فهرست دایره‌ای پیاده‌سازی می‌کند. در صورت null بودن node فرض شده که فهرست خالی است.
فرض کنید "L" متغیری است که به عنصر آخر فهرست مدور اشاره می‌کند. برای درج عنصر جدید newNode در انتهای فهرست از کد زیر استفاده می‌شود.
همچنین برای درج newNode در ابتدای فهرست کد زیر مورد استفاده قرار می‌گیرد.
داده‌ساختارهای پشته و صف معمولاً با استفاده از فهرست پیوندی پیاده‌سازی می‌شوند. درخت دودویی می‌تواند به عنوان نوعی فهرست پیوندی که هر کدام از عناصر آن خود یک فهرست پیوندی است مورد بررسی قرار گیرد. در نتیجه هر گره می‌تواند اشاره گری به اولین گره یک یا دو فهرست پیوندی دیگر داشته باشد که زیر درخت‌های آن گره را تشکیل می‌دهند. فهرست پیوندی باز شده(unrolled linked list) نوعی فهرست پیوندی است که هر گره آن شامل آرایه‌ای از داده‌ها است. این ساختار باعث افزایش کارایی حافظه نهان می‌شود. زیرا تعداد بیشتری از عناصر فهرست در حافظه پشت سر هم قرار می‌گیرند و سر جمع حافظه کاهش می‌یابد. زیرا فراداده کمتری باید برای هر عنصر فهرست ذخیره شود.
جدول در هم‌سازی برای ساختن زنجیره‌ای از عناصر که در یک خانه جدول قرار می‌گیرند از فهرست پیوندی استفاده می‌کند.