• Lista vinculada pode ser definida como uma coleção de objetos chamados nós que são armazenados aleatoriamente na memória.
• Um nó contém dois campos, ou seja, dados armazenados naquele endereço específico e o ponteiro que contém o endereço do próximo nó na memória.
• O último nó da lista contém um ponteiro para nulo.

Usos da lista vinculada

• A lista não precisa estar presente de forma contígua na memória. O nó pode residir em qualquer lugar da memória e ser vinculado para formar uma lista. Isto alcança uma utilização otimizada do espaço.
• o tamanho da lista é limitado ao tamanho da memória e não precisa ser declarado antecipadamente.
• O nó vazio não pode estar presente na lista vinculada.
• Podemos armazenar valores de tipos primitivos ou objetos na lista vinculada individualmente.

Por que usar lista vinculada em vez de array?

Até agora, estávamos usando uma estrutura de dados array para organizar o grupo de elementos que seriam armazenados individualmente na memória. Porém, Array possui diversas vantagens e desvantagens que devem ser conhecidas para decidir a estrutura de dados que será utilizada ao longo do programa.

Array contém as seguintes limitações:

1. O tamanho do array deve ser conhecido antecipadamente antes de usá-lo no programa.
2. Aumentar o tamanho da matriz é um processo demorado. É quase impossível expandir o tamanho do array em tempo de execução.
3. Todos os elementos do array precisam ser armazenados de forma contígua na memória. A inserção de qualquer elemento no array requer a mudança de todos os seus antecessores.

Lista vinculada é a estrutura de dados que pode superar todas as limitações de um array. Usar a lista vinculada é útil porque,

converter string em enum

1. Ele aloca a memória dinamicamente. Todos os nós da lista vinculada são armazenados de forma não contígua na memória e vinculados entre si com a ajuda de ponteiros.
2. O dimensionamento não é mais um problema, pois não precisamos definir seu tamanho no momento da declaração. A lista cresce conforme a demanda do programa e limitada ao espaço de memória disponível.

Lista vinculada individualmente ou cadeia unidirecional

A lista vinculada individualmente pode ser definida como a coleção de um conjunto ordenado de elementos. O número de elementos pode variar de acordo com a necessidade do programa. Um nó na lista vinculada individualmente consiste em duas partes: parte de dados e parte de link. A parte de dados do nó armazena informações reais que serão representadas pelo nó, enquanto a parte de link do nó armazena o endereço de seu sucessor imediato.

A cadeia unidirecional ou a lista vinculada individualmente podem ser percorridas apenas em uma direção. Em outras palavras, podemos dizer que cada nó contém apenas o próximo ponteiro, portanto não podemos percorrer a lista na direção inversa.

Considere um exemplo onde as notas obtidas pelo aluno em três disciplinas são armazenadas em uma lista vinculada conforme mostrado na figura.

mylivecricket para críquete ao vivo

Na figura acima, a seta representa os links. A parte de dados de cada nó contém as notas obtidas pelo aluno nas diferentes disciplinas. O último nó da lista é identificado pelo ponteiro nulo que está presente na parte do endereço do último nó. Podemos ter quantos elementos precisarmos, na parte de dados da lista.

Complexidade

Operações em lista vinculada individualmente

Existem várias operações que podem ser executadas em uma lista vinculada individualmente. Uma lista de todas essas operações é fornecida abaixo.

Criação de nós

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

Inserção

A inserção em uma lista vinculada individualmente pode ser realizada em diferentes posições. Com base na posição do novo nó que está sendo inserido, a inserção é categorizada nas seguintes categorias.

analisar string para int

Exclusão e travessia

A exclusão de um nó de uma lista vinculada individualmente pode ser realizada em diferentes posições. Com base na posição do nó que está sendo excluído, a operação é categorizada nas seguintes categorias.

Lista vinculada em C: programa baseado em 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; } } } 

Saída:

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