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

‏ لیست ‏‏پیوندی‏‏ یک ساختار داده خطی است، که در آن عناصر در مکان های حافظه به هم مرتبط ذخیره نمی شوند بلکه عناصر در یک لیست پیوندی با استفاده از اشاره گرها به هم ‏‏مرتبط می شوند‏‏. به عبارت ساده، یک لیست پیوندی شامل گره هایی است که هر گره شامل یک فیلد داده و یک مرجع(پیوند) به گره بعدی در لیست است. ‏

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

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

ساختار لیست پیوندی یک طرفه در زبان c:

class Node {

public:

int data

	Node* next;

};

ایجاد و تراورزال لیست پیوندی یک طرفه:

#include <bits/stdc++.h>                             

using namespace std;

class Node {

public:

	int data;

	Node* next;

};

void printList(Node* n)

{

           while (n != NULL) {

		cout << n->data << &quot &quot

		n = n->next;

	}

}

	Node* head = NULL;

	Node* second = NULL;

	Node* third = NULL;

	head = new Node();

	second = new Node();

	third = new Node();

	head->data = 1;

	head->next = second;

	second->data = 2;

	second->next = third;

	third->data = 3;

	third->next = NULL;

	printList(head);

	return 0;

}

‏لیست ‏‏پیوندی دو طرفه:‏‏ لیست پیوندی دو طرفه، نوع پیچیده تری از لیست پیوندی است که شامل اشاره گر به گره بعدی و همچنین گره قبلی در دنباله است، بنابراین شامل سه بخش داده، اشاره گر به گره بعدی، و اشاره گر به گره قبلی است. این ما را قادر به عبور از لیست در جهت عقب نیز می سازد. همانطور که در تصویر زیر مشاهده می کنید:

‏

ساختار لیست پیوندی دوطرفه در زبان c:

struct Node {

	int data;

	struct Node* next;

	struct Node* prev;

};

ایجاد و تراورزال لیست پیوندی دو طرفه در زبان c:

#include <bits/stdc++.h>

using namespace std;

class Node {

public:

	int data;

	Node* next;

	Node* prev;

};

void push(Node** head_ref, int new_data)

{

	Node* new_node = new Node();

	new_node->data = new_data;

	new_node->next = (*head_ref);

	new_node->prev = NULL;

	if ((*head_ref) != NULL)

		(*head_ref)->prev = new_node;

	(*head_ref) = new_node;

}

void printList(Node* node)

{

	Node* last;

	cout << &quot\nTraversal in forward&quot

		<< &quot direction \n&quot

	while (node != NULL) {

		cout << &quot &quot << node->data << &quot &quot

		last = node;

		node = node->next;

	}

	cout << &quot\nTraversal in reverse&quot

		<< &quot direction \n&quot

	while (last != NULL) {

		cout << &quot &quot << last->data << &quot &quot

		last = last->prev;

	}

}

int main()

{

	Node* head = NULL;

	push(&head, 6);

	push(&head, 7);

	push(&head, 1);

	cout << &quotCreated DLL is: &quot

	printList(head);

return 0;

}

‏‏لیست پیوندی حلقوی(دایره ایی):‏‏ در لیست پیوندی حلقوی، گره آخر شامل اشاره گر به گره اول لیست است، در حالی که در تراورزال یک لیست پیوندی ، ما می توانیم در هر گره ای آغاز و با عبور از لیست در هر جهتی، رو به جلو و یا رو به عقب و تا زمانی که رسیدن به همان گره شروع شده باشد. بدین ترتیب یک لیست پیوندی حلقوی هیچ آغاز و پایانی ندارد. همانطور که در تصویر زیر مشاهده می کنید:

ساختار لیست پیوندی حلقوی در زبان C:

class Node {

public:

	int data;

	Node* next;

};

ایجاد و تراورزال لیست پیوندی حلقوی در زبان c:

#include <bits/stdc++.h>

using namespace std;

class Node {

public:

	int data;

	Node* next;

};

void push(Node** head_ref, int data)

{

	Node* ptr1 = new Node();

	Node* temp = *head_ref;

	ptr1->data = data;

	ptr1->next = *head_ref;

	if (*head_ref != NULL) {

		while (temp->next != *head_ref) {

			temp = temp->next;

		}

		temp->next = ptr1;

	}

	else

		ptr1->next = ptr1;

         *head_ref = ptr1;

}

void printList(Node* head)

{

	Node* temp = head;

	if (head != NULL) {

		do {

			cout << temp->data << &quot &quot

			temp = temp->next;

		} while (temp != head);

	}

}

// Driver Code

int main()

{

	Node* head = NULL;

	push(&head, 12);

	push(&head, 56);

	push(&head, 2);

	push(&head, 11);

       cout << &quotContents of Circular&quot

	<< &quot Linked List\n &quot

	printList(head);

return 0;

}

گرداورندگان:

• علی قاسمی
• حسین قربانی
• سروش زندی
• مهدی نظری
• ابوالفضل ولی الهی
• یاشار مرتاض

با تشکر از استاد دکتر مریم حاجی اسمعیلی دکترای علوم کامپیوتر از دانشگاه کینگستون لندن

Dr. Maryam Hajiesmaeili phD of computer science from Kingstone university of London

منابع: https://www.tutorialspoint.com/data_structures_algorithms/linked_list_program_in_c.htm