TechCodeview

• Listę połączoną można zdefiniować jako zbiór obiektów tzw węzły które są losowo zapisywane w pamięci.
• Węzeł zawiera dwa pola, czyli dane przechowywane pod tym konkretnym adresem oraz wskaźnik zawierający adres kolejnego węzła w pamięci.
• Ostatni węzeł listy zawiera wskaźnik do wartości null.

Zastosowania listy połączonej

• Lista nie musi być stale obecna w pamięci. Węzeł może znajdować się w dowolnym miejscu pamięci i być połączony ze sobą w celu utworzenia listy. Zapewnia to optymalne wykorzystanie przestrzeni.
• Rozmiar listy jest ograniczony rozmiarem pamięci i nie trzeba go wcześniej deklarować.
• Na połączonej liście nie może znajdować się pusty węzeł.
• Możemy przechowywać wartości typów pierwotnych lub obiektów na pojedynczo połączonej liście.

Po co używać listy połączonej zamiast tablicy?

Do tej pory do organizowania grupy elementów, które miały być pojedynczo przechowywane w pamięci, używaliśmy tablicowej struktury danych. Jednakże Array ma kilka zalet i wad, które należy poznać, aby określić strukturę danych, która będzie używana w całym programie.

Tablica zawiera następujące ograniczenia:

1. Rozmiar tablicy musi być znany z góry przed użyciem jej w programie.
2. Zwiększanie rozmiaru tablicy jest procesem czasochłonnym. Zwiększenie rozmiaru tablicy w czasie wykonywania jest prawie niemożliwe.
3. Wszystkie elementy tablicy muszą być przechowywane w pamięci w sposób ciągły. Wstawienie dowolnego elementu tablicy wymaga przesunięcia wszystkich jego poprzedników.

Lista połączona to struktura danych, która może pokonać wszystkie ograniczenia tablicy. Korzystanie z listy połączonej jest przydatne, ponieważ:

operator warunkowy w Javie

1. Przydziela pamięć dynamicznie. Wszystkie węzły połączonej listy są przechowywane w pamięci nieciągle i łączone za pomocą wskaźników.
2. Rozmiar nie stanowi już problemu, gdyż w momencie deklaracji nie musimy określać jego rozmiaru. Lista rośnie zgodnie z zapotrzebowaniem programu i jest ograniczona do dostępnej przestrzeni pamięci.

Lista pojedynczo połączona lub łańcuch jednokierunkowy

Listę pojedynczo połączoną można zdefiniować jako zbiór uporządkowanego zestawu elementów. Liczba elementów może się różnić w zależności od potrzeb programu. Węzeł na liście pojedynczo połączonej składa się z dwóch części: części danych i części łącza. Część danych węzła przechowuje aktualne informacje, które ma być reprezentowane przez węzeł, natomiast część łącza węzła przechowuje adres jego bezpośredniego następcy.

Łańcuch jednokierunkowy lub lista pojedynczo połączona może być poruszana tylko w jednym kierunku. Innymi słowy, możemy powiedzieć, że każdy węzeł zawiera tylko kolejny wskaźnik, dlatego nie możemy przemierzać listy w odwrotnym kierunku.

Rozważmy przykład, w którym oceny uzyskane przez ucznia z trzech przedmiotów są przechowywane na połączonej liście, jak pokazano na rysunku.

różnica między miłością a lubieniem

Na powyższym rysunku strzałka reprezentuje łącza. Część danych każdego węzła zawiera oceny uzyskane przez ucznia z innego przedmiotu. Ostatni węzeł na liście jest identyfikowany przez wskaźnik zerowy, który znajduje się w części adresowej ostatniego węzła. W części danych listy możemy umieścić dowolną liczbę elementów.

Złożoność

Operacje na liście pojedynczo połączonej

Na listach połączonych pojedynczo można wykonać różne operacje. Lista wszystkich takich operacji znajduje się poniżej.

Tworzenie węzła

 struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 

Wprowadzenie

Wstawianie do pojedynczo połączonej listy można wykonać w różnych pozycjach. W zależności od położenia wstawianego nowego węzła, wstawianie jest podzielone na następujące kategorie.

jak otworzyć plik za pomocą Java

Usuwanie i przechodzenie

Usuwanie węzła z pojedynczo połączonej listy można wykonać w różnych pozycjach. W zależności od położenia usuwanego węzła operację dzieli się na następujące kategorie.

Połączona lista w C: Program sterowany menu

 #include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); 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 node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { 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; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
 Enter the location of the node after which you want to perform deletion 
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } 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; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } 

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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********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 node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9