لیست پیوندی

فهرست پیوندی[ ۱] یا لیست پیوندی ( به انگلیسی: Linked list ) ساختاری شامل دنباله ای از عناصر است که هر عنصر دارای اشاره گری به عنصر بعدی در دنباله است. فهرست پیوندی از جملهٔ ساده ترین و رایج ترین داده ساختارها است و در پیاده سازی از داده ساختارها پشته ( Stack ) ، صف ( Queue ) و جدول درهم سازی ( Hash table ) استفاده می شود. مزیت مهم فهرست پیوندی نسبت به آرایه ها این است که ترتیب قرار گرفتن داده ها در آن با ترتیب قرار گرفتن آن ها در حافظه متفاوت است. به همین دلیل فهرست پیوندی دارای این ویژگی است که درج و حذف گره ها در هر نقطه ای از فهرست، با تعداد ثابتی از عملیات امکان پذیر است. از طرف دیگر فهرست پیوندی اجازه دستیابی تصادفی به داده یا هرگونه اندیس گذاری را نمی دهد. در نتیجه بسیاری از اعمال ابتدایی نظیر به دست آوردن آخرین عنصر فهرست، پیدا کردن عنصر شامل داده مورد نظر، یا مشخص کردن مکان درج یک عنصر جدید ممکن است نیازمند بررسی اکثر عناصر فهرست باشد.
هر عنصر در یک فهرست پیوندی گره نامیده می شود. هر گره شامل یک فیلد کلید و یک فیلد اشاره گر است.
معمولاً در آخرین عنصر یک فهرست، فیلد اشاره گر اشاره گری به null است. null در زبان های برنامه نویسی به معنای عدم وجود یک عنصر است. این نوع فهرست، فهرست خطی نامیده می شود. در نوع دیگری از فهرست پیوندی، اشاره گر عنصر آخر به عنصر اول فهرست اشاره می کند. به این نوع فهرست، فهرست پیوندی دایره ای می گویند.
در یک فهرست دوپیوندی، هرگره علاوه بر اشاره گری به عنصر بعدی دارای اشاره گری به عنصر قبلی خود نیز می باشد. در این نوع ساختمان داده هر گره یا node دو پوینتر دارد به نام های back, front که برای اتصال گره ها استفاده می گردد. .
در بعضی پیاده سازی ها یک گره اضافی به نام sentinel قبل از اولین گره فهرست یا بعد از آخرین گره آن اضافه می شود. این عمل باعث سادگی و تسریع برخی از الگوریتم های مرتبط با فهرست پیوندی می شود.
فهرست دوپیوندی به ازای هر گره به فضای بیشتری نیاز دارد و انجام عملیات اصلی بر روی آن هزینه بیشتری را صرف می کند. با این حال اداره این نوع فهرست ساده تر است. به دلیل اینکه قابلیت دسترسی ترتیبی به عناصر را در هر دو جهت دارند. به عنوان مثال، تنها با در دست داشتن آدرس یک گره می توان با تعداد ثابتی از اعمال آن گره را از فهرست حذف یا در آن درج کرد. برای انجام همین اعمال در یک فهرست تک پیوندی آدرس گره قبل از گره مورد نظر نیز نیاز است.