به عنوان مثال، در یک سیستم، اگر لیست مرتب شده ای از شناسه ها را در یک آرایه id[] نگهداری کنیم.
id[] =[1000، 1010، 1050، 2000، 2040].
و اگر بخواهیم یک ID جدید 1005 وارد کنیم، برای حفظ ترتیب مرتب شده، باید همه عناصر را بعد از 1000 (به استثنای 1000) جابجا کنیم.
حذف نیز با آرایه ها گران است مگر اینکه از تکنیک های خاصی استفاده شود. به عنوان مثال، برای حذف 1010 در id[]، همه چیز بعد از 1010 باید جابجا شود، به این دلیل کار زیادی انجام می شود که بر کارایی کد تأثیر می گذارد.
.1) دسترسی تصادفی مجاز نیست. ما باید به ترتیب از اولین گره (گره سر) به عناصر دسترسی داشته باشیم. بنابراین نمی‌توانیم با اجرای پیش‌فرض آن، جستجوی باینری را با لیست‌های پیوندی به طور موثر انجام دهیم.
.2) فضای حافظه اضافی برای یک اشاره گر با هر عنصر لیست مورد نیاز است.
.3) کش پسند نیست. از آنجایی که عناصر آرایه مکان های پیوسته هستند، محل مرجعی وجود دارد که در مورد لیست های پیوندی وجود ندارد.
یک لیست پیوندی با اشاره گر به اولین گره لیست پیوندی نشان داده می شود. اولین گره سر نام دارد. اگر لیست پیوند شده خالی باشد، مقدار head به NULL اشاره می کند.
هر گره در یک لیست حداقل از دو بخش تشکیل شده است:
در C، ما می توانیم یک گره را با استفاده از ساختارها نشان دهیم. در زیر نمونه ای از یک گره لیست پیوندی با داده های عدد صحیح آورده شده است.
// A linked list node struct Node { int data; struct Node* next; };
// A simple C program to introduce // a linked list #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; // Program to create a simple linked // list with 3 nodes int main() { struct Node* head = NULL; struct Node* second = NULL; struct Node* third = NULL; // allocate 3 nodes in the heap head = (struct Node*)malloc(sizeof(struct Node)); second = (struct Node*)malloc(sizeof(struct Node)); third = (struct Node*)malloc(sizeof(struct Node)); /* Three blocks have been allocated dynamically. We have pointers to these three blocks as head, second and third head second third | | | | | | +---+-----+ +----+----+ +----+----+ | # | # | | # | # | | # | # | +---+-----+ +----+----+ +----+----+ # represents any random value. Data is random because we haven’t assigned anything yet */ head->data = 1; // assign data in first node head->next = second; // Link first node with // the second node /* data has been assigned to the data part of the first block (block pointed by the head). And next pointer of first block points to second. So they both are linked. head second third | | | | | | +---+---+ +----+----+ +-----+----+ | 1 | o----->| # | # | | # | # | +---+---+ +----+----+ +-----+----+ */ // assign data to second node second->data = 2; // Link second node with the third node second->next = third; /* data has been assigned to the data part of the second block (block pointed by second). And next pointer of the second block points to the third block. So all three blocks are linked. head second third | | | | | | +---+---+ +---+---+ +----+----+ | 1 | o----->| 2 | o-----> | # | # | +---+---+ +---+---+ +----+----+ */ third->data = 3; // assign data to third node third->next = NULL; /* data has been assigned to data part of third block (block pointed by third). And next pointer of the third block is made NULL to indicate that the linked list is terminated here. We have the linked list ready. head | | +---+---+ +---+---+ +----+------+ | 1 | o----->| 2 | o-----> | 3 | NULL | +---+---+ +---+---+ +----+------+ Note that only head is sufficient to represent the whole list. We can traverse the complete list by following next pointers. */ return 0; }
در برنامه قبلی یک لیست پیوندی ساده با سه گره ایجاد کرده ایم. اجازه دهید لیست ایجاد شده را طی کنیم و داده های هر گره را چاپ کنیم. برای پیمایش، اجازه دهید یک تابع همه منظوره printList() بنویسیم که هر لیست داده شده را چاپ می کند.
// A simple C program for traversal of a linked list #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; // This function prints contents of linked list starting from // the given node void printList(struct Node* n) { while (n != NULL) { printf(" %d ", n->data); n = n->next; } } int main() { struct Node* head = NULL; struct Node* second = NULL; struct Node* third = NULL; // allocate 3 nodes in the heap head = (struct Node*)malloc(sizeof(struct Node)); second = (struct Node*)malloc(sizeof(struct Node)); third = (struct Node*)malloc(sizeof(struct Node)); head->data = 1; // assign data in first node head->next = second; // Link first node with second second->data = 2; // assign data to second node second->next = third; third->data = 3; // assign data to third node third->next = NULL; printList(head); return 0; }
گردآورندگان:
با تشکر از استاد دکتر مریم حاجی اسمعیلی. دکترای علوم کامپیوتر از دانشگاه کینگستون لندن.
Dr. Maryam Hajiesmaeili
PhD of computer science from Kingston university of London
https://ir.linkedin.com/in/dr-maryam-hajiesmaeili-90930743
https://www.geeksforgeeks.org/linked-list-set-1-introduction/
https://www.youtube.com/watch?v=R9PTBwOzceo
https://www.youtube.com/watch?v=TeIVI8xN0jw
