Estrutura de dados - lista duplamente vinculada

A lista duplamente vinculada é uma variação da lista vinculada na qual a navegação é possível de ambas as maneiras, tanto para frente quanto para trás facilmente em comparação com a lista vinculada única. A seguir estão os termos importantes para entender o conceito de lista duplamente vinculada.

  • Link - Cada link de uma lista vinculada pode armazenar dados chamados de elemento.

  • Next - Cada link de uma lista vinculada contém um link para o próximo link chamado Próximo.

  • Prev - Cada link de uma lista vinculada contém um link para o link anterior chamado Anterior.

  • LinkedList - Uma lista vinculada contém o link de conexão para o primeiro link denominado Primeiro e para o último link denominado Último.

Representação de lista duplamente vinculada

Conforme a ilustração acima, a seguir estão os pontos importantes a serem considerados.

  • A lista duplamente vinculada contém um elemento de link denominado primeiro e último.

  • Cada link carrega um campo (s) de dados e dois campos de link chamados next e prev.

  • Cada link está vinculado ao seu próximo link usando o próximo link.

  • Cada link está vinculado a seu link anterior usando seu link anterior.

  • O último link carrega um link como nulo para marcar o final da lista.

Operações básicas

A seguir estão as operações básicas suportadas por uma lista.

  • Insertion - Adiciona um elemento no início da lista.

  • Deletion - Exclui um elemento do início da lista.

  • Insert Last - Adiciona um elemento no final da lista.

  • Delete Last - Exclui um elemento do final da lista.

  • Insert After - Adiciona um elemento após um item da lista.

  • Delete - Exclui um elemento da lista usando a tecla.

  • Display forward - Exibe a lista completa de uma maneira direta.

  • Display backward - Exibe a lista completa de forma reversa.

Operação de Inserção

O código a seguir demonstra a operação de inserção no início de uma lista duplamente vinculada.

Exemplo

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

Operação de Exclusão

O código a seguir demonstra a operação de exclusão no início de uma lista duplamente vinculada.

Exemplo

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

Inserção no final de uma operação

O código a seguir demonstra a operação de inserção na última posição de uma lista duplamente vinculada.

Exemplo

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

Para ver a implementação na linguagem de programação C, clique aqui .