برنامه لیست پیوندی به زبان c با اصول ساختمان داده ها

یک لیست پیوندی یک طرفه (Singly-linked list) دنباله ای از عناصر داده ای به نام گره(node) است که ترتیب خطی آنها توسط اشاره گرها تعیین می گردد.

عناصر لیست تنها می توانند به ترتیب از ابتدای لیست تا انتها مورد دسترسی قرار بگیرند. هر گره آدرس گره بعدی را شامل می شود که به این صورت امکان پیمایش از یک گره به گره بعدی فراهم می شود.

برای رسم لیست پیوندی گره ها به صورت مستطیل هائی پشت سرهم رسم می شوند که توسط فلش هائی بهم متصل شده اند.

پیاده سازی لیست پیوندی یک طرفه

برای پیاده سازی لیست پیوندی ابتدا باید نوع داده یک گره و متغیرهای موردنیاز تعریف شوند که در زبان C می تواند به صورت زیر نوشته شود:

typedef int ItemType;
typedef struct Node {
ItemType Info;
Node * Next;
};
typedef Node * NodePtr;
NodePtr Front, Rear;
int Count;

در تعریف فوق ItemType نوع داده عناصر لیست را معین می کند که در مثال int درنظر گرفته شده است. ساختمان Node برای تعریف هر گره لیست است که دارای دو فیلد Info و Next است که به ترتیب عنصر داده ای گره و اشاره گر به گره بعدی را ذخیره می کنند. اشاره گر Front برای اشاره به ابتدای لیست در نظر گرفته شده است. گاهی دسترسی سریع به انتهای لیست موردنظر است، به همین دلیل ممکن است اشاره گر Rear را برای اشاره به انتهای لیست اضافه کنیم. متغیر Count تعداد گره های لیست را ذخیره می کند تا هروقت که احتیاج است بدانیم چه تعداد عنصر در لیست وجود دارد از آن استفاده کنیم.

مزیـ اصلی آرایه نسبت به لیست پیوندی این است که آرایه امکان دسترسی تصادفی را می دهد و می توان به هر عنصر مستقیما توسط اندیس آن مراجعه کرد. به همین دلیل در یک آرایه مرتب می توانید از جستجوی باینری به جای جستجوی خطی استفاده کنید. اما با وجودیکه آرایه امکان دسترسی سریعتر به عناصر را می دهد در عملیات درج و حذف ضعیف است و عملیات درج و حذف ممکن است باعث شیفت دادن عناصر زیاد دیگری شود. درحالیکه درج و حذف در لیست راحت تر است و درحقیقت تنها با تغییر اشاره گرها صورت می پذیرد. بنابراین احتمالا زمانی که عملیات درج و حذف زیاد انجام می شود روش بهتری است. تفاوت دیگر میزان فضای موردنیاز دو روش است. آرایه یک ساختمان داده ایستا است. هنگام تعریف، اگر اندازه آرایه را کوچک بگیریم از قدرت برنامه کاسته می شود بنابراین ناگزیریم بیشترین فضای ممکن را درنظر بگیریم که در نتیجه آرایه خیلی بزرگ تعریف می شود و حافظه زیادی مصرف می شود. درحالیکه لیست پیوندی ساختمان داده پویا است یعنی می تواند به راحتی رشد کند یا تحلیل برود یا تغییر کند. البته فضائی از حافظه برای ذخیره باید اشاره گرها صرف شود.

کلا لیست های پیوندی اغلب برای نمایش اطلاعاتی که ویژگی های زیر را دارند بکار می روند:

• تعداد کلی عناصر داده ای از قبل شناخته شده نیست.
• ممکن است عملیات اضافه و حذف زیاد انجام شوند.
• داده ها در یک طریق مرتب یا متوالی ذخیره شوند.
• با داده ذخیره شده به طور وسیع کار شود نه موردی.