لیست پیوندی (Linked List)

لیست پیوندی (Linked List)مانند آرایه ها، لیست پیوندی یک ساختار داده خطی است. برخلاف آرایه ها، عناصر لیست پیوندی در یک مکان پیوسته ذخیره نمی شوند. عناصر با استفاده از اشاره گر به هم مرتبط می شوند.چرا لیست پیوندی؟ آرایه ها را می توان برای ذخیره داده های خطی از انواع مشابه استفاده کرد، اما آرایه ها دارای محدودیت های زیر هستند: 1) اندازه آرایه ها ثابت است: بنابراین باید حد بالایی تعداد عناصر را از قبل بدانیم. همچنین، به طور کلی، حافظه اختصاص داده شده برابر با حد بالایی صرف نظر از میزان مصرف است.2) درج یک عنصر جدید در آرایه ای از عناصر گران است زیرا اتاق باید برای عناصر جدید ایجاد شود و برای ایجاد اتاق عناصر موجود باید جابجا شوند اما در لیست پیوندی اگر گره سر را داشته باشیم، می توانیم به هر کدام پیمایش کنیم. از طریق آن گره بزنید و گره جدید را در موقعیت مورد نیاز قرار دهید.به عنوان مثال، در یک سیستم، اگر لیست مرتب شده ای از شناسه ها را در یک آرایه id[] نگهداری کنیم.id[] =[1000، 1010، 1050، 2000، 2040].و اگر بخواهیم یک ID جدید 1005 وارد کنیم، برای حفظ ترتیب مرتب شده، باید همه عناصر را بعد از 1000 (به استثنای 1000) جابجا کنیم.حذف نیز با آرایه ها گران است مگر اینکه از تکنیک های خاصی استفاده شود. به عنوان مثال، برای حذف 1010 در id[]، همه چیز بعد از 1010 باید جابجا شود، به این دلیل کار زیادی انجام می شود که بر کارایی کد تأثیر می گذارد.مزیت ها نسبت به آرایه ها1) اندازه پویا 2) سهولت در درجاشکالات(Drawbacks):.1) دسترسی تصادفی مجاز نیست. ما باید به ترتیب از اولین گره (گره سر) به عناصر دسترسی داشته باشیم. بنابراین نمی‌توانیم با اجرای پیش‌فرض آن، جستجوی باینری را با لیست‌های پیوندی به طور موثر انجام دهیم..2) فضای حافظه اضافی برای یک اشاره گر با هر عنصر لیست مورد نیاز است..3) کش پسند نیست. از آنجایی که عناصر آرایه مکان های پیوسته هستند، محل مرجعی وجود دارد که در مورد لیست های پیوندی وجود ندارد.نمایندگی(Representation):یک لیست پیوندی با اشاره گر به اولین گره لیست پیوندی نشان داده می شود. اولین گره سر نام دارد. اگر لیست پیوند شده خالی باشد، مقدار head به NULL اشاره می کند.هر گره در یک لیست حداقل از دو بخش تشکیل شده است:1) داده (ما می توانیم اعداد صحیح، رشته ها یا هر نوع داده ای را ذخیره کنیم).2) اشاره گر (یا مرجع) به گره بعدی (یک گره را به گره دیگر متصل می کند).در C، ما می توانیم یک گره را با استفاده از ساختارها نشان دهیم. در زیر نمونه ای از یک گره لیست پیوندی با داده های عدد صحیح آورده شده است.// A linked list node struct Node { int data; struct Node* next; };اولین لیست پیوندی ساده در Cاجازه دهید یک لیست پیوندی ساده با 3 گره ایجاد کنیم.// 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(&quot %d &quot, 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 HajiesmaeiliPhD of computer science from Kingston university of Londonhttps://ir.linkedin.com/in/dr-maryam-hajiesmaeili-90930743منابع:https://www.geeksforgeeks.org/linked-list-set-1-introduction/https://www.youtube.com/watch?v=R9PTBwOzceohttps://www.youtube.com/watch?v=TeIVI8xN0jwhttp://www.algorithmha.ir/%D8%B3%D8%A7%D8%AE%D8%AA%D9%85%D8%A7%D9%86-%D8%AF%D8%A7%D8%AF%D9%87/%D9%84%DB%8C%D8%B3%D8%AA-%D9%BE%DB%8C%D9%88%D9%86%D8%AF%DB%8C/https://blog.faradars.org/%D8%B3%D8%A7%D8%AE%D8%AA%D9%85%D8%A7%D9%86-%D8%AF%D8%A7%D8%AF%D9%87-data-structure-%D8%B1%D8%A7%D9%87%D9%86%D9%85%D8%A7%DB%8C-%D8%AC%D8%A7%D9%85%D8%B9-%D9%88-%DA%A9%D8%A7%D8%B1%D8%A8%D8%B1%D8%AF/