لیست پیوندی یک طرفه، دو طرفه و حلقوی — ساختمان داده و الگوریتم ها

لیست پیوندی یک توالی از ساختارهای داده‌ای است که از طریق پیوندهایی به هم مربوط شده‌اند. لیست پیوندی در واقع یک توالی از لیست‌ها هستند که شامل آیتم‌هایی می‌شوند. هر پیوند شامل اتصال به پیوندهای دیگر است. لیست پیوندی پس از آرایه‌ها دومین ساختمان داده پر کاربرد محسوب می‌شود. در ادامه برخی اصلاح‌های مهم برای درک مفهوم لیست پیوندی ارائه شده است:

• پیوند (Link): هر پیوند به یک لیست پیوندی می‌تواند داده‌هایی که عنصر نامیده می‌شوند را در خود ذخیره سازد.
• بعدی (Next): هر پیوند به یک لیست پیوندی شامل یک پیوند به لیست بعدی است که Next نامیده می‌شود.
• لیست پیوندی (LinkedList): لیست پیوندی شامل پیوند اتصال به پیوند نخست است که First نامیده می‌شود.

نمایش لیست پیوندی

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

همان طور که در شکل فوق مشخص است، نقاط زیر در یک لیست پیوندی مهم هستند:

• لیست پیوندی شامل یک عنصر پیوندی است که آغاز (first) نامیده می‌شود.
• هر لینک فیلدهای داده‌ای و همچنین یک فیلد پیوند دارد که بعدی (next) نامیده می‌شود.
• هر لینک با استفاده از پیوند next به پیوند بعدی خود مربوط می‌شود.
• هر لینک که یک پیوند null داشته باشد به معنی انتهای لیست است.

انواع لیست پیوندی

در ادامه انواع مختلف لیست‌های پیوندی فهرست شده است:

فیلم آموزش ساختمان داده ها در فرادرس

کلیک کنید

• لیست پیوندی ساده: جهت آیتم‌ها تنها به سمت جلو است.
• لیست پیوندی دو طرفه: آیتم‌ها می‌توانند به سمت جلو یا عقب لینک شوند
• لیست پیوندی حلقوی: آیتم آخر شامل پیوندی به صورت next به عنصر نخست است و عنصر اول نیز پیوندی به صورت previous به عنصر آخر دارد.

عملیات‌های ابتدایی

در ادامه فهرستی از عملیات‌های ابتدایی که می‌توان روی یک لیست انجام داد ارائه شده است:

• درج (Insertion): یک عنصر به ابتدای لیست اضافه می‌کند.
• حذف (Deletion): یک عنصر را از ابتدای لیست حذف می‌کند.
• نمایش (Display): لیست کامل را نمایش می‌دهد.
• جستجو (Search): یک عنصر را با استفاده از کلید مفروض جستجو می‌کند.
• حذف (Delete): یک عنصر را با استفاده از کلید مفروض حذف می‌کند.

عملیات درج

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

تصور کنید که می‌خواهیم یک گره B (گره جدید) را بین گره A (گره چپ) و گره C (گره راست) درج کنیم. در این صورت B باید به C به عنوان next اشاره کند:

NewNode.next −> RightNode;

این عملیات به صورت زیر خواهد بود:

اینک گره سمت چپ باید به گره جدید اشاره کند:

LeftNode.next −> NewNode;

بدین ترتیب گره جدید در میان دو گره قبلی قرار می‌گیرد. لیست جدید به صورت زیر خواهد بود:

اگر بخواهیم گرهی را در ابتدای لیست اضافه کنیم نیز مراحل مشابهی را طی می‌کنیم. زمانی که می‌خواهیم گرهی را در انتهای لیست درج کنیم، گره ما قبل آخر باشد به گره جدید اشاره کند و گره جدید به یک مقدار null اشاره می‌کند.

عملیات حذف

حذف نیز یک فرایند چندمرحله‌ای است. این عملیات را با نمودارهایی توضیح می‌دهیم. ابتدا گره هدف که می‌خواهیم حذف کنیم را با استفاده از الگوریتم‌های جستجو می‌یابیم.

گره چپ (قبلی) گره هدف اینک باید به گره بعد از گره هدف اشاره کند:

LeftNode.next −> TargetNode.next;

با این کار پیوندی که به گره هدف وجود داشت از بین می‌رود. اینک با استفاده از کد زیر موردی که گره هدف به آن اشاره می‌کرد را نیز حذف می‌کنیم:

TargetNode.next −> NULL;

ما باید از گره حذف شده استفاده کنیم. ما می‌توانیم آن را در حافظه نگه داریم و یا به سادگی آن حافظه را به چیز دیگری تخصیص دهیم و گره هدف را به طور کامل پاک کنیم.

عملیات معکوس سازی (Reverse)

این عملیات یک مرحله‌ای است. ما باید کاری کنیم که گره آخر به سمت گره اول اشاره کند و جهت کل لیست پیوندی را معکوس بکنیم.

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

باید مطمئن شویم که گره آخر، دیگر آخرین گره نیست. بنابراین یک گره موقتی داریم که شبیه گره اول به نظر می‌رسد و به گره قبلی خود اشاره می‌کند. اینک همه گره‌های سمت چپ به جز گره اول را یک به یک طوری تنظیم می‌کنیم که به گره‌های قبلی خود اشاره کنند.

وقتی به گره اول رسیدیم، همه گره‌ها باید به گره قبلی خود ارائه کرده باشند. گره اول نیز به یک مقدار null اشاره می‌کند.

با استفاده از یک گره موقت کاری می‌کنیم که گره اول به گره قبلی خود اشاره کند.

لیست پیوندی این معکوس شده است. در ادامه پیاده‌سازی عملی یک لیست پیوندی در زبان C اراده شده است.

#include 
#include 
#include 
#include 

struct node {
   int data;
   int key;
   struct node *next;
};

struct node *head = NULL;
struct node *current = NULL;

//display the list
void printList() {
   struct node *ptr = head;
   printf("\n[ ");
	
   //start from the beginning
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
	
   printf(" ]");
}

//insert link at the first location
void insertFirst(int key, int data) {
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
	
   link->key = key;
   link->data = data;
	
   //point it to old first node
   link->next = head;
	
   //point first to new first node
   head = link;
}

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //mark next to first link as first 
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

//is list empty
bool isEmpty() {
   return head == NULL;
}

int length() {
   int length = 0;
   struct node *current;
	
   for(current = head; current != NULL; current = current->next) {
      length++;
   }
	
   return length;
}

//find a link with given key
struct node* find(int key) {

   //start from the first link
   struct node* current = head;

   //if list is empty
   if(head == NULL) {
      return NULL;
   }

   //navigate through list
   while(current->key != key) {
	
      //if it is last node
      if(current->next == NULL) {
         return NULL;
      } else {
         //go to next link
         current = current->next;
      }
   }      
	
   //if data found, return the current Link
   return current;
}

//delete a link with given key
struct node* delete(int key) {

   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;
	
   //if list is empty
   if(head == NULL) {
      return NULL;
   }

   //navigate through list
   while(current->key != key) {

      //if it is last node
      if(current->next == NULL) {
         return NULL;
      } else {
         //store reference to current link
         previous = current;
         //move to next link
         current = current->next;
      }
   }

   //found a match, update the link
   if(current == head) {
      //change first to point to next link
      head = head->next;
   } else {
      //bypass the current link
      previous->next = current->next;
   }    
	
   return current;
}

void sort() {

   int i, j, k, tempKey, tempData;
   struct node *current;
   struct node *next;
	
   int size = length();
   k = size ;
	
   for ( i = 0 ; i < size - 1 ; i++, k-- ) { current = head; next = head->next;
		
      for ( j = 1 ; j < k ; j++ ) { if ( current->data > next->data ) {
            tempData = current->data;
            current->data = next->data;
            next->data = tempData;

            tempKey = current->key;
            current->key = next->key;
            next->key = tempKey;
         }
			
         current = current->next;
         next = next->next;
      }
   }   
}

void reverse(struct node** head_ref) {
   struct node* prev   = NULL;
   struct node* current = *head_ref;
   struct node* next;
	
   while (current != NULL) {
      next  = current->next;
      current->next = prev;   
      prev = current;
      current = next;
   }
	
   *head_ref = prev;
}

void main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 

   printf("Original List: "); 
	
   //print list
   printList();

   while(!isEmpty()) {            
      struct node *temp = deleteFirst();
      printf("\nDeleted value:");
      printf("(%d,%d) ",temp->key,temp->data);
   }  
	
   printf("\nList after deleting all items: ");
   printList();
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   
   printf("\nRestored List: ");
   printList();
   printf("\n");  

   struct node *foundLink = find(4);
	
   if(foundLink != NULL) {
      printf("Element found: ");
      printf("(%d,%d) ",foundLink->key,foundLink->data);
      printf("\n");  
   } else {
      printf("Element not found.");
   }

   delete(4);
   printf("List after deleting an item: ");
   printList();
   printf("\n");
   foundLink = find(4);
	
   if(foundLink != NULL) {
      printf("Element found: ");
      printf("(%d,%d) ",foundLink->key,foundLink->data);
      printf("\n");
   } else {
      printf("Element not found.");
   }
	
   printf("\n");
   sort();
	
   printf("List after sorting the data: ");
   printList();
	
   reverse(&head);
   printf("\nList after reversing the data: ");
   printList();
}

اگر کد فوق را کامپایل و اجرا کنیم خروجی زیر به دست می‌آید:

خروجی

Original List:

[(6,56) (5,40) (4,1) (3,30) (2,20) (1,10)]

Deleted value: (6,56)

Deleted value: (5,40)

Deleted value: (4,1)

Deleted value: (3,30)

Deleted value: (2,20)

Deleted value: (1,10)

List after deleting all items:

[]

Restored List:

[(6,56) (5,40) (4,1) (3,30) (2,20) (1,10)]

Element found: (4,1)

List after deleting an item:

[(6,56) (5,40) (3,30) (2,20) (1,10)]

Element not found.

List after sorting the data:

[(1,10) (2,20) (3,30) (5,40) (6,56)]

List after reversing the data:

[(6,56) (5,40) (3,30) (2,20) (1,10)]

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

لیست پیوندی دو طرفه نسخه‌ای از لیست پیوندی است که حرکت در هر دو جهت یعنی به سمت جلو یا عقب در آن امکان‌پذیر است.

فیلم آموزش ساختمان داده ها در فرادرس

کلیک کنید

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

همان طور که در شکل فوق مشاهده می‌شود، نقاط مهمی در این نوع لیست وجود دارند که در ادامه توضیح داده شده‌اند:

• لیست پیوندی دوطرفه شامل عناصر پیوندی است که عنصر اول و آخر نامیده می‌شوند.
• هر پیوند یک فیلد داده‌ای و دو فیلد پیوندی دارد که پیوندهای قبلی و بعدی نامیده می‌شوند.
• هر عنصر با استفاده از پیوند بعدی (next) به عنصر بعدی خود اتصال یافته است.
• هر عنصر با استفاده از پیوند قبلی (previous) به عنصر قبلی خود اتصال یافته است.
• عنصر آخر یک پیوند به صورت null دارد که انتهای لیست را مشخص می‌کند.

عملیات‌های ابتدایی

• درج (Insertion): یک عنصر به ابتدای لیست اضافه می‌کند.
• حذف (Deletion): یک عنصر از ابتدای لیست حذف می‌کند.
• درج انتها (Insert Last): یک عنصر به انتهای لیست اضافه می‌کند.
• حذف انتها (Delete Last): یک عنصر از انتهای لیست حذف می‌کند.
• درج بعد (Insert After): یک عنصر پس از یک آیتم لیست اضافه می‌کند.
• حذف موردی (Delete): یک عنصر را با استفاده از یک کلید از لیست حذف می‌کند.
• نمایش رو به جلو (Display forward): لیست کامل را به روش رو به جلو نمایش می‌دهد.
• نمایش رو به عقب (Display backward): لیست کامل را به روش رو به عقب نمایش می‌دهد:

عملیات درج

کدی که در ادامه آمده است عملیات درج در ابتدای یک لیست پیوندی دو طرفه را نمایش می‌دهد:

مثال

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

عملیات حذف

کدی که در ادامه آمده است عملیات حذف را از ابتدای یک لیست پیوندی دوطرفه نمایش می‌دهد.

مثال

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

درج در انتهای یک عملیات

در ادامه کدی ارائه شده است که عملیات درج در موقعیت آخر یک لیست پیوندی دو طرفه را نمایش می‌دهد.

مثال

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

پیاده‌سازی عملی لیست پیوندی دوطرفه و همه عملیات‌های آن در کد زیر ارائه شده است:

پیاده‌سازی در زبان C

#include 
#include 
#include 
#include 

struct node {
   int data;
   int key;
	
   struct node *next;
   struct node *prev;
};

//this link always point to first Link
struct node *head = NULL;

//this link always point to last Link 
struct node *last = NULL;

struct node *current = NULL;

//is list empty
bool isEmpty() {
   return head == NULL;
}

int length() {
   int length = 0;
   struct node *current;
	
   for(current = head; current != NULL; current = current->next){
      length++;
   }
	
   return length;
}

//display the list in from first to last
void displayForward() {

   //start from the beginning
   struct node *ptr = head;
	
   //navigate till the end of the list
   printf("\n[ ");
	
   while(ptr != NULL) {        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
	
   printf(" ]");
}

//display the list from last to first
void displayBackward() {

   //start from the last
   struct node *ptr = last;
	
   //navigate till the start of the list
   printf("\n[ ");
	
   while(ptr != NULL) {    
	
      //print data
      printf("(%d,%d) ",ptr->key,ptr->data);
		
      //move to next item
      ptr = ptr ->prev;
      
   }
	
}

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL){
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
   //return the deleted link
   return tempLink;
}

//delete link at the last location

struct node* deleteLast() {
   //save reference to last link
   struct node *tempLink = last;
	
   //if only one link
   if(head->next == NULL) {
      head = NULL;
   } else {
      last->prev->next = NULL;
   }
	
   last = last->prev;
	
   //return the deleted link
   return tempLink;
}

//delete a link with given key

struct node* delete(int key) {

   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;
	
   //if list is empty
   if(head == NULL) {
      return NULL;
   }

   //navigate through list
   while(current->key != key) {
      //if it is last node
		
      if(current->next == NULL) {
         return NULL;
      } else {
         //store reference to current link
         previous = current;
			
         //move to next link
         current = current->next;             
      }
   }

   //found a match, update the link
   if(current == head) {
      //change first to point to next link
      head = head->next;
   } else {
      //bypass the current link
      current->prev->next = current->next;
   }    

   if(current == last) {
      //change last to point to prev link
      last = current->prev;
   } else {
      current->next->prev = current->prev;
   }
	
   return current;
}

bool insertAfter(int key, int newKey, int data) {
   //start from the first link
   struct node *current = head; 
	
   //if list is empty
   if(head == NULL) {
      return false;
   }

   //navigate through list
   while(current->key != key) {
	
      //if it is last node
      if(current->next == NULL) {
         return false;
      } else {           
         //move to next link
         current = current->next;
      }
   }
	
   //create a link
   struct node *newLink = (struct node*) malloc(sizeof(struct node));
   newLink->key = newKey;
   newLink->data = data;

   if(current == last) {
      newLink->next = NULL; 
      last = newLink; 
   } else {
      newLink->next = current->next;         
      current->next->prev = newLink;
   }
	
   newLink->prev = current; 
   current->next = newLink; 
   return true; 
}

void main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 

   printf("\nList (First to Last): ");  
   displayForward();
	
   printf("\n");
   printf("\nList (Last to first): "); 
   displayBackward();

   printf("\nList , after deleting first record: ");
   deleteFirst();        
   displayForward();

   printf("\nList , after deleting last record: ");  
   deleteLast();
   displayForward();

   printf("\nList , insert after key(4) : ");  
   insertAfter(4,7, 13);
   displayForward();

   printf("\nList  , after delete key(4) : ");  
   delete(4);
   displayForward();
}

اگر کد فوق را کامپایل و اجرا کنیم، نتیجه زیر به دست می‌آید:

خروجی

List (First to Last):

[(6,56) (5,40) (4,1) (3,30) (2,20) (1,10)]

List (Last to first):

[(1,10) (2,20) (3,30) (4,1) (5,40) (6,56)]

List, after deleting first record:

[(5,40) (4,1) (3,30) (2,20) (1,10)]

List, after deleting last record:

[(5,40) (4,1) (3,30) (2,20)]

List, insert after key(4):

[(5,40) (4,1) (4,13) (3,30) (2,20)]

List, after delete key(4):

[(5,40) (4,13) (3,30) (2,20)]

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

لیست پیوندی حلقوی نسخه‌ای از لیست پیوندی است که در آن عنصر نخست به عنصر آخر اشاره می‌کند و عنصر آخر نیز به عنصر اول اشاره دارد. هر دو نوع لیست پیوندی یک طرفه (ساده) و دوطرفه را می‌توان به لیست پیوندی حلقوی تبدیل کرد.

فیلم آموزش رایگان ساختمان داده ها – سریع و آسان در ۱۲۰ دقیقه در فرادرس

کلیک کنید

تبدیل لیست پیوندی یک طرفه به لیست حلقوی

در لیست پیوندی یک طرفه، اشاره‌گر next در عنصر آخر به گره اول لیست اشاره می‌کند:

تبدیل لیست پیوندی دو طرفه به لیست حلقوی

در لیست پیوندی دو طرفه اشاره‌گر next در عنصر آخر به گره اول لیست اشاره می‌کند و اشاره‌گر previous گره نخست نیز به عنصر آخر اشاره می‌کند تا از هر دو طرف لیست به صورت یک حلقه در آید.

همان طور که در تصویر فوق مشخص است این نوع لیست نقاط مهمی دارد که در ادامه آن‌ها را توضیح داده‌ایم:

• در هر دو نوع لیست‌های پیوندی یک و دو طرفه، اشاره‌گر next لینک آخر به لینک نخست لیست اشاره می‌کند.
• در لیست پیوندی دو طرفه اشاره‌گر previous عنصر نخست به گره آخر لیست اشاره می‌کند.

عملیات‌های ابتدایی

در ادامه عملیات‌های مهمی که در لیست‌های حلقوی وجود دارند را فهرست کرده‌ایم:

• درج (insert): یک عنصر در ابتدای لیست درج می‌کند.
• حذف (delete): یک عنصر از ابتدای لیست حذف می‌کند
• نمایش (display): لیست را نمایش می‌دهد.

عملیات درج

در ادامه کدی آمده است که عملیات درج در لیست حلقوی را بر مبنای یک لیست پیوندی منفرد نشان می‌دهد.

//insert link at the first location
void insertFirst(int key, int data) {
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data= data;
	
   if (isEmpty()) {
      head = link;
      head->next = head;
   } else {
      //point it to old first node
      link->next = head;
		
      //point first to new first node
      head = link;
   }   
}

عملیات حذف

کدی که در ادامه ارائه شده است عملیات حذف در یک لیست پیوندی حلقوی را بر مبنای لیست پیوندی منفرد نمایش می‌دهد:

//delete first item
struct node * deleteFirst() {
   //save reference to first link
   struct node *tempLink = head;
	
   if(head->next == head) {  
      head = NULL;
      return tempLink;
   }     

   //mark next to first link as first 
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

عملیات نمایش لیست

کد زیر عملیات نمایش لیست را در یک لیست پیوندی حلقوی نشان می‌دهد.

//display the list
void printList() {
   struct node *ptr = head;
   printf("\n[ ");
	
   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {     
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
	
   printf(" ]");
}

برنامه لیست پیوندی حلقوی در زبان C

در ادامه کدی ارائه شده است که پیاده‌سازی لیست پیوندی حلقوی در زبان C و عملیات‌های مربوط به آن را نشان می‌دهد.

پیاده‌سازی در C

#include 
#include 
#include 
#include 

struct node {
   int data;
   int key;
	
   struct node *next;
};

struct node *head = NULL;
struct node *current = NULL;

bool isEmpty() {
   return head == NULL;
}

int length() {
   int length = 0;

   //if list is empty
   if(head == NULL) {
      return 0;
   }

   current = head->next;

   while(current != head) {
      length++;
      current = current->next;   
   }
	
   return length;
}

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if (isEmpty()) {
      head = link;
      head->next = head;
   } else {
      //point it to old first node
      link->next = head;
		
      //point first to new first node
      head = link;
   }    
}

//delete first item
struct node * deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   if(head->next == head) {  
      head = NULL;
      return tempLink;
   }     

   //mark next to first link as first 
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

//display the list
void printList() {

   struct node *ptr = head;
   printf("\n[ ");
	
   //start from the beginning
   if(head != NULL) {
	
      while(ptr->next != ptr) {     
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
	
   printf(" ]");
}

void main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 

   printf("Original List: "); 
	
   //print list
   printList();

   while(!isEmpty()) {            
      struct node *temp = deleteFirst();
      printf("\nDeleted value:");  
      printf("(%d,%d) ",temp->key,temp->data);
   }   
	
   printf("\nList after deleting all items: ");
   printList();   
}

اگر برنامه فوق را کامپایل و اجرا کنیم، خروجی زیر را به دست می‌آوریم:

خروجی

Original List:

[(6,56) (5,40) (4,1) (3,30) (2,20)]

Deleted value: (6,56)

Deleted value: (5,40)

Deleted value: (4,1)

Deleted value: (3,30)

Deleted value: (2,20)

Deleted value: (1,10)

List after deleting all items:

[]

بدین ترتیب به پایان این راهنما در خصوص لیست‌های پیوندی می‌رسیم.

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم – از دروس دانشگاهی تا کاربردی در فرادرس

کلیک کنید

اگر تمایل دارید در مورد مطالب ساختمان داده و الگوریتم‌های مربوط به آن بیشتر مطالعه کنید، مطالب آینده ما را از دست ندهید. همچنین، جهت مطالعه بیشتر پیرامون ارتباط ساختمان داده و درس تحلیل و طراحی الگوریتم ها و درس الگوریتم های پیشرفته (درس نظریه الگوریتم پیشرفته)، مطالعه مطلب «درس الگوریتم های پیشرفته | مفاهیم پایه به زبان ساده» پیشنهاد می‌شود.

اگر این نوشته مورد توجه شما قرار گرفته است، پیشنهاد می‌کنیم موارد زیر را نیز ملاحظه کنید:

• ابزارهای مهندسی کامپیوتر
• آموزش ساختمان داده ها با C و ++C
• پایگاه داده و سیستم های مدیریت اطلاعات
• ساختمان داده (Data Structure) — راهنمای جامع و کاربردی
• گنجینه آزمون کارشناسی ارشد مهندسی کامپیوتر
• آموزش ساختمان داده ها

==