لیست پیوندی یک طرفه، دو طرفه و حلقوی – ساختمان داده و الگوریتم ها
لیست پیوندی یک توالی از ساختارهای دادهای است که از طریق پیوندهایی به هم مربوط شدهاند. لیست پیوندی در واقع یک توالی از لیستها هستند که شامل آیتمهایی میشوند. هر پیوند شامل اتصال به پیوندهای دیگر است. لیست پیوندی پس از آرایهها دومین ساختمان داده پر کاربرد محسوب میشود. در ادامه برخی اصلاحهای مهم برای درک مفهوم لیست پیوندی ارائه شده است:
- پیوند (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) — راهنمای جامع و کاربردی
- گنجینه آزمون کارشناسی ارشد مهندسی کامپیوتر
- آموزش ساختمان داده ها
==
عالیییییییییییییییییییییییییییییییییییییییییییییییییییییییی بوووووووووووووووووووووووووووووووود
عالی و واضح بود ممنون
عاليييييييييييييييييييييييييييييييييييييييييييييييييييييييي بوووووووووووووووووووووووووووووووود