لیست های پیوندی ( Linked List ) در ساختمان داده ها

[آبجی]

این نوع ساختار داده ها ساختاری پویا Dynamic است . یعنی به هنگام نیاز به استفاده از حافظه اصلی با درخواستی كه مینماییم بخشی در اختیارمان قرار میگیرد . و در صورت عدم نیاز با رها سازی ان بخش به مجموعه حافظه قابل استفاده باز میگردد .

یادآوری میکنم که ساختار ایستا یا آرایه ساختاری است که توانایی كم و زیاد شدن حافظه در ساختار مربوطه را نداریم. تفاوت لیست پیوندی با آرایه در ان است كه اعضا در لیست پیوندی پراكنده هستند .

هر عنصر لیست پیوندی در كنار خود حداقل یك بخش جهت حفظ آدرس عضو بعدی وجود دارد . در نتیجه یك خانه دو قسمتی است :
كه خانه سمت راست آدرس لیست پیوندی بعد از خود را نشان میدهد . ( اشاره گریست به خانه بعد از خود ) و خانه سمت چپ اطلاعات را نگهداری میكند .
برای نمایش خانه سمت چپ و اینكه محتویات این عنصر چیست از (Info(Address مثل (Info(345H برای نمایش خانه سمت راست عنصر و اینكه این عنصر به كدام خانه بعد از خود اشاره میكند از (Link(Address مثل (Link(354H استفاده میكنیم .
در این لیست ها كه لیست های یكطرفه Single Link List گفته میشود اطلاعات تنها یك آدرس حفظ میشود . آدرس شروع در این ساختمان داده ای بسیار مهم است كه ان را در متغیری كمكی به نام First نگهداری میكنیم .


محدوده موجودیت Availability Area
محدوده ایست كه در آن عناصر لیست های پیوندی در اختیار قرار میگیرند . در ساختارهای پیوندی درج و حذف اطلاعات فیزیكی است به منظور درك بهتر عملیات را خود انجام میدهیم . باین منظور فرض میكنیم مجموعه موجودیت عناصرش روی هم stack شده اند . بنابراین مجموعه stack گونه ای را ایجاد نموده اند ( Availability Stack ) گویند . اشاره پیكان ها میتواند به هر نقطه ای باشد . به نقطه بالایی این محیط Avail گوییم .

[آبجی]

الگوریتم درج در یك لیست پیوندی مرتب ( صعودی )

در این مرحله از الگوریتم مقدار x را در مقدار (info(new میریزیم .

کد:
5.[check is the list empty ?]
if first=null
then link(new):=null
return(new)



در این مرحله چك میشود كه ایا اصلا لیست عضوی دارد اگر ندارد لینك new پوچ شود و مقدار new بعنوان first به برنامه فراخوان Postback شود .

کد:
6.[does the new node proceed of the others ? ]
IF info(new)<=info(first)
link(new):=first
return(new)



در این مرحله تست میشود كه ایا عضو اول ما از مقدار جدید كه قرار است اضافه شود كوچكتر است یا خیر در غیر اینصورت new ما first لیست شود .

کد:
7.[initialize search for last node]
save:=first



باز هم یك كپی از first بر میداریم .

کد:
8.[search for prodecessor of new node ? ]
repeat while link(save)<> null and info(link(save))<=info(new)
save:=link(save)



تا وقتی كه لیست به پایان نرسیده است و محتویات link(save) از محتویات new كوچكتر نشده است به كار خود ادامه دهد . و مداما save را بروز برساند و به عنصر بعدی اشاره كند

کد:
9.[set link fields of new node and its prodecessor]
link(new):=link(save)
link(save):=new
10.[return first node pointer]
return(first)

[بانوثریا]

البته چند نوع الگوریتم درج داریم
درج در ابتدا
درج در انتها
درج مابین
که هر کدام روش های بخصوصی داره

[بانوثریا]

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

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

http://hpkclasses.ir/Courses/DataStructure/ds0502.GIF
مقدار ثابت NULL برای علامتگذاری انتهای ليست در اشاره گر آخرين گره ذخيره می شود.
ليست توسط يک اشاره گر Head که آدرس اولين گره ليست را در خود ذخيره می کند قابل دسترس است. بقيه عناصر توسط جستجوی خطی بدست می آيند.

[بانوثریا]

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

[بانوثریا]

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

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

http://hpkclasses.ir/Courses/DataStructure/ds0503.GIF
در ابتدای برنامه متغيرهای Front و Rear بايد برابر با NULL شوند تا يک ليست تهی ايجاد شود.
void CreateEmptyList(void)
{
Front = NULL;
Rear = Front;
Count = 0;
}
برای پياده سازی يک ليست پيوندی، عمليات اصلی شامل موارد زير هستند:

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

[بانوثریا]

درج يک گره در ابتدای ليست

يک گره جديد می تواند در هر جائی از ليست اضافه شود؛ ابتدا، انتها يا ميان ليست. حالت زير را درنظر بگيريد که می خواهيم گره جديد Current را به ابتدای يک ليست موجود اضافه کنيم.

http://hpkclasses.ir/Courses/DataStructure/ds0505.GIF
اشاره گر Current به گره جديد اشاره می کند. فيلد Next اين گره بايد مقدار Front مقداردهی شود تا به اولين گره ليست اشاره کند. با اضافه شدن گره جديد به ابتدای ليست اشاره گر Front بايد تغيير کند و به گره ابتدا که اکنون گره Current است اشاره کند. متغير Count در انتها يک واحد اضافه می شود.
void InsertFirst(const ItemType & Item)
{
NodePtr Current;
Current = GetNode(Item, Front);
Front = Current;
if (Count == 0)
Rear = Current;
Count++;
}
تابع GetNode برای ايجاد يک گره و ذخيره داده در آن فراخوانی می شود. پارامتر دوم تابع مقدار فيلد Next گره جديد را معين می کند.
در حالتی که گره جديد به ابتدای يک ليست خالی اضافه می شود(يعنی وقتی Count=0 است) بايد اشاره گر Rear هم تنظيم شود تا به گره جديد که اولين و آخرين گره ليست محسوب می شود اشاره کند

[بانوثریا]

درج يک گره در انتهای ليست

برای اضافه کردن يک گره در انتهای ليست گره Current بايد بعد از آخرين گره ليست که آدرس آن در اشاره گر Rear نگهداری می شود درج شود.

http://hpkclasses.ir/Courses/DataStructure/ds0506.GIF
فيلد Next آخرين گره به گره جديد بايد اشاره کند . بعد از اضافه شدن گره در انتهای ليست اشاره گر Rear برابر با آدرس گره آخر می شود.
void InsertLast(const ItemType & Item)
{
NodePtr Current;
Current = GetNode(Item, NULL);
Rear->Next = Current;
Rear = Current;
Count++;
}

[بانوثریا]

وقتی ليست مرتب است گره جديد بايد در محلی اضافه شود که ترتيب گره های ليست حفظ شود. بنابراين ابتدا بايد محل درج گره جديد در ليست پيدا شود سپس اشاره گرها تنظيم شوند.

[بانوثریا]

ليست پيوندی حلقوی

در مثال قبل احتياج به يک گره آغازين و يک گره پايانی بود. ابتدای ليست توسط يک اشاره گر خاص (در مثال قبل Front) و انتهای ليست توسط گره ای که اشاره گر آن برابر با NULL است مشخص می شود. اگر مسئله به عملياتی نياز دارد که روی يک گره ليست پيوندی انجام می شود که مهم نيست گره اول يا آخرتوسط يک ليست پيوندی حلقوی حل می شود.
ليست حلقوی(circular list) ليست پيوندی است که آخرين گره آن به اولين گره ليست اشاره می کند. ليست حلقوی اشاره گر تهی ندارد و فيلد Next آخرين گره با آدرس گره اول مقداردهی می شود.
Rear->Next = Front;
عمليات درج، حذف و جستجو مانند ليست پيوندی است.

http://hpkclasses.ir/Courses/DataStructure/ds0507.GIF

[بانوثریا]

يکی از کاربردهای ليست حلقوی در اشتراک زمانی است که سيستم عامل ليستی از کاربران را دارد و به طور تناوبی به هر کاربر برش کوچکی از وقت پردازنده را اختصاص می دهد. هر بار يک کاربر را انتخاب می کند و مقداری از وقت پردازنده را می دهد سپس به کاربر بعدی منتقل می شود.

[بانوثریا]

ليست پيوندی دوطرفه

در ليست يک طرفه فقط می توانيم در يک جهت پيمايش کنيم. گاهی پيمايش روی ليست از هردوطرف مورد نياز است. بنابراين در هر گره به دو فيلد اشاره گر نياز است؛ برای اشاره به گره بعدی و گره قبلی که اغلب اشاره گرهای Left و Right ناميده می شوند. ليستی که شامل اين نوع گره باشد را ليست پيوندی دوطرفه (doubly-linked list) می نامند. شکل زير ساختار گره را نشان می دهد.

http://hpkclasses.ir/Courses/DataStructure/ds0508.GIF
اگر ليست به صورت افقی ترسيم شود اشاره گرهای Right برای پيمايش ليست از چپ به راست (از ابتدا به انتها) استفاده می شوند. توسط اشاره گرهای Left می توان در صورت نياز به گره قبلی برگشت. بنابراين امکان پيمايش ليست در هردو جهت وجود دارد.

http://hpkclasses.ir/Courses/DataStructure/ds0509.GIF
همين طور که در شکل ديده می شود اشاره گر Left اولين گره و اشاره گر Right آخرين گره ليست NULL هستند که نشان دهنده ابتدای هر جهت می باشند.

[بانوثریا]

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

[بانوثریا]

مقايسه ليست پيوندی و آرايه

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

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