Lista duplamente vinculada: C++, Python (Code Exemplo)

O que é uma lista duplamente encadeada?

Em uma lista duplamente encadeada, cada nó possui links tanto para o nó anterior quanto para o próximo. Cada nó consiste em três elementos: um que armazena os dados e os outros dois que são ponteiros para o nó anterior e o próximo. Esses dois ponteiros permitem navegar para frente ou para trás a partir de um nó específico.

Aqui está a estrutura básica de uma lista duplamente encadeada.

Estrutura de uma lista duplamente vinculada

Toda lista encadeada possui um nó cabeça e um nó cauda. O nó cabeça não possui um nó cauda. prev (ponteiro anterior) nó, e o nó de cauda não tem Próximo nó.

Aqui estão alguns termos importantes para uma Lista Duplamente Encadeada:

• prev: Cada nó está vinculado ao seu nó anterior. É usado como um ponteiro ou link.
• Seguinte: Cada nó está vinculado ao seu próximo nó. É usado como um ponteiro ou link.
• Data: Isso é usado para armazenar dados em um nó. Os dados podem conter outros elementos. Estruturas de dados dentro dele. Por exemplo, strings, dicionários, conjuntos, mapas de hash e outras estruturas podem ser armazenadas no campo de dados.

Eis a estrutura básica de um único nó em uma Lista Duplamente Encadeada:

Estrutura de um nó em uma lista duplamente vinculada

Operações de lista duplamente vinculada

As operações de uma lista duplamente encadeada incluem adicionar, excluir, inserir e remover nós, bem como percorrer a lista de cima para baixo ou de baixo para cima.

Segue a lista de operações que podem ser implementadas em uma Lista Duplamente Encadeada:

• Inserção na frente
• Inserção na cauda ou no último nó
• Inserção após um nó
• Inserção antes de um nó
• Exclusão da frente
• Exclusão da cauda
• Pesquise e exclua um nó
• Atravessar da cabeça à cauda
• Atravesse a cauda até a cabeça

A implementação e o pseudocódigo para cada uma dessas operações seguem abaixo.

Inserção em frente de uma lista duplamente encadeada

A inserção no início significa criar um nó na lista encadeada e colocá-lo no começo da lista.

Por exemplo, existe um nó específico. 15É necessário adicioná-lo como o nó principal.

Duas condições importantes devem ser consideradas ao realizar esta operação:

1. O novo nó torna-se o nó principal se a lista duplamente encadeada estiver vazia.
2. Se já existir um nó cabeça, o nó cabeça anterior será substituído pelo novo nó.

Segue o pseudocódigo para esta operação:

function insertAtFront(ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = newNode
  newNode.next = ListHead
  newNode.prev = NULL
  return ListHead

Inserção no nó frontal

Inserção no final de uma lista duplamente encadeada

Inserir no final significa criar um nó na lista encadeada e colocá-lo no final.

Existem dois métodos para realizar essa operação:

• Método 1: Comece a percorrer a lista duplamente encadeada a partir do início até Próximo torna-se nulo. Em seguida, vincule o novo nó ao Próximo ponteiro.
• Método 2: Pegue o último nó da Lista Duplamente Encadeada. Então, o Próximo O ponteiro do último nó aponta para o novo nó. O novo nó torna-se o nó final.

Segue o pseudocódigo para inserção no nó final:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Inserção no final da lista vinculada

Inserção após um nó

Considere uma lista duplamente encadeada existente como a seguinte:

O objetivo é inserir um nó específico que será vinculado após o nó com o valor 12.

Passo 1) Percorra o array do nó inicial até o último nó. Verifique qual nó possui o valor. 12.

Passo 2) Crie um novo nó e atribua-o como o próximo ponteiro do nó. 12. O Próximo O número de nós do novo nó será 15.

Segue o pseudocódigo para inserir um nó após outro nó em uma lista duplamente encadeada:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Inserção após um nó

Inserção antes de um nó

Essa operação é semelhante à inserção após um nó. Um valor de nó específico é pesquisado, então um novo nó é criado e inserido antes do nó pesquisado.

Para inserir um nó específico 15 antes do nó 12, Siga esses passos:

Passo 1) Percorra a lista vinculada do nó principal ao nó final.

Passo 2) Verifique se o ponteiro seguinte do nó atual tem o valor 12.

Passo 3) Insira o novo nó como o Próximo nó do nó atual.

Segue o pseudocódigo para inserir um nó antes de outro nó em uma lista duplamente encadeada:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.next.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Inserindo um nó antes de um nó

Excluir o cabeçalho da lista duplamente encadeada

O nó inicial em uma lista duplamente encadeada não possui nenhum nó anterior. Portanto, Próximo O ponteiro se torna o novo nó cabeça quando o nó cabeça atual é removido. Liberar a memória ocupada por um nó excluído também é necessário.

Aqui estão os passos para excluir o nó principal:

Passo 1) Atribua uma variável ao nó principal atual.

Passo 2) Visite a página de produto do Próximo nó do nó principal atual e faça o prev ponteiro NULL. Isso desconecta o segundo nó do primeiro nó.

Passo 3) Libere a memória ocupada pelo nó cabeçalho anterior.

Aqui está o pseudocódigo para remover o primeiro elemento de uma lista duplamente encadeada:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Excluindo o nó principal

É necessário liberar a memória alocada após qualquer exclusão. Caso contrário, a memória do bloco excluído permanece ocupada durante toda a execução do programa, e nenhum outro aplicativo poderá usar esse segmento de memória.

Excluir a cauda da lista duplamente encadeada

Essa operação é semelhante à remoção do cabeçalho. Em vez do cabeçalho, remove-se a cauda. Para identificar um nó como cauda, ​​verifica-se se o ponteiro para o próximo nó é nulo. Após a remoção da cauda, ​​a memória deve ser liberada.

Esta operação também é conhecida como exclusão da parte traseira.

Aqui estão as etapas para fazer isso:

Passo 1) Percorra a lista até o último nó da lista duplamente encadeada.

Passo 2) Atribua uma variável ou ponteiro ao nó final.

Passo 3) Colocou o Próximo Atribua um ponteiro a NULL e libere a memória do nó de cauda.

Segue o pseudocódigo para excluir o nó final:

function deleteTail(ListHead):
  head = ListHead
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  Tail = ListHead
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

Pesquisar e excluir um nó de uma lista duplamente encadeada

Esta operação procura um valor de nó específico e remove esse nó. Uma busca linear é necessária porque a lista ligada é uma estrutura de dados linear. Após a remoção, a memória deve ser liberada.

Aqui estão os passos para pesquisar e excluir um nó em uma Lista Duplamente Encadeada:

Passo 1) Percorra a lista encadeada a partir do início até que o valor do nó seja igual ao item de busca.

Passo 2) Atribua uma variável excluirNó ao nó correspondente.

Passo 3) Conecte o nó anterior do excluirNó para o próximo nó e defina o do próximo nó prev ponteiro para o nó anterior.

Passo 4) Liberte a memória do excluirNó.

Segue o pseudocódigo para pesquisar e excluir um nó de uma lista encadeada:

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

Operação de pesquisa e exclusão

Percorrer uma lista duplamente encadeada de trás para frente

A iteração a partir do nó inicial percorre o próximo nó até encontrar NULL. Ao percorrer cada nó, o valor pode ser impresso. Aqui estão os passos para percorrer a lista na direção direta:

Passo 1) Atribua um ponteiro ou variável ao nó principal atual.

Passo 2) Percorra o próximo nó da cabeça até obter NULL.

Passo 3) Imprima os dados do nó em cada iteração.

Passo 4) Retorne o nó principal.

Aqui está o pseudocódigo para percorrer uma lista duplamente encadeada de baixo para cima:

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals NULL:
    print head.data
    head = head.next
  return ListHead

O retorno não é obrigatório. No entanto, retornar o nó principal após as operações é uma boa prática.

Percorrer uma lista duplamente encadeada de trás para frente

Esta operação é o inverso da travessia frontal. A abordagem é a mesma, com uma pequena diferença: primeiro, alcance o nó final e, em seguida, caminhe de trás para frente até o nó inicial usando o prev ponteiro.

Aqui estão os passos para percorrer uma lista duplamente encadeada de trás para frente:

Passo 1) Percorra a rota até alcançar o nó final.

Passo 2) A partir do nó final, percorra usando prev até que o nó anterior seja NULL. O prev O ponteiro é nulo para o nó principal.

Passo 3) A cada iteração, imprima os dados do nó.

Aqui está o pseudocódigo para percorrer a lista de trás para frente:

function traverseFromBack(ListHead):
  head = ListHead
  while head.next is not NULL:
    head = head.next
  tail = head
  while tail is not NULL:
    print tail.value
    tail = tail.prev
  return ListHead

Diferença entre listas simplesmente encadeadas e listas duplamente encadeadas

A principal diferença entre uma lista simplesmente encadeada e uma lista duplamente encadeada é o número de ligações que cada nó possui.

Eis a diferença entre os nós de uma lista simplesmente encadeada e uma lista duplamente encadeada:

Lista Duplamente Vinculada em C++

Abaixo segue uma lista completa. C++ Implementação de uma lista duplamente encadeada com operações de inserção, exclusão, busca e percurso.

#include<iostream>
using namespace std;
struct node{
  int data;
  struct node *next;
  struct node *prev;
};
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead != NULL){
    listHead->prev = newNode;
    newNode->next = listHead;
  }
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
}
void insertEnd(node* &listHead, int value){
  if(listHead == NULL){
    insertFront(listHead, value);
    return;
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL){
    head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
}
void insertAfter(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->next->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
void traverseFromFront(node *listHead){
  node* head = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\t";
  while(head->next != NULL){
    head = head->next;
  }
  node *tail = head;
  while(tail != NULL){
    cout<<tail->data<<"\t";
    tail = tail->prev;
  }
  cout<<endl;
}
void searchAndDelete(node **listHead, int searchItem){
  node* head = (*listHead);
  while(head != NULL && head->data != searchItem){
    head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
    *listHead = head->next;
  }
  if(head->next != NULL){
    head->next->prev = head->prev;
  }
  if(head->prev != NULL){
    head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
int main(){
  node *head = NULL;
  insertFront(head, 5);
  insertFront(head, 6);
  insertFront(head, 7);
  insertEnd(head, 9);
  insertEnd(head, 10);
  insertAfter(head, 5, 11);
  insertBefore(head, 5, 20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head, 7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

saída

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7  6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Lista Duplamente Vinculada em Python

Abaixo segue uma lista completa. Python Implementação de uma lista duplamente encadeada usando classes para os nós e para a própria lista.

class Node:
  def __init__(self, data=None, prev=None, next=None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None
  def insertFront(self, val):
    newNode = Node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))
  def insertEnd(self, val):
    newNode = Node(data=val)
    if self.head is None:
      self.head = newNode
      print("Added {} at the end".format(val))
      return
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))
  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp is not None:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from tail:\t", end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data), end="")
      tail = tail.prev
    print()
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value, searchItem))
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value, searchItem))
  def searchAndDelete(self, searchItem):
    temp = self.head
    while temp is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == temp.data:
      self.head = temp.next
    if temp.next is not None:
      temp.next.prev = temp.prev
    if temp.prev is not None:
      temp.prev.next = temp.next
    print("Deleted Node\t{}".format(searchItem))
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

saída

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7  6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6  7
Deleted Node    7
Traversing from head:   6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6

Complexidade da lista duplamente vinculada

A complexidade temporal é geralmente dividida em três tipos: melhor caso, caso médio e pior caso.

Complexidade de tempo no melhor caso para lista duplamente vinculada:

1. A inserção no início ou no fim custa O(1) porque não é necessário percorrer a lista encadeada. Os ponteiros para o início e o fim dão acesso direto aos nós do início e do fim.
2. A remoção no início ou no final custa O(1).
3. A busca em um nó custa O(1) quando o nó alvo é o nó cabeça.

Complexidade de tempo no caso médio para lista duplamente vinculada:

1. A inserção na cabeça ou na cauda custa O(1).
2. A remoção no início ou no final custa O(1).
3. A busca em um nó tem custo O(n), pois o alvo pode estar em qualquer lugar da lista. Aqui, n é o número total de nós.

A complexidade temporal no pior caso da Lista Duplamente Encadeada é a mesma que no caso médio.

Complexidade de memória da lista duplamente vinculada

A complexidade de memória é O(n), onde n é o número total de nós. Ao implementar a lista encadeada, a memória deve ser liberada. Caso contrário, listas encadeadas maiores causam vazamentos de memória.

Aplicações de listas duplamente encadeadas

Listas duplamente encadeadas são a base de diversas estruturas de dados do mundo real, pois a travessia bidirecional simplifica muitas operações comuns.

• Cache LRU: Os caches LRU (Least-Recently-Used) usam uma lista duplamente encadeada com um mapa hash para movimentação para o início e remoção em O(1).
• Histórico do navegador: A navegação para frente e para trás percorre a lista encadeada em qualquer direção.
• Pilhas de desfazer e refazer: Editores e IDEs track versões de documentos com ponteiros anterior e seguinte.
• Deque: DoubleFilas com extremidades -inserem e desemergem de ambas as extremidades em tempo O(1).
• Listas de reprodução de música: Anterior e próximo tracOs botões K dependem dos ponteiros para frente e para trás.

Perguntas Frequentes