TechCodeview

• A csatolt lista a meghívott objektumok gyűjteményeként definiálható csomópontok amelyek véletlenszerűen tárolódnak a memóriában.
• Egy csomópont két mezőt tartalmaz, azaz az adott címen tárolt adatokat és a mutatót, amely a következő csomópont címét tartalmazza a memóriában.
• A lista utolsó csomópontja tartalmazza a nullára mutató mutatót.

A linkelt lista használata

• A listának nem szükséges folyamatosan jelen lennie a memóriában. A csomópont bárhol elhelyezkedhet a memóriában, és összekapcsolható egy lista létrehozásához. Ezzel optimalizált helykihasználás érhető el.
• A lista mérete a memória méretére korlátozódik, és nem kell előre megadni.
• Üres csomópont nem lehet a hivatkozott listában.
• Az egyedileg csatolt listában primitív típusok vagy objektumok értékeit tárolhatjuk.

Miért használjunk linkelt listát tömbön keresztül?

Eddig tömb adatszerkezetet használtunk a memóriában külön-külön tárolandó elemek csoportjának rendszerezésére. A tömbnek azonban számos előnye és hátránya van, amelyeket ismerni kell ahhoz, hogy eldönthessük, milyen adatszerkezetet használunk a programban.

A tömb a következő korlátozásokat tartalmazza:

1. A tömb méretét előre ismerni kell, mielőtt a programban használnánk.
2. A tömb méretének növelése időigényes folyamat. A tömb méretét futás közben szinte lehetetlen bővíteni.
3. A tömb összes elemét folyamatosan tárolni kell a memóriában. Bármely elem beszúrásához a tömbbe az összes elődjét el kell tolni.

A linkelt lista az az adatstruktúra, amely képes legyőzni egy tömb összes korlátját. A linkelt lista használata azért hasznos, mert

hogyan tudhatom meg a monitorom méretét

1. Dinamikusan allokálja a memóriát. A csatolt lista összes csomópontja nem összefüggően tárolódik a memóriában, és mutatók segítségével összekapcsolódik.
2. A méretezés már nem jelent problémát, hiszen a méretét a bejelentéskor nem kell meghatároznunk. A lista a program igényei szerint bővül, és a rendelkezésre álló memóriaterületre korlátozódik.

Egyedileg kapcsolódó lista vagy egyirányú lánc

Az egyedileg csatolt lista az elemek rendezett halmazának gyűjteményeként definiálható. Az elemek száma a program igénye szerint változhat. Az egyedileg csatolt lista egyik csomópontja két részből áll: adatrészből és hivatkozási részből. A csomópont adatrésze a csomópont által reprezentálandó aktuális információkat tárolja, míg a csomópont link része a közvetlen utódjának címét tárolja.

Az egyirányú láncon vagy egyedileg összekapcsolt listán csak egy irányban lehet bejárni. Más szóval azt mondhatjuk, hogy minden csomópont csak a következő mutatót tartalmazza, ezért a listán fordított irányban nem haladhatunk be.

programozási minták java

Tekintsünk egy példát, ahol a tanuló által három tantárgyból szerzett jegyeket az ábrán látható módon egy linkelt listában tároljuk.

A fenti ábrán a nyíl a hivatkozásokat jelöli. Minden csomópont adatrésze tartalmazza a hallgató által a különböző tantárgyból szerzett érdemjegyeket. A lista utolsó csomópontját a null mutató azonosítja, amely az utolsó csomópont cím részében található. A lista adat részében tetszőleges számú elem szerepelhet.

java parseint

Bonyolultság

Műveletek az egyedileg összekapcsolt listán

Különféle műveletek végezhetők el egyedileg összekapcsolt listán. Az alábbiakban felsoroljuk az összes ilyen műveletet.

Csomópont létrehozása

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

Beillesztés

Az egyedileg csatolt listába való beillesztés különböző pozíciókban hajtható végre. A beszúrandó új csomópont helyzete alapján a beillesztés a következő kategóriákba sorolható.

Törlés és bejárás

Egy csomópont törlése egy egyedileg csatolt listából különböző pozíciókban hajtható végre. A törlendő csomópont pozíciója alapján a művelet a következő kategóriákba sorolható.

Hivatkozott lista a C-ben: Menüvezérelt program

 #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; } } } 

Kimenet:

 *********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