Lista podwójnie połączona to złożony typ listy połączonej, w której węzeł zawiera wskaźnik do poprzedniego i następnego węzła w sekwencji. Dlatego na podwójnie połączonej liście węzeł składa się z trzech części: danych węzła, wskaźnika do następnego węzła w sekwencji (następny wskaźnik), wskaźnika do poprzedniego węzła (poprzedni wskaźnik). Przykładowy węzeł na podwójnie połączonej liście pokazano na rysunku.
Podwójnie połączona lista zawierająca trzy węzły posiadające w części danych numery od 1 do 3 jest pokazana na poniższym obrazku.
W C strukturę węzła na liście podwójnie połączonej można przedstawić jako:
struct node { struct node *prev; int data; struct node *next; } The poprzednie część pierwszego węzła i Następny część ostatniego węzła będzie zawsze zawierać wartość null wskazującą koniec w każdym kierunku.
Na liście pojedynczo połączonej moglibyśmy poruszać się tylko w jednym kierunku, ponieważ każdy węzeł zawiera adres następnego węzła i nie ma żadnego zapisu o swoich poprzednich węzłach. Jednak podwójnie połączona lista przezwycięża to ograniczenie pojedynczo połączonej listy. Ponieważ każdy węzeł listy zawiera adres swojego poprzedniego węzła, wszystkie szczegóły dotyczące poprzedniego węzła możemy znaleźć również korzystając z poprzedniego adresu zapisanego w poprzedniej części każdego węzła.
Pamięć Reprezentacja listy podwójnie połączonej
Reprezentacja pamięci podwójnie połączonej listy jest pokazana na poniższym obrazku. Ogólnie rzecz biorąc, podwójnie połączona lista zajmuje więcej miejsca dla każdego węzła i dlatego powoduje bardziej rozbudowane podstawowe operacje, takie jak wstawianie i usuwanie. Możemy jednak łatwo manipulować elementami listy, ponieważ lista utrzymuje wskaźniki w obu kierunkach (do przodu i do tyłu).
Na poniższym obrazku pierwszy element listy, czyli 13, jest przechowywany pod adresem 1. Wskaźnik nagłówka wskazuje adres początkowy 1. Ponieważ jest to pierwszy element dodawany do listy, dlatego poprzednie z listy zawiera zero. Następny węzeł listy znajduje się pod adresem 4, zatem pierwszy węzeł zawiera 4 w swoim następnym wskaźniku.
Możemy w ten sposób przemierzać listę, aż znajdziemy w jej następnej części dowolny węzeł zawierający null lub -1.
Operacje na liście podwójnie połączonej
Tworzenie węzła
struct node { struct node *prev; int data; struct node *next; }; struct node *head; Wszystkie pozostałe operacje dotyczące listy podwójnie połączonej opisano w poniższej tabeli.
| SN | Operacja | Opis |
|---|---|---|
| 1 | Wstawienie na początku | Dodanie węzła do połączonej listy na początku. |
| 2 | Wstawienie na końcu | Dodanie węzła do połączonej listy na koniec. |
| 3 | Wstawienie po określonym węźle | Dodanie węzła do połączonej listy po określonym węźle. |
| 4 | Usuwanie na początku | Usunięcie węzła z początku listy |
| 5 | Na koniec usunięcie | Usunięcie węzła z końca listy. |
| 6 | Usunięcie węzła posiadającego podane dane | Usunięcie węzła występującego tuż za węzłem zawierającym podane dane. |
| 7 | Badawczy | Porównywanie danych każdego węzła z elementem, który ma zostać przeszukany, i zwrócenie lokalizacji elementu na liście, jeśli znaleziony element zwróci wartość null. |
| 8 | Przemierzanie | Odwiedzenie każdego węzła listy przynajmniej raz w celu wykonania określonej operacji, takiej jak wyszukiwanie, sortowanie, wyświetlanie itp. |
Program sterowany menu w C do implementowania wszystkich operacji na liście podwójnie połączonej
#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
'); } } } Wyjście
*********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..