لیست پیوندی

۱) لیست پیوندی ساختمان داده ای پویاست.
۲) جستجو در لیست پیوندی همواره خطی(ترتیبی) است.
۳) جستجوی دودویی در لیست پیوندی قابل پیاده سازی نیست.
۴) برای حذف گره از لیست خطی نیاز است یک اشاره گر تغییر کند.
۵) درج گره در لیست پیوندی خطی نیاز به تغییر دو اشاره گردارد.
۶) در صورتی که تعدادعناصر مورد استفاده مشخص باشد بکار گرفتن آرایه بهتر از کار با لیست پیوندی است.
۷)برای درج گره ی جدید بعد از گره ی p در لیست خطی داریم:

;(New(q
;q.Data=Item
;q.Next=p.Next
;p.Next=q

۹) درج عنصر جدید در صف پیوندی به انتهای لیست است و حذف از ابتداست.
۱۰) حذف و درج عنصر جدید درپشته ی پیوندی به ابتدای لیست غیر تهی است.

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

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

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

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

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

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


تذکر: تهی قرار دادن فیلد next آخرین گره برای تشخیص انتهای لیست ضروری است.

در ادامه این بحث فرض می‌گیریم گره‌های لیست از نوع myrec - شامل عنصری به نام next از نوع اشاره گر به خود - هستند.
در ابتدا، همیشه باید دو اشاره‌گر عمومی (مثلا به نامهای first و last) تعریف کنید که یکی به ابتدای لیست و دیگری به انتهای آن اشاره کنند. در لیست‌های پیوندی اگر آدرس عنصر اول را داشته باشید، می‌توانید به همه عناصر دسترسی پیدا کنید. عنصر آخر هم زمان اضافه کردن گره جدید به کار می‌آید. با داشتن آدرس این گره در زمان اضافه کردن گره جدید، لازم نیست لیست را از ابتدا تا انتها برای یافتن آخرین گره پیمایش کنید. پس وجود این اشاره‌گرها مهم بوده و حتما باید تعریف شوند. در تعریف این اشاره‌گرها باید به دو نکته توجه کرد:
۱- باید عمومی تعریف شوند. اگر از کلاس استفاده می‌کنید، باید عضو مستقیم و خصوصی کلاس باشند.
۲- باید در زمان تعریف با تهی (NULL برای ++C) مقداردهی شوند. مانند عبارت‌های زیر:

;myrec *first = NULL
;myrec *last = NULL

یادآوری: برای دسترسی به عناصر یک ساختمان توسط اشاره‌گر دو روش وجود دارد:

first->next
*first).next)

این دو دستور معادل هستند، اما اولی کمی بامسماتر است.

---------------------------------------------------------------------------------------------------
اعمال لیست پیوندی


اضافه کردن گره به لیست پیوندی:

وظیفه تابع add اضافه کردن یک گره به انتهای لیست پیوندی است. این تابع باید یک ورودی - شامل اطلاعات گره جدید - داشته باشد و نیازی به خروجی ندارد. البته می‌توان خروجی را از نوع بولی تعریف کرد که نشان می‌دهد عملیات با موفقیت انجام شده است یا نه؟

(void add( myrec info
}
; myrec *temp
; temp = new myrec
; temp = info*
; (if( first == NULL
}
; first = temp
; first->next = NULL
; last = first
{
else
}
; last->next = temp
; last = temp
; last->next = NULL
{

این تابع، ابتدا با دستور new یک فضا برای گره جدید رزرو می‌کند، و آدرس آن را در متغیر temp قرار می‌دهد. سپس محتوای info را در temp کپی می‌کند. دستورات مهم از اینجا شروع می‌شوند: ابتدا بررسی می‌کند که آیا first تهی است یا نه؟ اگر تهی باشد، یعنی لیست خالی است و گره جدید اولین گره لیست خواهد بود. پس temp را در first و last (چون لیست خالی بود، گره اول همان گره آخر هم می‌شود) کپی می‌کند. اگر first تهی نبود، تنها محل last را تغییر می‌دهد.


حذف یک گره از لیست پیوندی:

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


این تابع ابتدا گره با id مورد نظر را در لیست جستجو می‌کند. اگر چنین گرهی پیدا نشد، بدون انجام عمل دیگری از تابع خارج می‌شود. اشاره‌گر cur به گره حذف‌شدنی اشاره دارد و اشاره‌گر prior به گره قبل از cur. چهار حالت برای گره حذف‌شدنی وجود دارد:
۱- هم گره اول باشد و هم گره آخر.
۲- تنها گره اول باشد.
۳- تنها گره آخر باشد.
۴- نه گره اول باشد و نه گره آخر.
کد بالا برای هر چهار حالت عملیاتی را که لازم است انجام می‌دهد. برای درک بهتر عملکرد تابع فوق، آن را به صورت خط به خط به ازای گره‌هایی که در چهار وضعیت ذکر شده قرار دارند ردیابی کنید.
ما به اشاره‌گر prior نیاز داریم تا بتوانیم گره‌های قبل و بعد از cur را به هم متصل کنیم. حذف یک گره از لیست مانند آن است که حلقه‌ای را از وسط زنجیر جدا کنید. بعد از حذف حلقه، دو تکه زنجیر را باید به هم وصل کرد تا زنجیر کامل به دست بیاید.
آخرین خط تابع فضای cur را نیز که دیگر نیازی به آن نداریم آزاد می‌کند.


درج یک گره در لیست پیوندی:

تایع insert یک گره را به هر نقطه دلخواه لیست پیوندی اضافه می‌کند. این تابع دو ورودی دارد: ورودی اول اطلاعات گره جدید و ورودی دوم محل درج گره، که عموما توسط کلید مشخص می‌شود. به این معنی که گره جدید قبل از گره با کلید مشخص شده قرار می‌گیرد.
 
در اینجا از سه اشاره‌گر استفاده کرده شده است: اشاره‌گر cur برای اشاره به گره جاری، اشاره‌گر prior برای اشاره به گره قبل از cur و بالاخره اشاره‌گر temp برای اشاره به گره جدید. این تابع گره با id تعیین شده را پیدا کرده و گره جدید را قبل از آن درج می‌کند. در واقع گرهی که temp به آن اشاره دارد بین گره‌های cur و prior قرار می‌گیرد.