تماس درباره   صفحه اصلی
  ساختمان داده > ليست پيوندي  
 
 

ليست پيوندي


ليست پيوندی ساختاری است که ترتيب خطی عناصر داده ای در آن توسط اشاره گرها تعيين می شود.

ليست پيوندي يک طرفه
ليست پيوندي حلقوي
ليست پيوندي دوطرفه
مقايسه ليست پيوندي و آرايه


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

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

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

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

Linked list

مقدار ثابت NULL برای علامتگذاری انتهای ليست در اشاره گر آخرين گره ذخيره می شود.

ليست توسط يک اشاره گر Head که آدرس اولين گره ليست را در خود ذخيره می کند قابل دسترس است. بقيه عناصر توسط جستجوی خطی بدست می آيند.


پياده سازي ليست پيوندي يک طرفه به زبان C++


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

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

Linked list

در ابتدای برنامه متغيرهای Front و Rear بايد برابر با NULL شوند تا يک ليست تهی ايجاد شود.

void CreateEmptyList(void)
{
   Front = NULL;
   Rear = Front;
   Count = 0;
}

برای پياده سازی يک ليست پيوندی، عمليات اصلی شامل موارد زير هستند:

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


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

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

Insert into Linked list

اشاره گر Current به گره جديد اشاره می کند. فيلد Next اين گره بايد مقدار Front مقداردهی شود تا به اولين گره ليست اشاره کند. با اضافه شدن گره جديد به ابتدای ليست اشاره گر Front بايد تغيير کند و به گره ابتدا که اکنون گره Current است اشاره کند. متغير Count در انتها يک واحد اضافه می شود.

void InsertFirst( ItemType Item)
{
   NodePtr Current;
   Current = new Node;
   if (current == NULL)
      {
      cerr << "Memory allocation error!" << endl;
      exit(1);
      }
   current->Next = Front;
   current->Info = item;
   Front = current;
   if (Count == 0)
      Rear = current;
   Count++;
}

در حالتی که گره جديد به ابتدای يک ليست خالی اضافه می شود(يعنی وقتی Count=0 است) بايد اشاره گر Rear هم تنظيم شود تا به گره جديد که اولين و آخرين گره ليست محسوب می شود اشاره کند.


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

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

Insert into Linked list

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

void InsertLast(ItemType & Item)
{
   NodePtr Current;
   current = new Node;
   if (current == NULL)
      {
      cerr << "Memory allocation error!" << endl;
      exit(1);
      }
   current->Next = NULL;
   current->Info = item;
   if (Count == 0)
      Front = current;
   else
      Rear->Next = current;
   Rear = current;
   Count++;
}


در حالتی که گره جديد به انتهای يک ليست خالی اضافه می شود(يعنی وقتی Count=0 است) بايد اشاره گر Front هم تنظيم شود تا به گره جديد که اولين و آخرين گره ليست محسوب می شود اشاره کند.

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


حذف يک گره از ابتدای ليست

عمل حذف از درج ساده تر است. البته احتمال يک پيغام خطا وقتی که ليست تهی است وجود دارد. در ساده ترين حالت حذف از ابتدای ليست صورت می گيرد. آدرس اولين گره در متغير اشاره گر Current ذخيره می شود. مقدار فيلد Info اين گره در متغير Item نگهداری می شود. سپس فيلد Next گره اول برای اشاره به گره دوم ليست تنظيم می شود. حافظه گره ای که از ليست حذف شده است توسط دستور free آزاد می شود. در انتها از متغير Count يک واحد کم می شود.

يک حالت استثنا وجود دارد وقتی که ليست تنها شامل يک گره است و با حذف آن Rear بايد برابر با NULL شود.

void RemoveFirst(ItemType &Item)
{
   NodePtr Current;
   if (Count == 0) {
      cerr << "ERROR: there is no item to remove in the list!" << endl;
      exit(1);
   }
   Current = Front;
   Item = Current->Info;
   Front = Current->Next;
   Count--;
   if (Count == 0)
      Rear = Front;
   delete Current;
}


جستجو در ليست

تا وقتی که ليست تهی نيست می توانيم داده معينی را در ليست جستجو کنيم. جستجو از ابتدای ليست آغاز می شود. اشاره گر Current برای جلو رفتن روی گره های ليست استفاده می شود و در ابتدا آدرس اولين گره در آن قرار می گيرد. در صورت وجود گره مورد نظر در ليست آدرس آن که در Current است برگردانده می شود.


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

در مثال قبل احتياج به يک گره آغازين و يک گره پايانی بود. ابتدای ليست توسط يک اشاره گر خاص (در مثال قبل Front) و انتهای ليست توسط گره ای که اشاره گر آن برابر با NULL است مشخص می شود. اگر مسئله به عملياتی نياز دارد که روی يک گره ليست پيوندی انجام می شود که مهم نيست گره اول يا آخرتوسط يک ليست پيوندی حلقوی حل می شود.

ليست حلقوی(circular list) ليست پيوندی است که آخرين گره آن به اولين گره ليست اشاره می کند. ليست حلقوی اشاره گر تهی ندارد و فيلد Next آخرين گره با آدرس گره اول مقداردهی می شود.

Rear->Next = Front;

عمليات درج، حذف و جستجو مانند ليست پيوندی است.

Circular list

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


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

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

Doubly-Linked list node

اگر ليست به صورت افقی ترسيم شود اشاره گرهای Right برای پيمايش ليست از چپ به راست (از ابتدا به انتها) استفاده می شوند. توسط اشاره گرهای Left می توان در صورت نياز به گره قبلی برگشت. بنابراين امکان پيمايش ليست در هردو جهت وجود دارد.

Doubly-Linked list

همين طور که در شکل ديده می شود اشاره گر Left اولين گره و اشاره گر Right آخرين گره ليست NULL هستند که نشان دهنده ابتدای هر جهت می باشند.


پياده سازي ليست پيوندي دو طرفه به زبان C++


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

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

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

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


تمرينات ليست پيوندي

سوالات چندگزينه اي درباره ليست پيوندي


 


 


صفحه اصلی| PDF| درباره| تماس