Lista duplamente vinculada: C++, Python (Exemplo de código)
Sarah Chen
O que é uma lista duplamente vinculada?
Em uma lista duplamente vinculada, cada nó possui links para o nó anterior e para o próximo. Cada nó consiste em três elementos: um contém os dados e outros dois são os ponteiros do nó seguinte e do nó anterior. Esses dois ponteiros nos ajudam a avançar ou retroceder a partir de um nó específico.
Aqui está a estrutura básica da lista duplamente vinculada.
Cada lista vinculada possui um nó inicial e um nó final. O nó principal não possui um nó “anterior” (ponteiro anterior) e o nó final não possui um nó “próximo”.
Aqui estão alguns termos importantes para uma lista duplamente vinculada:
- 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ó. “Dados” podem conter outros Estruturas de dados dentro dele. Por exemplo, string, dicionário, conjunto, hashmap, etc. podem ser armazenados em “Dados”.
Aqui está a estrutura básica de um único nó na lista duplamente vinculada:
Operações de lista duplamente vinculada
As operações de uma lista duplamente vinculada incluem adicionar e excluir nós, inserir e remover nós e percorrer a lista vinculada de cima para baixo.
Aqui está a lista de operações que podemos implementar usando a lista duplamente vinculada:
- Inserção na frente
- Inserção na cauda ou ú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
Veremos a implementação e o pseudocódigo de todas as operações acima.
Inserção na frente da lista duplamente vinculada
A inserção na frente significa que precisamos criar um nó na lista vinculada e colocá-lo no início da lista vinculada.
Por exemplo, existe um determinado nó “15”. Precisamos adicionar isso ao nó principal.
Aqui estão duas condições importantes ao fazer esta operação:
- O novo nó será o nó principal se não houver nenhum nó na lista duplamente vinculada.
- Se já existir um nó principal, o nó anterior será substituído pelo novo nó.
Aqui está 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 final da lista duplamente vinculada
“Inserção no final” significa que criaremos um nó na lista vinculada e o colocaremos no final.
Para fazer isso, podemos usar dois métodos:
- Método 1: Comece a percorrer a partir do início da lista duplamente vinculada até que o “próximo” se torne nulo. Em seguida, vincule o novo nó ao “próximo”.
- Método 2: Pegue o último nó da lista duplamente vinculada. Então, o “próximo” nó do último nó será vinculado ao novo nó. Agora, o novo nó será o nó final.
Aqui está 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: then ListHead = ListHead.next newNode.prev = ListHead ListHead.next = newNode return ListHead
Inserção após um nó
Digamos que temos uma lista duplamente vinculada como a seguinte:
Queremos inserir um determinado nó que será vinculado após o nó, que possui o valor “12”.
Aqui estão as etapas para isso:
Passo 1) Percorra da cabeça até o último nó. Verifique qual nó tem o valor “12”.
Passo 2) Crie um novo nó e atribua-o como o próximo ponteiro do nó “12”. O “próximo” nó do novo nó será 15.
Aqui está o pseudocódigo para inserir um nó após um nó em uma lista duplamente vinculada:
function insertAfter(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.value is not equal searchItem then List = ListHead.next List = List.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
Inserção antes de um nó
Esta operação é mais parecida com a “inserção após um nó”. Precisamos procurar o valor de um nó específico para fazer isso. Em seguida, criaremos um novo nó e o inseriremos antes do nó pesquisado.
Digamos que queremos inserir um determinado nó “15” antes do nó “12”. Então aqui estão as etapas para fazer isso:
Passo 1) Percorra a lista vinculada do nó principal ao nó final.
Passo 2) Verifique se o próximo ponteiro do nó atual tem o valor “12” ou não.
Passo 3) Insira o novo nó como o “próximo” nó do nó atual.
Aqui está o pseudocódigo para inserir um nó antes de um nó em uma lista duplamente vinculada:
function insertBefore(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.next.value is not equal searchItem then List = ListHead.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
Exclua o topo da lista duplamente vinculada
O nó principal na lista duplamente vinculada que não possui nenhum nó anterior. Portanto, o próximo ponteiro será o novo nó principal se quisermos excluir o nó principal. Também precisamos liberar a memória ocupada por um nó ao excluir um nó.
Aqui estão as etapas para excluir o nó principal:
Passo 1) Atribua uma variável ao nó principal atual.
Passo 2) Visite o nó “próximo” do nó principal atual e torne o nó “anterior” (ponteiro anterior) como ''NULL”. Isso significa que estamos desconectando o segundo nó do primeiro nó.
Passo 3) Libere a memória ocupada pelo nó principal anterior.
Aqui está o pseudocódigo para excluir o cabeçalho de uma lista duplamente vinculada:
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
É necessário deletar a memória alocada após realizar qualquer tipo de operação de deleção. Caso contrário, durante todo o tempo de execução do programa, a memória do bloco excluído permanecerá ocupada. Nenhum outro aplicativo pode usar esse segmento de memória.
Exclua o final da lista duplamente vinculada.
Esta operação é semelhante à exclusão da cabeça. Aqui, em vez da cabeça, precisamos deletar a cauda. Para identificar um nó como nó final, devemos verificar se o próximo ponteiro ou o próximo nó é nulo ou não. Depois de deletar a cauda, precisamos liberar memória.
Esta operação também é conhecida como “exclusão por trás”.
Aqui estão as etapas para fazer isso:
Passo 1) Percorra até o nó final da lista duplamente vinculada.
Passo 2) Atribua uma variável ou ponteiro ao nó final.
Passo 3) Torne o “próximo” nó como NULL e libere a memória do nó final.
Aqui está o pseudocódigo para excluir o nó final:
function DeleteTail( ListHead ): head = ListHead while ListHead.next is not NULL: ListHead = ListHead.next Tail = ListHead.next ListHead.next = NULL free memory( Tail ) return head
Pesquise e exclua um nó da lista duplamente vinculada
Esta operação nos permite pesquisar dados de um nó específico e excluí-lo. Precisamos realizar uma pesquisa linear, pois a lista vinculada é uma estrutura de dados linear. Após a exclusão, também precisamos liberar memória.
Aqui estão as etapas para pesquisar e excluir um nó na lista duplamente vinculada:
Passo 1) Percorra a lista encadeada desde o início até que o valor do nó seja igual ao item de pesquisa.
Passo 2) Atribua uma variável “deleteNode” ao nó correspondente.
Passo 3) Atribua o nó anterior de “deleteNode” ao próximo nó.
Passo 4) Libere a memória do “deleteNode”
Aqui está o pseudocódigo para pesquisar e excluir um nó de uma lista vinculada:
function SearchAndDelete(ListHead, searchItem): head = ListHead while ListHead.next.value not equals searchItem: head = head.next deleteNode = head.next head.next = head.next.next head.next.prev = head deleteNode.next, deleteNode.next = NULL free memory(deleteNode) return ListHead
Percorrer uma lista duplamente vinculada de frente
Para percorrer a partir do nó principal e iterar no próximo nó até encontrar “NULL”. Ao percorrer cada nó, podemos imprimir o valor do nó. Aqui estão as etapas para atravessar pela frente (direção para frente):
Passo 1) Atribua um ponteiro ou variável ao nó principal atual.
Passo 2) Itere para o próximo nó do cabeçalho 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 vinculada pela frente:
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
Aqui, a devolução não é obrigatória. Mas é uma boa prática retornar o nó principal após as operações.
Percorra uma lista duplamente vinculada de trás para frente
Esta operação é o inverso da poligonal pela frente. A abordagem é a mesma com uma pequena diferença. Devemos percorrer até o nó final e, em seguida, percorrer do nó final até o nó frontal.
Aqui estão as etapas para percorrer uma lista duplamente vinculada desde o final:
Passo 1) Atravesse até chegar ao nó final.
Passo 2) A partir do nó final, percorreremos até obtermos o nó anterior como “NULL”. O “prev” (ponteiro anterior) será nulo para o nó principal
Passo 3) A cada iteração, imprimiremos os dados do nó.
Aqui está o pseudocódigo para percorrer de trás:
function traverseFromBack(ListHead): head = ListHead while head not equals NULL: head = head.next tail = head while tail not equal to NULL: print tail.value tail = tail.prev return ListHead
Diferença entre lista vinculada simples e duplamente
A principal diferença entre a lista individual e duplamente vinculada é o número de links.
Aqui está a diferença entre os nós de uma lista vinculada individualmente e a estrutura de nós da lista duplamente vinculada:
| Campo | Lista encadeada individualmente | Lista duplamente vinculada |
|---|---|---|
| Estrutura | Lista encadeada individualmente tem um campo de dados e um link para o próximo nó. | A lista duplamente vinculada possui um campo de dados e dois links. Um para o nó anterior e outro para o próximo nó. |
| Traversal | Ele só pode percorrer da cabeça à cauda. | Ele pode percorrer tanto para frente quanto para trás. |
| Memória | Ocupa menos memória. | Ocupa mais memória do que uma lista vinculada individualmente. |
| Acessibilidade | Listas vinculadas individualmente são menos eficientes porque usam apenas um link para o próximo nó. Não há link para o nó anterior. | As listas duplamente vinculadas são mais eficientes do que as listas vinculadas individualmente. |
Lista Duplamente Vinculada em C++
#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);
}
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 = new 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 = new node();
head = listHead;
cout<<"Traversal from head:\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 = new node();
head = (*listHead);
while(head->next!=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;
return;
}
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 Aded 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 head: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6
Lista Duplamente Vinculada em Python
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.insertFront(val)
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:
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 is not 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 is not 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.next is not None and temp.data is not searchItem:
temp = temp.next
if self.head is None or temp is None:
return
if self.head.data is 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))
return
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
Geralmente, a complexidade do tempo é dividida em três tipos.
Eles são:
- Melhor Case
- Caso Médio
- Pior caso
Complexidade de tempo no melhor caso para lista duplamente vinculada:
- A inserção na cabeça ou na cauda custará O(1). Porque não precisamos percorrer a lista vinculada. O ponteiro inicial e final podem nos dar acesso ao nó principal e final com complexidade de tempo O (1).
- A exclusão no início ou no final custará O(1).
- A pesquisa de um nó terá a complexidade de tempo de O(1). Porque o nó de destino pode ser o nó principal.
Complexidade de tempo no caso médio para lista duplamente vinculada:
- A inserção na cabeça ou na cauda terá a complexidade de tempo do custo O(1).
- A exclusão no início ou no final terá a complexidade de tempo do custo O(1).
- A pesquisa de um nó terá a complexidade de tempo de O(n). Porque o item de pesquisa pode residir em qualquer lugar da lista vinculada. Aqui, “n” é o nó total presente na lista vinculada.
A complexidade de tempo do pior caso da lista duplamente vinculada será a mesma do caso médio.
Complexidade de memória da lista duplamente vinculada
A complexidade da memória é O(n), onde “n” é o número total de nós. Ao implementar a lista vinculada, devemos liberar a memória que usamos. Caso contrário, para uma lista vinculada maior, causará vazamento de memória.
Resumo
- Uma lista vinculada é um tipo de estrutura de dados linear, uma coleção de dados representados de maneira linear.
- Uma lista duplamente vinculada é um tipo de lista vinculada em que um nó possui links com o nó anterior e o próximo.
- A lista duplamente vinculada contém todas as operações como adicionar um nó, excluir um nó, inserir um nó antes ou depois de outro nó e percorrer a lista vinculada do início ao fim.
- A lista duplamente vinculada possui um campo de dados e dois links. Um para o nó anterior e outro para o próximo nó.
- Complexidade da lista duplamente encadeada Melhor Caso, Caso médio
- E o pior caso.
