A lista vinculada é um tipo de estrutura de dados dinâmica linear que usamos para armazenar elementos de dados. Matrizes também são um tipo de estrutura de dados linear onde os itens de dados são armazenados em blocos de memória contínuos.
Ao contrário dos arrays, a lista vinculada não precisa armazenar elementos de dados em regiões ou blocos de memória contíguos.
A lista vinculada é composto por elementos conhecidos como 'Nós' que são divididos em duas partes. O primeiro componente é a parte onde armazenamos os dados reais, e o segundo é a parte onde armazenamos o ponteiro para o próximo nó. Este tipo de estrutura é conhecido como ' lista vinculada individualmente .'
Lista vinculada em C++
Este tutorial examinará detalhadamente a lista vinculada individualmente.
A estrutura de uma lista vinculada individualmente é ilustrada no diagrama abaixo
- Como vimos na parte acima, o primeiro nó da lista vinculada é conhecido como ‘cabeça’, enquanto o último nó é chamado de ‘cauda’. É porque nenhum endereço de memória é especificado no último nó, o nó final da lista vinculada terá um próximo ponteiro nulo.
- Como cada nó inclui um ponteiro para o próximo nó, os elementos de dados na lista vinculada não precisam ser retidos em locais contíguos. Os nós podem estar dispersos pela memória. Como cada nó possui o endereço do nó seguinte, podemos acessar os nós sempre que quisermos.
- Podemos adicionar e remover rapidamente itens de dados da lista conectada. Como resultado, a lista vinculada pode aumentar ou contrair dinamicamente. A lista vinculada não possui quantidade máxima de itens de dados que pode conter. Como resultado, podemos adicionar quantos itens de dados quisermos à lista vinculada, desde que haja RAM disponível.
- Como não precisamos especificar antecipadamente quantos itens precisamos na lista vinculada, a lista vinculada economiza espaço de memória além de ser simples de inserir e excluir. O único espaço usado por uma lista encadeada é armazenar o ponteiro para o próximo nó, o que adiciona algum custo.
A seguir, examinaremos as diversas operações que podem ser realizadas em uma lista vinculada.
1) Inserção
A lista vinculada é expandida pela ação de adicionar itens a ela. Embora pareça simples, dada a estrutura da lista encadeada, sabemos que cada vez que um item de dados é adicionado, devemos alterar os próximos ponteiros dos nós anteriores e seguintes do novo item que adicionamos.
O local onde o novo item de dados será inserido é o segundo aspecto a considerar.
Existem três locais onde um item de dados pode ser adicionado à lista vinculada.
a. Começando com a lista vinculada
Abaixo está uma lista conectada dos números 2->4->6->8->10. O cabeçalho apontando para o nó 2 agora apontará para o nó 1, e o próximo ponteiro do nó 1 terá o endereço de memória do nó 2, conforme mostrado na ilustração abaixo, se adicionarmos um novo nó 1 como o primeiro nó da lista .
Como resultado, a nova lista vinculada é 1->2->4->6->8->10.
b. Após o nó fornecido
Neste caso, recebemos um nó e devemos adicionar um novo nó atrás dele. A lista vinculada terá a seguinte aparência se o nó f for adicionado à lista vinculada a->b->c->d->e após o nó c:
Portanto, verificamos se o nó especificado está presente no diagrama acima. Se estiver presente, um novo nó f é criado. Depois disso, apontamos o próximo ponteiro do nó c para o novo nó f. O próximo ponteiro do nó f agora aponta para o nó d.
c. O último item da lista vinculada
No terceiro caso, um novo nó é adicionado ao final da lista vinculada. Leve em consideração a lista vinculada abaixo: a->b->c->d->e, com a adição do nó f no final. Após adicionar o nó, a lista vinculada aparecerá assim.
Como resultado, construímos um novo nó f. O ponteiro final que leva a nulo é então apontado para f, e o próximo ponteiro do nó f é apontado para nulo. Na linguagem de programação abaixo, geramos todos os três tipos de funções de inserção.
Uma lista vinculada pode ser declarada como uma estrutura ou como uma classe em C++. Uma lista vinculada declarada como uma estrutura é uma declaração clássica no estilo C. Uma lista vinculada é usada como uma classe em C++ moderno, principalmente ao usar a biblioteca de modelos padrão.
A estrutura foi usada no aplicativo a seguir para declarar e gerar uma lista vinculada. Seus membros serão dados e um ponteiro para o elemento seguinte.
Programa C++:
#include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -> data = nodeData; newNode1 -> next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -> next; prevNode -> next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -> data = nodeData; newNode1 -> next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -> next != NULL ) last = last -> next; last -> next = newNode1; return; } void displayList ( struct Node *node ) { while ( node != NULL ) { cout <data <'; node="node" -> next; } if ( node== NULL) cout<next, 55 ); cout << 'final linked list: ' endl; displaylist (head); return 0; } < pre> <p> <strong>Output:</strong> </p> <pre> Final linked list: 35-->25-->55-->15-->45-->null </pre> <h3>2) Deletion</h3> <p>Similar to insertion, deleting a node from a linked list requires many points from which the node might be eliminated. We can remove the linked list's first, last, or kth node at random. We must correctly update the next pointer and all other linked list pointers in order to maintain the linked list after deletion.</p> <p>In the following C++ implementation, we have two deletion methods: deleting the list's initial node and deleting the list's last node. We begin by adding nodes to the head of the list. The list's contents are then shown following each addition and deletion.</p> <p> <strong>C++ Program:</strong> </p> <pre> #include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <'; if ( temp="=" null ) cout << 'null' endl; head="deletingFirstNode" (head); 'linked list after deleting node' < next <data cout<<'null'<<endl; last data 'null'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data></pre></next,></data></data> 2) Exclusão
Semelhante à inserção, a exclusão de um nó de uma lista vinculada requer muitos pontos dos quais o nó pode ser eliminado. Podemos remover o primeiro, o último ou o k-ésimo nó da lista vinculada aleatoriamente. Devemos atualizar corretamente o próximo ponteiro e todos os outros ponteiros da lista vinculada para manter a lista vinculada após a exclusão.
Na implementação C++ a seguir, temos dois métodos de exclusão: exclusão do nó inicial da lista e exclusão do último nó da lista. Começamos adicionando nós ao topo da lista. O conteúdo da lista é mostrado após cada adição e exclusão.
Programa C++:
data local java
#include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <\'; if ( temp="=" null ) cout << \'null\' endl; head="deletingFirstNode" (head); \'linked list after deleting node\' < next <data cout<<\'null\'<<endl; last data \'null\'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data> Contagem de nós
Ao percorrer a lista vinculada, o processo de contagem do número de nós pode ser realizado. Na abordagem anterior, vimos que se precisássemos inserir/excluir um nó ou exibir o conteúdo da lista vinculada, teríamos que percorrer a lista vinculada desde o início.
Definir um contador e incrementar à medida que percorremos cada nó nos fornecerá o número de nós na lista vinculada.
Diferenças entre array e lista vinculada:
| Variedade | Lista vinculada |
|---|---|
| As matrizes têm um tamanho definido. | O tamanho da lista vinculada é variável. |
| Inserir um novo elemento é difícil. | Inserção e exclusão são mais simples. |
| O acesso é permitido aleatoriamente. | Nenhum acesso aleatório é possível. |
| Os elementos estão relativamente próximos ou contíguos. | Os elementos não são contíguos. |
| Nenhum espaço adicional é necessário para o ponteiro a seguir. | O ponteiro a seguir requer memória adicional. |
Funcionalidade
Como listas vinculadas e matrizes são estruturas de dados lineares que contêm objetos, elas podem ser utilizadas de maneira semelhante para a maioria dos aplicativos.
A seguir estão alguns exemplos de aplicativos de lista vinculada:
- Pilhas e filas podem ser implementadas usando listas vinculadas.
- Quando precisamos expressar gráficos como listas de adjacências, podemos usar uma lista vinculada para implementá-los.
- Também podemos usar uma lista vinculada para conter um polinômio matemático.
- No caso de hashing, listas vinculadas são empregadas para implementar os buckets.
- Quando um programa requer alocação dinâmica de memória, podemos utilizar uma lista vinculada porque as listas vinculadas são mais eficientes neste caso.
Conclusão
Listas vinculadas são estruturas de dados usadas para armazenar elementos de dados de forma linear, mas não contígua. Uma lista vinculada é composta de nós com dois componentes cada. O primeiro componente é composto de dados, enquanto a segunda metade possui um ponteiro que armazena o endereço de memória do próximo membro da lista.
Como sinal de que a lista vinculada terminou, o último item da lista tem seu próximo ponteiro definido como NULL. A Cabeça é o primeiro item da lista. A lista vinculada permite uma variedade de ações, como inserção, exclusão, passagem e assim por diante. As listas vinculadas são preferidas aos arrays para alocação dinâmica de memória.
Listas vinculadas são difíceis de imprimir ou percorrer porque não podemos acessar os elementos aleatoriamente como arrays. Quando comparados aos arrays, os procedimentos de inserção-exclusão são menos dispendiosos.
Neste tutorial, aprendemos tudo o que há para saber sobre listas vinculadas lineares. As listas vinculadas também podem ser duplamente vinculadas ou circulares. Em nossos próximos tutoriais, examinaremos essas listas em detalhes.