Depois dos arrays, a segunda estrutura de dados mais popular é a lista vinculada. Uma lista encadeada é uma estrutura de dados linear, feita de uma cadeia de nós em que cada nó contém um valor e um ponteiro para o próximo nó da cadeia. Neste artigo, vamos ver como implementar uma lista vinculada em C.
O que é lista vinculada em C?
Uma lista vinculada é uma estrutura de dados linear. Cada lista vinculada possui duas partes, a seção de dados e a seção de endereço que contém o endereço do próximo elemento na lista, que é chamado de nó.
O tamanho da lista vinculada não é fixo e os itens de dados podem ser adicionados em qualquer local da lista. A desvantagem é que, para chegar a um nó, devemos percorrer todo o caminho desde o primeiro nó até o nó de que necessitamos. A lista vinculada é como uma matriz, mas, ao contrário de uma matriz, não é armazenada sequencialmente na memória.
Os tipos mais populares de uma lista vinculada são:
Exemplo de lista vinculada
Formato: [dados, endereço]
Cabeça -> [3,1000] -> [43,1001] -> [21,1002]
No exemplo, o número 43 está presente na localização 1000 e o endereço está presente no nó anterior. É assim que uma lista vinculada é representada.
Funções básicas de lista vinculada
Existem várias funções que podem ser implementadas na lista vinculada em C. Vamos tentar entendê-las com a ajuda de um programa de exemplo.Primeiro, criamos uma lista, exibimos, inserimos em qualquer local, excluímos um local. O código a seguir mostrará como realizar operações na lista.
#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct node {int info struct node * next} struct node * start = NULL int main () {escolha int enquanto (1) {printf ('n MENU n') printf ('n 1.Criar n') printf ('n 2.Exibir n') printf ('n 3.Inserir em o n inicial ') printf (' n 4.Insira no final n ') printf (' n 5.Insira na posição especificada n ') printf (' n 6.Excluir do início n ') printf (' n 7.Excluir do final n ') printf (' n 8.Excluir da posição especificada n ') printf (' n 9.Sair n ') printf (' n ----------------- --------------------- n ') printf (' Digite sua escolha: t ') scanf ('% d ', & escolha) switch (escolha) {caso 1 : create () interromper o caso 2: display () interromper o caso 3: insert_begin () interromper o caso 4: insert_end () interromper o caso 5: insert_pos () interromper o caso 6: delete_begin () interromper o caso 7: delete_end () interromper o caso 8: delete_pos () break case 9: exit (0) break default: printf ('n Wrong Choice: n') break}} return 0} voi d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nDigite o valor dos dados para o nó: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> próximo! = NULL) {ptr = ptr-> próximo} ptr-> próximo = temp}} void display () {struct node * ptr if (start == NULL) {printf ('nList está vazio: n ') return} else {ptr = start printf (' nOs elementos da lista são: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> próximo}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nDigite o valor de dados para o nó: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} p rintf ('nInsira o valor dos dados para o nó: t') scanf ('% d', & temp-> info) temp-> próximo = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> próximo! = NULL) {ptr = ptr-> próximo} ptr-> próximo = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nDigite a posição do novo nó a ser inserido: t') scanf ('% d' , & pos) printf ('nDigite o valor dos dados do nó: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [Handle with care] n') return}} temp-> next = ptr-> próximo ptr -> próximo = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nO elemento excluído é:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nO elemento excluído é:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > próximo! = NULL) {temp = ptr ptr = ptr-> próximo} temp-> próximo = NULL printf ('nO elemento excluído é:% dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nA lista está vazia: n') exit (0)} else {printf ('nInsira a posição do nó a ser excluído : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nO elemento excluído é:% dt ', ptr-> info) free (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nO elemento excluído é: % dt ', ptr-> info) grátis (ptr)}}}A primeira parte deste código é a criação de uma estrutura. Uma estrutura de lista vinculada é criada para que possa conter os dados e o endereço conforme necessário. Isso é feito para dar ao compilador uma ideia de como o nó deve ser.
struct node {int info struct node * next}Na estrutura, temos uma variável de dados chamada info para conter os dados e uma variável de ponteiro para apontar para o endereço. Existem várias operações que podem ser feitas em uma lista vinculada, como:
- crio()
- exibição()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Essas funções são chamadas pela função principal baseada em menu. Na função principal, recebemos informações do usuário com base na operação que o usuário deseja fazer no programa. A entrada é então enviada para a caixa do switch e com base na entrada do usuário.
Com base na entrada fornecida, a função será chamada. A seguir, temos diferentes funções que precisam ser resolvidas. Vamos dar uma olhada em cada uma dessas funções.
Criar Função
Primeiro, há uma função de criação para criar a lista vinculada. Esta é a maneira básica como a lista vinculada é criada. Vamos examinar o código.
void create () {struct node * temp, * ptr printf ('nInsira o valor dos dados para o nó: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}Resultado
Primeiro, dois ponteiros são criados do tipo nó, ptr e temp . Pegamos o valor que precisa ser adicionado na lista vinculada do usuário e o armazenamos na parte info da variável temp e atribuímos temp de next, que é a parte do endereço, como null. Há um ponteiro de início segurando o início da lista. Em seguida, verificamos o início da lista. Se o início da lista for nulo, atribuímos temp ao ponteiro de início. Caso contrário, atravessamos para o último ponto onde os dados foram adicionados.
Para isso, atribuímos a ptr o valor inicial e atravessamos até ptr-> próximo = nulo . Nós então atribuímos ptr-> próximo o endereço de temp. De forma semelhante, existe um código fornecido para inserir no início, inserir no final e inserir em um local especificado.
Função de exibição
Aqui está o código para a função de exibição.
void display () {struct node * ptr if (start == NULL) {printf ('nList está vazio: n') return} else {ptr = start printf ('nOs elementos da lista são: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> próximo}}}Resultado
Na função de exibição, primeiro verificamos se a lista está vazia e retornamos se ela está vazia. Na próxima parte, atribuímos o valor inicial a ptr. Em seguida, executamos um loop até que ptr seja nulo e imprimimos o elemento de dados para cada nó, até que ptr seja nulo, o que especifica o fim da lista.
Apagar Função
Aqui está o trecho de código para excluir um nó da lista vinculada.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nA lista está vazia: n') exit (0)} else {printf ('nIntroduza a posição do nó a ser excluído: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nO elemento excluído é:% dt ', ptr-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe o elemento excluído é:% dt ', ptr-> info) free (ptr)}}}Resultado
No processo de exclusão, primeiro verifica se a lista está vazia, se sim existe. Se não estiver vazio, pede ao usuário que a posição seja excluída. Uma vez que o usuário entra na posição, ele verifica se é a primeira posição, se sim atribui ptr para iniciar e move o ponteiro de início para o próximo local e exclui ptr. Se o posição não é zero , então ele executa um loop for de 0 até a posição inserida pelo usuário e armazenada no pos variável. Há uma instrução if para decidir se a posição inserida não está presente. E se ptr é igual a nulo , então não está presente.
Nós atribuir ptr a temp no loop for e ptr então passa para a próxima parte. Depois disso, quando a posição for encontrada. Fazemos a variável temp para conter o valor de ptr-> próximo pulando assim o ptr. Em seguida, ptr é excluído. Da mesma forma, isso pode ser feito para a exclusão do primeiro e do último elemento.
Lista duplamente vinculada
É chamada de lista duplamente ligada porque existem dois ponteiros , um aponta para o próximo nó e outro aponta para o nó anterior. As operações realizadas em duplamente vinculado são semelhantes às de uma lista unicamente vinculada. Aqui está o código para operações básicas.
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode Lista typedef PtrToNode Posição struct Node {int e Posição anterior Posição seguinte} void Insert (int x, Lista l, Posição p) {Posição TmpCell TmpCell = (struct Node *) malloc (sizeof (Nó de estrutura)) if (TmpCell == NULL) printf ('Memória sem espaço') else {TmpCell-> e = x TmpCell-> anterior = p TmpCell-> próximo = p-> próximo p-> próximo = TmpCell}} void Delete (int x, List l) {Posição p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> p2 anterior = p -> próximo p1 - > próximo = p -> próximo if (p2! = NULL) // se o nó não é o último nó p2 -> anterior = p -> anterior} else printf ('Elemento não existe !!! n')} void Display (List l) {printf ('Os elementos da lista são ::') Posição p = l-> próximo enquanto (p! = NULL) {printf ('% d ->', p-> e) p = p- > próximo}} int main () {int x, pos, ch, i Lista l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> anterior = NULL l-> next = NULL Lista p = l printf ('IMPLEMENTAÇÃO DA LISTA DUPLA LIGADA DE L IST ADTnn ') faça {printf (' nn1. CRIAR 2. EXCLUIR 3. EXIBIR 4. SAIR Insira a escolha :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Insira o elemento a ser inserido :: ') scanf ('% d', & x) printf ('Digite a posição do elemento ::') scanf ('% d', & pos) para (i = 1 inext} Insert (x, l, p) break case 2: p = l printf ('Insira o elemento a ser excluído ::') scanf ('% d', & x) Delete (x, p) break case 3: Display (l) pausa}} enquanto (ch<4) } Resultado
Então, como você pode ver, o conceito de operações é bastante simples. A lista duplamente vinculada tem as mesmas operações que a lista vinculada simples na linguagem de programação C. A única diferença é que há outra variável de endereço que ajuda a percorrer a lista melhor em uma lista duplamente vinculada.
Espero que você tenha entendido como realizar operações básicas em uma lista unida e duplamente vinculada em C.
tratamento de exceção no procedimento armazenado oracle
Se você deseja aprender Linked List em Java, aqui está um .
Se tiver alguma dúvida, fique à vontade para fazer todas as suas perguntas na seção de comentários da “Lista Vinculada em C” e nossa equipe terá prazer em responder.