ساختار داده اي ليست پيوندي Linked List

[Y@SiN]

اين ساختار ‍ ساختاري پويا Dynamic است . يعني به هنگام نياز به استفاده از حافظه اصلي با درخواستي كه مينماييم بخشي در اختيارمان قرار ميگيرد . و در صورت عدم نياز با رها سازي ان بخش به مجموعه حافظه قابل استفاده باز ميگردد .
يادآوري ( ايستايي )‌:‌( آرايه )‌در صورتي كه توانايي كم و زياد شدن حافظه در ساختار مربوطه را نداشته باشيم .
تفاوت ليست پيوندي با آرايه در ان است كه اعضا در ليست پيوندي پراكنده هستند .
هر عنصر ليست پيوندي در كنار خود حداقل يك بخش جهت حفظ آدرس عضو بعدي وجود دارد . در نتيجه يك خانه دو قسمتي است :
كه خانه سمت راست آدرس ليست پيوندي بعد از خود را نشان ميدهد . ( اشاره گريست به خانه بعد از خود . )
و خانه سمت چپ اطلاعات را نگهداري ميكند .
براي نمايش خانه سمت چپ و اينكه محتويات اين عنصر چيست از Info(Address) مثل Info(345H)
براي نمايش خانه سمت راست عنصر و اينكه اين عنصر به كدام خانه بعد از خود اشاره ميكند از Link(Address) مثل Link(354H) استفاده ميكنيم .
در اين ليست ها كه ليست هاي يكطرفه Single Link List گفته ميشود اطلاعات تنها يك آدرس حفظ ميشود . آدرس شروع در اين ساختمان داده اي بسيار مهم است كه ان را در متغيري كمكي به نام First نگهداري ميكنيم .
محدوده موجوديت Availability Area
محدوده ايست كه در آن عناصر ليست هاي پيوندي در اختيار قرار ميگيرند . در ساختار پيوندي درج و حذف اطلاعات فيزيكي است .
به منظور درك بهتر عمليات را خود انجام ميدهيم . باين منظور فرض ميكنيم مجموعه موجوديت عناصرش روي هم stack شده اند . بنابراين مجموعه stack گونه اي را ايجاد نموده اند و بناربراين به ان Availability Stack گويند . اشاره پيكان ها ميتواند به هر نقطه اي باشد . به نقطه بالايي اين محيط Avail گوييم .
الگوريتمي بنويسيد براي درج عضو جديد در ابتداي يك ليست پيوندي :

Function Insert(X,First) 
1.[UnderFlow?] 
   IF Avail=null 
   Then write('availability stack,  UnderFlow ') 
   return(first) 
2.[obtain Address Of Free Node ] 
   new := Avail 
3.[remove node from availability stack] 
  Avail:=Link(Avail) 
4.[Set Fields of new] 
  Info(New):=X 
  Link(New):=First 
5.[Exit] 
return(new)

الگوريتم فوق را اينگونه فراخواني كرده ايم :‌ First = Insert(X,First) كه در آن X مقداريست كه ميخواهيم در ليست اضافه كنيم . و First اشاره گريست به خانه اول ليست .
در گام اول الگوريتم چك كرده ايم كه آيا حافظه ما خانه خالي دارد ؟ اگر ندارد عملياتي انجام ندهد و همان first را دست نخورده بازگرداند .
در گام دوم به new ميگوييم به همان خانه ايكه Avail اشاره ميكند اشاره كند .
در گام سوم مقدار Link(Avail) را به Avail ميريزيم تا يك خانه از حافظه ما براي عمليات آزاد شود . يعني Avail يك خانه در حافظه فرضي ما پايين امده است .
در مرحله چهارم X را به اطلاعات New و سپس Link(New) را گوييم كه به first اشاره كند . در نهايت مقدار new به جاي First برگرداننده ميشود .
الگوريتم درج يك عضو در انتهاي يك ليست پيوندي

Function InsEnd(X,First) 
1.[UnderFlow?] 
IF Avail=Null 
   Then write('Availability Stack UnderFlow') 
   return(First) 
2.[obtain Address Of free node] 
  New:=Avail 
3.[Remove Node from availability stack] 
Avail:=Link(Avail) 
4.[set fields of new node] 
  Info(new):=X 
  Link(new):=null 
5.[is the list empty ? ] 
  If First=Null 
   Then return(new) 
6.[Initialize seach for last node] 
  save:=first 
7.[search for end of list] 
repeat while link(save)<>null 
   save:=link(save) 
8.[set link field of last node to new] 
link(save):=new 
9.[finished] 
  return(first)

سه مرحله اول از اين الگوريتم دقيقا مانند الگوريتم قبل است .
در مرحله چهار عنصر جديد مقدار دهي ميشود وچون قرار است اخر ليست قرار بگيرد مقدار null در ادرس ان قرار ميدهيم .
در مرحله پنجم چك ميشود كه آيا ليست پيوندي اصلا عضوي دارد ؟ اگر ندارد new بعنوان first بازگردانده ميشود .
مرحله ششم به save ميگوييم كه به first اشاره كند . چراكه همانطور كه گفتيم مقدار first حياتي ترين مقدار در ليست پيوندي است لذا يك كپي از ان بر ميداريم و به ادامه كارميپردازيم .
مرحله هفتم ميگويد تا وقتي كه اشاره گر save به null اشاره نكرده است save را يك مقدار به جلو بدهد .
در مرحله هشتم link(save) را ميگوييم كه به new اشاره كند تا الگوريتم به پايان برسد .

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

Function InsOrd(X,First) 
1.[underflow?] 
   IF avail=null 
   then write('availability stack underflow') 
   return(first) 
2.[obtain address of free node] 
  new:=avail 
3[remove node from availability stack] 
avail:=link(avail) 
4.[copy information info(new)] 
   info(new):=x

در اين مرحله از الگوريتم مقدار 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)

الگوريتم حذف از يك عنصر :

 
Procedure Delete(X,First) 
1.[empty first?] 
IF first=null 
Then write('UnderFlow?') 
Exit 
2.[initialize search for X ] 
empty:=first 
3.[find x] 
repeat thru step5 while link(temp) <> null and temp<>x 
4.[update prodecessor marker] 
pred:=temp 
5.[move to next node] 
temp:=link(temp) 
6.[end of first ?] 
if temp<>x 
then write('node not found') 
exit 
7.[delete x] 
if x=first 
then first:=link(first) 
else link(pred):=link(x) 
8.[return node to availability stack] 
link(x):=avail 
avail:=x 
exit

اين الگوريتم را ميتوان به شيوه هاي گوناگوني نوشت كه اينگونه شايد واضح ترين ان باشد .

[Y@SiN]