يک ليست پيوندی يک طرفه (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 تعداد گره های ليست را ذخيره می کند تا هروقت که احتياج است بدانيم چه تعداد عنصر در ليست وجود دارد از آن استفاده کنيم.

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

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

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