Divkārši saistīts saraksts ir sarežģīts saistīto sarakstu veids, kurā mezglā ir rādītājs uz iepriekšējo, kā arī uz nākamo secības mezglu. Tāpēc divkārši saistītā sarakstā mezgls sastāv no trim daļām: mezgla dati, rādītājs uz nākamo mezglu pēc kārtas (nākamais rādītājs) , rādītājs uz iepriekšējo mezglu (iepriekšējais rādītājs). Mezgla paraugs dubultsaitā sarakstā ir parādīts attēlā.
Nākamajā attēlā ir parādīts divkārši saistīts saraksts, kurā ir trīs mezgli ar cipariem no 1 līdz 3 to datu daļā.
C versijā mezgla struktūru divreiz saistītā sarakstā var norādīt kā:
struct node { struct node *prev; int data; struct node *next; }
The iepriekj daļa no pirmā mezgla un Nākamais daļa no pēdējā mezgla vienmēr satur nulli, kas norāda galu katrā virzienā.
Atsevišķi saistītā sarakstā mēs varētu pārvietoties tikai vienā virzienā, jo katrs mezgls satur nākamā mezgla adresi un tajā nav ierakstu par iepriekšējiem mezgliem. Tomēr divkārši saistītie saraksti pārvar šo atsevišķi saistītā saraksta ierobežojumu. Sakarā ar to, ka katrs saraksta mezgls satur sava iepriekšējā mezgla adresi, mēs varam atrast visu informāciju par iepriekšējo mezglu, kā arī izmantojot iepriekšējo adresi, kas saglabāta katra mezgla iepriekšējā daļā.
Atmiņa Divkārši saistīta saraksta attēlojums
Atmiņa Divkārši saistīta saraksta attēlojums ir parādīts nākamajā attēlā. Parasti dubultsavienots saraksts patērē vairāk vietas katram mezglam un tādējādi rada plašākas pamatdarbības, piemēram, ievietošanu un dzēšanu. Tomēr mēs varam viegli manipulēt ar saraksta elementiem, jo saraksts saglabā norādes abos virzienos (uz priekšu un atpakaļ).
Nākamajā attēlā pirmais saraksta elements, kas, t.i., 13, ir saglabāts adresē 1. Galvenā rādītāja norāda uz sākuma adresi 1. Tā kā šis ir pirmais elements, kas tiek pievienots sarakstam, tāpēc iepriekj no saraksta satur null. Nākamais saraksta mezgls atrodas adresē 4, tāpēc pirmā mezgla nākamajā rādītājā ir 4.
Mēs varam šķērsot sarakstu šādā veidā, līdz mēs atrodam jebkuru mezglu, kas satur nulli vai -1 tā nākamajā daļā.
Darbības divkāršā sarakstā
Mezglu izveide
struct node { struct node *prev; int data; struct node *next; }; struct node *head;
Visas pārējās darbības, kas saistītas ar divkārši saistīto sarakstu, ir aprakstītas nākamajā tabulā.
SN | Darbība | Apraksts |
---|---|---|
1 | Ievietošana sākumā | Mezgla pievienošana saistītajam sarakstam sākumā. |
2 | Ievietošana beigās | Mezgla pievienošana saistītajam sarakstam līdz beigām. |
3 | Ievietošana pēc norādītā mezgla | Mezgla pievienošana saistītajam sarakstam pēc norādītā mezgla. |
4 | Dzēšana sākumā | Noņemt mezglu no saraksta sākuma |
5 | Dzēšana beigās | Mezgla noņemšana no saraksta beigām. |
6 | Tā mezgla dzēšana, kurš sniedzis datus | Noņemt mezglu, kas atrodas tieši aiz mezgla, kurā ir dotie dati. |
7 | Meklēšana | Salīdzinot katra mezgla datus ar meklējamo vienumu un atgriežot vienuma atrašanās vietu sarakstā, ja citādi atrastais vienums atgriež nulli. |
8 | Šķērsošana | Apmeklējiet katru saraksta mezglu vismaz vienu reizi, lai veiktu kādu konkrētu darbību, piemēram, meklēšanu, kārtošanu, attēlošanu utt. |
Izvēlnes vadīta programma C, lai īstenotu visas divkārši saistītā saraksta darbības
#include #include struct node { struct node *prev; struct node *next; int data; }; struct node *head; void insertion_beginning(); void insertion_last(); void insertion_specified(); void deletion_beginning(); void deletion_last(); void deletion_specified(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf(' *********Main Menu********* '); printf(' Choose one option from the following list ... '); printf(' =============================================== '); printf(' 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit '); printf(' Enter your choice? '); scanf(' %d',&choice); switch(choice) { case 1: insertion_beginning(); break; case 2: insertion_last(); break; case 3: insertion_specified(); break; case 4: deletion_beginning(); break; case 5: deletion_last(); break; case 6: deletion_specified(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void insertion_beginning() { struct node *ptr; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf(' OVERFLOW'); } else { printf(' Enter Item value'); scanf('%d',&item); if(head==NULL) { ptr->next = NULL; ptr->prev=NULL; ptr->data=item; head=ptr; } else { ptr->data=item; ptr->prev=NULL; ptr->next = head; head->prev=ptr; head=ptr; } printf(' Node inserted '); } } void insertion_last() { struct node *ptr,*temp; int item; ptr = (struct node *) malloc(sizeof(struct node)); if(ptr == NULL) { printf(' OVERFLOW'); } else { printf(' Enter value'); scanf('%d',&item); ptr->data=item; if(head == NULL) { ptr->next = NULL; ptr->prev = NULL; head = ptr; } else { temp = head; while(temp->next!=NULL) { temp = temp->next; } temp->next = ptr; ptr ->prev=temp; ptr->next = NULL; } } printf(' node inserted '); } void insertion_specified() { struct node *ptr,*temp; int item,loc,i; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf(' OVERFLOW'); } else { temp=head; printf('Enter the location'); scanf('%d',&loc); for(i=0;inext; if(temp == NULL) { printf(' There are less than %d elements', loc); return; } } printf('Enter value'); scanf('%d',&item); ptr->data = item; ptr->next = temp->next; ptr -> prev = temp; temp->next = ptr; temp->next->prev=ptr; printf(' node inserted '); } } void deletion_beginning() { struct node *ptr; if(head == NULL) { printf(' UNDERFLOW'); } else if(head->next == NULL) { head = NULL; free(head); printf(' node deleted '); } else { ptr = head; head = head -> next; head -> prev = NULL; free(ptr); printf(' node deleted '); } } void deletion_last() { struct node *ptr; if(head == NULL) { printf(' UNDERFLOW'); } else if(head->next == NULL) { head = NULL; free(head); printf(' node deleted '); } else { ptr = head; if(ptr->next != NULL) { ptr = ptr -> next; } ptr -> prev -> next = NULL; free(ptr); printf(' node deleted '); } } void deletion_specified() { struct node *ptr, *temp; int val; printf(' Enter the data after which the node is to be deleted : '); scanf('%d', &val); ptr = head; while(ptr -> data != val) ptr = ptr -> next; if(ptr -> next == NULL) { printf(' Can't delete '); } else if(ptr -> next -> next == NULL) { ptr ->next = NULL; } else { temp = ptr -> next; ptr -> next = temp -> next; temp -> next -> prev = ptr; free(temp); printf(' node deleted '); } } void display() { struct node *ptr; printf(' printing values... '); ptr = head; while(ptr != NULL) { printf('%d ',ptr->data); ptr=ptr->next; } } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf(' Empty List '); } else { printf(' Enter item which you want to search? '); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf(' item found at location %d ',i+1); flag=0; break; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf(' Item not found '); } } }
Izvade
*********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 1 Enter Item value12 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 1 Enter Item value123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 1 Enter Item value1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 1234 123 12 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 2 Enter value89 node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 3 Enter the location1 Enter value12345 node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 1234 123 12345 12 89 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 4 node deleted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 5 node deleted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 123 12345 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 6 Enter the data after which the node is to be deleted : 123 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 123 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 123 item found at location 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 6 Enter the data after which the node is to be deleted : 123 Can't delete *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 9 Exited..