لیست پیوندی رایج ترین ساختار داده مورد استفاده و پایه دیگر ساختارهای داده پیچیده است. لیست پیوندی برای ذخیره داده ها در زمان اجرا یا به صورت پویا در حین اجرای برنامه استفاده می شود.
همه ما می دانیم که لیست پیوندی چیست، مجموعه ای از گره ها است که حاوی یک داده و اشاره گر است که به گره های دیگر اشاره می کند. یک لیست پیوندی با استفاده از یک اشاره گر یا شی که به سر یا اولین گره لیست پیوندی اشاره می کند قابل دسترسی است.
انواع مختلفی از لیستهای پیوندی مانند لیستهای پیوندی منفرد، فهرستهای پیوندی دوگانه، فهرستهای پیوندی چندگانه، فهرستهای پیوندی دایرهای، فهرستهای پیوندی عمومی و غیره وجود دارد. ما یک لیست پیوندی را در زبانهای ساختارگرا مانند C و همچنین در زبانهای شیگرا مانند C++,C#,Java,Python,VB.Net.
ما همچنین از لیست پیوندی برای پیاده سازی یک سیستم اطلاعات دانش آموز ساده برای ذخیره داده ها در سی شارپ استفاده خواهیم کرد.
![](http://pezhvak24.ir/dl/10kcor/cscd/article/understanding-data-structures-linked-lists/Images/student_information_system.png)
بیایید برخی از کاربردهای لیست های پیوندی را ببینیم.
- سیستم های فایل
- مدیر حافظه
- خواندن/نوشتن داده ها از/به دستگاه های جانبی مانند صفحه نمایش کامپیوتر، چاپگر، درایو فلش USB و غیره.
- عملیات رابط کاربری مانند بعدی یا قبلی در برنامه هایی مانند پخش کننده ویدیو/موسیقی، مرورگر و غیره.
- ارسال/دریافت داده های بسته از طریق شبکه و یا در سیستم مخابراتی.
- نرم افزار کاربردی سازمانی (EAS)
- برای پیاده سازی Stack، Queue، Hash Tables و غیره، Stack برای Undo و Queue برای Redo عملیات و غیره.
- کامپایلرها و مفسران
لیستهای پیوندی دارای اشکالاتی هستند، مانند دسترسی تصادفی، جستجو، حافظه اضافی و غیره
. برای تأیید لیست پیوندی، مکان حافظه هر گره و همچنین گره بعدی/قبلی را چاپ خواهیم کرد. شماره thisNode را ببینید و اعتبار سنجی کنید که لیست پیوندی درست است یا خیر.
لیست های پیوندی منفرد
یک لیست پیوندی منفرد شامل یک بخش داده و یک اشاره گر به گره بعدی است. بخش داده ممکن است حاوی هر نوع داده یا اشاره گر یا اشیاء کلاس باشد. بخش بعدی شامل آدرس گره بعدی یا مرجع شی گره بعدی است.
تصویر زیر را ببینید.
![](http://pezhvak24.ir/dl/10kcor/cscd/article/understanding-data-structures-linked-lists/Images/singly_linked_list_basic.png)
این تصویر فهرست پیوندی را نشان میدهد، اما نحوه اجرای آن را نشان نمیدهد. این فقط تصویر اصلی در اینترنت برای لیست پیوند شده است. بسیاری از لیست پیوندهای منفرد را توصیف نمی کند. برای درک آن تصویر اصلاح شده زیر را ببینید.
![](http://pezhvak24.ir/dl/10kcor/cscd/article/understanding-data-structures-linked-lists/Images/singly_linked_list.png)
هر گره رکوردی است که برخی از داده ها را ذخیره می کند. رکورد می تواند هر نوع باشد مانند ساختارهای C یا کلاس در زبان های شی گرا. یک داده را می توان به هر گره اشاره گر یا شی اختصاص داد.
پیاده سازی ساده زیر از لیست پیوندی منفرد را در ساختار گرا و شی گرا مشاهده کنید.
در C و C++ شما باید یک حافظه را تخصیص دهید و همچنین پس از اتمام کار، آن را آزاد کنید. سایر زبان های شی گرا از جمع آوری زباله پشتیبانی می کنند، بنابراین نیازی به نگرانی در مورد انتشار حافظه نیست.
ابتدا باید یک پروژه خالی در ویژوال استودیو به صورت Visual C++ ایجاد کنید و سپس آیتم جدیدی به آن اضافه کنید. ابتدا اجازه دهید ساختاری را برای ذخیره داده های خود یا ساخت یک نوع داده انتزاعی تعریف کنیم.
- typedef struct node {
- int data;
- struct node *next;
- }Node;
همانطور که در تصویر نشان داده شده است، می توانید مستقیماً یک متغیر اشاره گر همان نوع را به متغیر اشاره گر دیگری اختصاص دهید. در C باید با استفاده از تابع malloc() حافظه را تخصیص دهید. می توانید مستقیماً حافظه را تخصیص دهید و یک داده به آن اختصاص دهید یا می توانید یک تابع برای آن بنویسید.
تابع زیر داده ها را به newnode و اشاره گر بعدی را به NULL پس از تخصیص حافظه به آن اختصاص می دهد و مکان حافظه اختصاص داده شده را برمی گرداند. می توانید با استفاده از مشخص کننده فرمت %p یک مکان حافظه را در C چاپ کنید.
کد منبع را دانلود کنید.
- Node *getNewNode(int data)
- {
- Node *newnode = (Node*)malloc(sizeof(Node));
- if (newnode != NULL){
- newnode->data = data;
- newnode->next = NULL;
- }
- return newnode;
- }
در تابع اصلی، همانطور که در تصویر بالا نشان داده شده است، نشانگر بعدی را با تخصیص گره های اشاره گر دیگر به آن اختصاص دهید یا شکل دهید. ابتدا یک هد بسازید و آن را روی NULL قرار دهید. میتوانید با فراخوانی ()getNewNode، گره حافظه اختصاص داده شده را مستقیماً به head اختصاص دهید. سپس سه گره ایجاد کنید، node_1 را به head اختصاص دهید و با اختصاص گره های اشاره گر به یکدیگر، یک لیست پیوندی تشکیل دهید.
شما همچنین می توانید یک تابع برای آن بنویسید که می تواند گره را به لیست اضافه کند. سپس دادههای هر گره را چاپ میکنیم، میتوانید همانطور که معمولاً انجام میدهیم، آن را در حلقه while قرار دهید. به یاد داشته باشید که ما در اینجا فقط تخصیص اشاره گر را انجام می دهیم و هیچ چیز دیگری برای تشکیل یک لیست پیوندی انجام نمی دهیم.
- int main()
- {
- Node *head = NULL;
- Node *node_1 = getNewNode(10);
- Node *node_2 = getNewNode(20);
- Node *node_3 = getNewNode(30);
- head = node_1;
- node_1->next = node_2;
- node_2->next = node_3;
- node_3->next = NULL;
- printf("node_1 = %d, node_2 = %d, node_3 = %d\n", head->data, head->next->data, head->next->next->data);
- getchar();
- return 0;
- }
در شی گرا، رویه مانند ساختار گرا است، تنها تفاوت در بازی با اشیا است. ابتدا کلاس یک گره را تعریف کنید و سپس روال یکسان است. در شی گرا، به تابعی مانند getNewNode() نیاز ندارید، می توانید مستقیماً حافظه را با استفاده از کلمه کلیدی جدید اختصاص دهید .
- class Node {
- int data;
- Node next;
- public Node(int data){
- this.data = data;
- this.next = null;
- }
- }
- class Program{
- static void Main(string[] args){
- Node head = null;
- Node node_1 = new Node(10);
- Node node_2 = new Node(20);
- Node node_3 = new Node(30);
- head = node_1;
- node_1.next = node_2;
- node_2.next = node_3;
- node_3.next = null;
- Console.WriteLine("node_1 = %d, node_2 = %d, node_3 = %d\n", head.data, head.next.data, head.next.next.data);
- Console.Read();
- }
- }
دوگانه یک لیست دارای پیوند دوگانه شامل یک بخش داده، یک اشاره گر به گره بعدی و یک اشاره گر به گره قبلی است. بخش داده ممکن است حاوی هر نوع داده یا اشاره گر یا اشیاء کلاس باشد. بخش بعدی شامل آدرس گره بعدی یا مرجع شی گره بعدی است. بخش Prev شامل آدرس گره قبلی یا مرجع شی گره قبلی است.
تصویر زیر را ببینید.
![](http://pezhvak24.ir/dl/10kcor/cscd/article/understanding-data-structures-linked-lists/Images/doubly_linked_list_basic.png)
بسیاری از لیست پیوندهای مضاعف را توصیف نمی کند. برای درک آن تصویر اصلاح شده زیر را ببینید.
![](http://pezhvak24.ir/dl/10kcor/cscd/article/understanding-data-structures-linked-lists/Images/doubly_linked_list.png)
فقط یک فیلد را مانند قبل به لیست پیوندهای منفرد اضافه کنید. و مکان اشاره گر یا شیء نشانگرها یا اشیاء قبلی را مطابق تصویر بالا تغییر دهید.
- typedef struct node {
- int data;
- struct node *next;
- struct node *prev;
- }Node;
- class Node {
- int data;
- Node next;
- Node prev;
- }
بسیاری از عملیات را می توان در لیست پیوندی با توجه به موارد استفاده از آن همانطور که در بالا توضیح داده شد اعمال کرد. ما فقط چند عملیات مانند افزودن گره به انتها یا جلو و حذف گره جلو یا آخرین گره در لیست پیوندی را خواهیم دید. ما هم لیست لینک شده و هم لیست پیوند مضاعف را اجرا خواهیم کرد. بیایید پیاده سازی لیست پیوندی را در زبان های برنامه نویسی مختلف ببینیم.
برای مشاهده کد کامل، کد منبع C را دانلود کنید.
- typedef struct sll_node
- {
- int data;
- struct sll_node *next;
- }SLL_Node;
- typedef struct dll_node
- {
- int data;
- struct dll_node *next;
- struct dll_node *prev;
- }DLL_Node;
- SLL_Node *sll_getNewNode(int data)
- {
- SLL_Node *newnode = NULL;
- newnode = (SLL_Node*)malloc(sizeof(SLL_Node));
- if (newnode != NULL){
- newnode->data = data;
- newnode->next = NULL;
- }
- return newnode;
- }
- DLL_Node *dll_getNewNode(int data)
- {
- DLL_Node *newnode = NULL;
- newnode = (DLL_Node*)malloc(sizeof(DLL_Node));
- if (newnode != NULL){
- newnode->data = data;
- newnode->next = NULL;
- newnode->prev = NULL;
- }
- return newnode;
- }
- typedef struct singly_linked_list{
- SLL_Node *head;
- SLL_Node*(*getNewNode)(int);
- void(*addNodeToEnd)(SLL_Node**, int);
- void(*addNodeToFront)(SLL_Node**, int);
- void(*deleteLastNode)(SLL_Node**);
- void(*deleteFrontNode)(SLL_Node**);
- void(*display)(SLL_Node*);
- }SinglyLinkedList;
- typedef struct doubly_linked_list{
- DLL_Node *head;
- DLL_Node*(*getNewNode)(int);
- void(*addNodeToEnd)(DLL_Node**, int);
- void(*addNodeToFront)(DLL_Node**, int);
- void(*deleteLastNode)(DLL_Node**);
- void(*deleteFrontNode)(DLL_Node**);
- void(*display)(DLL_Node*);
- }DoublyLinkedList;
- SinglyLinkedList *initSinglyLinkedList()
- {
- SinglyLinkedList *s_list = (SinglyLinkedList*)malloc(sizeof(SinglyLinkedList));
- s_list->head = NULL;
- s_list->getNewNode = sll_getNewNode;
- s_list->addNodeToEnd = sll_addNodeToEnd;
- s_list->addNodeToFront = sll_addNodeToFront;
- s_list->deleteLastNode = sll_deleteLastNode;
- s_list->deleteFrontNode = sll_deleteFrontNode;
- s_list->display = sll_display;
- return s_list;
- }
- DoublyLinkedList *initDoublyLinkedList()
- {
- DoublyLinkedList *d_list = (DoublyLinkedList*)malloc(sizeof(DoublyLinkedList));
- d_list->head = NULL;
- d_list->getNewNode = dll_getNewNode;
- d_list->addNodeToEnd = dll_addNodeToEnd;
- d_list->addNodeToFront = dll_addNodeToFront;
- d_list->deleteLastNode = dll_deleteLastNode;
- d_list->deleteFrontNode = dll_deleteFrontNode;
- d_list->display = dll_display;
- return d_list;
- }
کلاسی در C وجود ندارد، اما میتوانیم کلاس را در C با استفاده از اشارهگر به توابع و قرار دادن آن در یک ساختار پیادهسازی کنیم. ساختار singly_linked_list تمام متدهای اشاره گر به تابع را تعریف می کند. initSinglyLinkedList() و initDoublyLinkedList() با تخصیص توابع اشاره گر را برای عملکرد مقداردهی اولیه می کنند. و سپس می توانیم از متغیر ساختار SinglyLinkedList یا DoublyLinkedList به همه توابع دسترسی داشته باشیم.