لیست پیوندی

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

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

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

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

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

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

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

گره sentinel

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

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

فهرست‌های خطی پیوندی در مقایسه با سایر فهرست‌ها

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

یک فهرست پیوندی خطی یک‌سویه، یک ساختار دادهٔ بازگشتی است، زیرا شامل اشاره‌گری به یک شیء کوچک‌تر از همان نوع خود است. به همین دلیل، بسیاری از عملیات روی فهرست‌های پیوندی خطی یک‌سویه (مانند ادغام دو فهرست یا پیمایش عناصر به ترتیب معکوس) معمولاً دارای الگوریتم‌های بازگشتی بسیار ساده‌ای هستند که از هر راه‌حل مبتنی بر دستورات تکراری ساده‌ترند. اگرچه این راه‌حل‌های بازگشتی را می‌توان برای فهرست‌های پیوندی دوسویه و حلقوی نیز تطبیق داد، اما این کار معمولاً به آرگومان‌های اضافی و شرایط پایهٔ پیچیده‌تری نیاز دارد.

فهرست‌های پیوندی خطی یک‌سویه همچنین امکان اشتراک دُم (tail-sharing) را فراهم می‌کنند؛ یعنی استفاده از یک بخش پایانی مشترک به‌عنوان انتهای دو فهرست متفاوت. به‌طور خاص، اگر یک گرهٔ جدید به ابتدای یک فهرست اضافه شود، فهرست قبلی همچنان به‌عنوان دُم فهرست جدید در دسترس باقی می‌ماند. این ویژگی نمونهٔ ساده‌ای از یک ساختار دادهٔ پایدار (persistent data structure) است. این قابلیت در سایر گونه‌ها وجود ندارد؛ زیرا یک گره هرگز نمی‌تواند هم‌زمان به دو فهرست حلقوی یا دوسویهٔ متفاوت تعلق داشته باشد.

به‌طور ویژه، گره‌های نگهبان انتهایی (end-sentinel nodes) می‌توانند میان فهرست‌های پیوندی یک‌سویهٔ غیرحلقوی به اشتراک گذاشته شوند. یک گرهٔ نگهبان انتهایی واحد می‌تواند برای همهٔ این فهرست‌ها استفاده شود. برای مثال، در زبان لیسپ، هر فهرست درست (proper list) با پیوند به یک گرهٔ ویژه که با ‎nil‎ یا ‎()‎ نمایش داده می‌شود، پایان می‌یابد.

مزایای گونه‌های پیشرفته‌تر اغلب به پیچیدگی الگوریتم‌ها محدود می‌شود و الزاماً به معنای کارایی بیشتر نیست. به‌ویژه، یک فهرست حلقوی معمولاً می‌تواند با استفاده از یک فهرست خطی به‌همراه دو متغیر که به اولین و آخرین گره اشاره می‌کنند، و بدون هزینهٔ اضافی، شبیه‌سازی شود.

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

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

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

یک فهرست پیوندی حلقوی می‌تواند گزینه‌ای مناسب برای نمایش آرایه‌ها یا مجموعه‌هایی باشد که ذاتاً ساختاری حلقوی دارند؛ برای مثال، گوشه‌های یک چندضلعی، مجموعه‌ای از بافرها که به ترتیب FIFO («اولین ورودی، اولین خروجی») مورد استفاده قرار گرفته و آزاد می‌شوند، یا مجموعه‌ای از فرایندها که باید به‌صورت گردشی (round-robin) زمان‌بندی شوند. در این کاربردها، یک اشاره‌گر به هر گره می‌تواند به‌عنوان دسترسی (handle) به کل فهرست عمل کند.

در یک فهرست حلقوی، اشاره‌گر به آخرین گره امکان دسترسی آسان به اولین گره را نیز فراهم می‌کند، زیرا با دنبال کردن تنها یک پیوند می‌توان به ابتدای فهرست رسید. ازاین‌رو، در کاربردهایی که نیازمند دسترسی به هر دو انتهای فهرست هستند (برای نمونه، در پیاده‌سازی صف)، ساختار حلقوی اجازه می‌دهد که کل فهرست تنها با یک اشاره‌گر مدیریت شود، نه با دو اشاره‌گر جداگانه.

یک فهرست حلقوی را می‌توان در زمان ثابت به دو فهرست حلقوی تقسیم کرد، به شرط آن‌که نشانی آخرین گرهٔ هر بخش مشخص باشد. این عمل با جابه‌جا کردن محتوای فیلد پیوند (link) این دو گره انجام می‌شود. انجام همین عملیات روی هر دو گره از دو فهرست مجزا، باعث اتصال آن دو فهرست و تشکیل یک فهرست واحد می‌شود. این ویژگی برخی الگوریتم‌ها و ساختارهای داده، مانند quad-edge و face-edge، را به‌طور قابل توجهی ساده می‌کند.

ساده‌ترین نمایش برای یک فهرست حلقویِ خالی (در مواردی که چنین مفهومی معنا داشته باشد)، استفاده از یک اشاره‌گر تهی (null pointer) است که نشان می‌دهد فهرست هیچ گره‌ای ندارد. در غیر این صورت، بسیاری از الگوریتم‌ها ناچارند این حالت ویژه را بررسی کرده و آن را به‌طور جداگانه مدیریت کنند. در مقابل، استفاده از مقدار تهی برای نمایش یک فهرست خطیِ خالی طبیعی‌تر است و معمولاً موارد استثنای کمتری ایجاد می‌کند.

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

استفاده از گرهٔ نگهبان (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

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

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