Como criar uma lista duplamente encadeada em C

Escrito por g.s. jackson | Traduzido por guilherme vieira
Como criar uma lista duplamente encadeada em C

Listas duplamente encadeadas apresentam uma alternativa eficiente para outras estruturas de dados, como vetores

Comstock/Comstock/Getty Images

Programadores usam listas duplamente encadeadas como estruturas de dados de acesso linear. Isso significa que ele pode iniciar no começo da lista (chamada de cabeça) e mover-se adiante através da lista, um item por vez. Esse método de armazenamento de dados também permite que o programador adicione dados à lista eficientemente, oferecendo uma alternativa mais versátil a outras estruturas de dados, como vetores dinâmicos. Este exemplo mostra como construir uma lista duplamente encadeada simples, a qual permite navegação em duas direções (para frente e para trás).

Nível de dificuldade:
Moderadamente desafiante

Outras pessoas estão lendo

O que você precisa?

  • Editor de texto
  • Compilador de C/C++ ou uma IDE (como Microsoft Visual Studio ou Dev-C++)

Lista completaMinimizar

Instruções

  1. 1

    Crie a estrutura do nó, que servirá como o tipo de dado na lista. No editor de texto, digite o seguinte código: #include <stdlib.h> int main{ struct listNode{ int data; strut listNode *prev; strut listNode *next; }; return 0; } O bloco de código "struct listNode" cria um modelo para os itens que povoarão a lista. Esse modelo define um "listNode" (Nó da lista) contendo três elementos: um item de dados (no caso, um inteiro) e ponteiros para o próximo item e também para o anterior. Um ponteiro é uma variável que guarda um endereço de memória. Ponteiros são usados para serem referidos a outras estruturas de dados guardadas profundamente ou para a memória alocada dinamicamente, durante a execução do código.

  2. 2

    Declare as variáveis que organizarão a estrutura da lista. Insira o seguinte código de exemplo no arquivo de texto: int size; listNode *head; listNode *tail; tail = head; head = tail; Esses dois ponteiros são o início e o fim da lista, respectivamente. Usando-os, o programador sabe onde estão o início e o fim da lista, simplesmente verificando se o nó atual é o ponteiro da "cabeça" ou da "cauda". Ambos referem-se um ao outro no caso de uma lista vazia.

  3. 3

    Crie um algoritmo simples para adicionar na lista encadeada. Siga este código de exemplo: void append(int num){ struct listNode *tracer = head; struct listNode *newNode = (struct listNode*)malloc(sizeof(struct listNode)); newNode->data = num; if (head == NULL){ head = newNode; tail = newNode; newNode->prev = head; newNode->next = tail; } else{ while (tracer->next != tail) {tracer = tracer->next;} newNode->prev = tracer; newNode->next = tail; tracer->next = node; tail = node; } size++; } Esse código adiciona um nó ao final da lista. Isso começa criando um ponteiro para a cabeça ("tracer"). Depois, cria um ponteiro para um bloco de memória alocada dinamicamente e direcionada para um "listNode" recém criado (o newNode) e faz o dado guardado naquele nó receber o inteiro guardado em "num". Se a cabeça apontar para NULL (o que significa que a lista está vazia, uma vez que a cabeça aponta para nada), então o código insere o nó no começo da lista. Caso contrário, o laço "while" circula através dos nós na lista até encontrar o último. Quando "tracer" apontar para o último elemento na lista, o código inserirá o nó. O comando final incrementa o inteiro "size" (tamanho) que guarda o número de elementos na lista.

  4. 4

    Crie um algoritmo que remova um item do fim da lista: void removeNode(){ if (tail != head){ struct listNode *end = tail; tail = tail->prev; free(end); size--; } } Esse código cria um ponteiro ("end") para o último elemento da lista (o mesmo para o qual "tail" aponta). Depois disso, "tail" passa a apontar para o penúltimo elemento (o nó apontado pelo ponteiro "prev" no último elemento). Por fim, a variável que guarda o tamanho da lista, "size", é decrementada e a memória usada pelo último nó, referenciada por "end", é liberada para uso posterior.

Dicas & Advertências

  • Isso é apenas o esqueleto de uma lista duplamente encadeada. Outras funcionalidades, como ordenação, inserção e remoção do meio da lista, podem ser adicionadas à funcionalidade básica.

Não deixe de ver

Filtro:
  • Geral
  • Artigos
  • Slides
  • Vídeos
Mostrar:
  • Mais relevantes
  • Mais lidos
  • Mais recentes

Nenhum artigo disponível

Nenhum slide disponível

Nenhum vídeo disponível

Direitos autorais © 1999-2015 Demand Media, Inc.

O uso deste site constitui plena aceitação dos Termos de Uso e Política de privacidade de eHow. Ad Choices pt-BR

Demand Media