Lista duplamente ligada
Última atualização
Uma lista duplamente ligada é uma lista ligada em que cada nó guarda dois ponteiros: next (para o nó seguinte) e prev (para o anterior). Esse elo para trás adicional permite percorrer em ambas as direções e remover um nó em O(1) quando você já tem uma referência a ele, porque é possível alcançar o predecessor diretamente em vez de caminhar desde a cabeça. Pressione reproduzir acima para ver os nós ligarem e religarem nos dois sentidos.
O custo é um ponteiro adicional por nó e mais gestão: cada inserção e remoção deve atualizar tanto next quanto prev nos vizinhos. É a estrutura por trás de muitas filas duplas (deques) e caches LRU, onde a remoção rápida por ambas as extremidades importa.
Complexidade temporal
| Operação | Complexidade | Notas |
|---|---|---|
| Inserir na cabeça/cauda | O(1) | Com ponteiros para cabeça e cauda |
| Remover um nó conhecido | O(1) | Alcança prev diretamente, sem percorrer |
| Busca | O(n) | Ainda é uma varredura linear |
| Acesso por índice | O(n) | Sem acesso aleatório |
Lista simplesmente ligada vs duplamente ligada
| Aspecto | Simples | Dupla |
|---|---|---|
| Ponteiros por nó | 1 (next) | 2 (next + prev) |
| Percorrer para trás | Não | Sim |
| Remover um nó conhecido | O(n) (achar prev) | O(1) |
| Sobrecarga de memória | Menor | Maior |
Exemplo resolvido
Construindo [10, 20, 30] acrescentando ao final e depois removendo o nó 20:
| Passo | Estrutura | Ação |
|---|---|---|
| Início | null | Lista vazia: head e tail são ambos null |
| Acrescentar 10 | 10 | Primeiro nó; head e tail apontam para ele, prev = next = null |
| Acrescentar 20 | 10 <-> 20 | Define 10.next = 20 e 20.prev = 10; tail = 20 |
| Acrescentar 30 | 10 <-> 20 <-> 30 | Define 20.next = 30 e 30.prev = 20; tail = 30 |
| Remover 20 | 10 <-> 30 | Usando 20.prev e 20.next: define 10.next = 30 e 30.prev = 10 em O(1) |
Quando usar uma lista duplamente ligada
| Use quando | Evite quando |
|---|---|
| Você precisa percorrer ou emendar em ambas as direções | Você só avança para frente: uma lista simples é mais leve |
Você remove nós arbitrários dos quais já tem referência (O(1)) | Você geralmente indexa por posição: use um array para acesso O(1) |
| Você implementa um deque, cache LRU ou histórico de desfazer | A memória é escassa: o ponteiro prev adicional dobra a sobrecarga de elos |
| Inserções e remoções ocorrem com frequência em ambas as extremidades | Os dados são pequenos e mudam pouco: copiar arrays é mais barato |
Código de Doubly Linked List
Uma implementação limpa e executável de Doubly Linked List em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Doubly Linked List em Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.prev = None5 self.next = None6
7
8class DoublyLinkedList:9 def __init__(self):10 self.head = None11 self.tail = None12
13 def append(self, value):14 node = Node(value)15 if self.tail is None:16 self.head = self.tail = node17 return18 # Wire both directions: old tail <-> new node19 node.prev = self.tail20 self.tail.next = node21 self.tail = node22
23 def prepend(self, value):24 node = Node(value)25 if self.head is None:26 self.head = self.tail = node27 return28 node.next = self.head29 self.head.prev = node30 self.head = node31
32 def forward(self):33 values, current = [], self.head34 while current:35 values.append(current.value)36 current = current.next37 return values38
39 def backward(self):40 values, current = [], self.tail41 while current:42 values.append(current.value)43 current = current.prev44 return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49 lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())Código de Doubly Linked List em JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.prev = null;5 this.next = null;6 }7}8
9class DoublyLinkedList {10 constructor() {11 this.head = null;12 this.tail = null;13 }14
15 // Tail pointer makes append O(1)16 append(value) {17 const node = new Node(value);18 if (!this.tail) {19 this.head = node;20 this.tail = node;21 return;22 }23 node.prev = this.tail;24 this.tail.next = node;25 this.tail = node;26 }27
28 forward() {29 const out = [];30 for (let n = this.head; n; n = n.next) out.push(n.value);31 return out;32 }33
34 backward() {35 const out = [];36 for (let n = this.tail; n; n = n.prev) out.push(n.value);37 return out;38 }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));Código de Doubly Linked List em Java
Java
1public class Main {2 static class Node {3 int value;4 Node prev, next;5 Node(int value) { this.value = value; }6 }7
8 static Node head, tail;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = tail = node; return; }13 node.prev = tail;14 tail.next = node;15 tail = node;16 }17
18 // Unlink in O(1) once found: fix both neighbor pointers19 static void delete(int value) {20 for (Node cur = head; cur != null; cur = cur.next) {21 if (cur.value != value) continue;22 if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23 if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24 return;25 }26 }27
28 public static void main(String[] args) {29 append(1);30 append(2);31 append(3);32 append(4);33
34 StringBuilder forward = new StringBuilder("Forward:");35 for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36 System.out.println(forward);37
38 StringBuilder backward = new StringBuilder("Backward:");39 for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40 System.out.println(backward);41
42 delete(3);43 StringBuilder after = new StringBuilder("After delete 3:");44 for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45 System.out.println(after);46 }47}Código de Doubly Linked List em C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* prev = nullptr;6 Node* next = nullptr;7 explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11 Node* head = nullptr;12 Node* tail = nullptr;13
14 void append(int value) {15 Node* node = new Node(value);16 if (tail == nullptr) {17 head = tail = node;18 return;19 }20 node->prev = tail; // link both directions21 tail->next = node;22 tail = node;23 }24
25 void prepend(int value) {26 Node* node = new Node(value);27 if (head == nullptr) {28 head = tail = node;29 return;30 }31 node->next = head;32 head->prev = node;33 head = node;34 }35
36 void printForward() const {37 for (Node* cur = head; cur != nullptr; cur = cur->next) {38 std::cout << cur->value << " <-> ";39 }40 std::cout << "null\n";41 }42
43 void printBackward() const {44 for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45 std::cout << cur->value << " <-> ";46 }47 std::cout << "null\n";48 }49};50
51int main() {52 DoublyLinkedList list;53 for (int value : {10, 20, 30}) list.append(value);54 list.prepend(5);55 std::cout << "Forward: ";56 list.printForward();57 std::cout << "Backward: ";58 list.printBackward();59 return 0;60}Código de Doubly Linked List em C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* prev;7 struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14 Node* n = calloc(1, sizeof(Node));15 n->value = value;16 return n;17}18
19void append(int value) {20 Node* node = newNode(value);21 if (tail == NULL) {22 head = tail = node;23 return;24 }25 node->prev = tail; // link both directions26 tail->next = node;27 tail = node;28}29
30void prepend(int value) {31 Node* node = newNode(value);32 if (head == NULL) {33 head = tail = node;34 return;35 }36 node->next = head;37 head->prev = node;38 head = node;39}40
41void printForward(void) {42 for (Node* cur = head; cur != NULL; cur = cur->next) {43 printf("%d <-> ", cur->value);44 }45 printf("NULL\n");46}47
48void printBackward(void) {49 for (Node* cur = tail; cur != NULL; cur = cur->prev) {50 printf("%d <-> ", cur->value);51 }52 printf("NULL\n");53}54
55int main(void) {56 int values[] = {10, 20, 30};57 for (int i = 0; i < 3; i++) append(values[i]);58 prepend(5);59 printf("Forward: ");60 printForward();61 printf("Backward: ");62 printBackward();63 return 0;64}Perguntas frequentes sobre listas duplamente ligadas
Qual é a diferença entre uma lista simplesmente ligada e uma duplamente ligada?
Uma lista simplesmente ligada tem um ponteiro por nó (
next), então você só pode avançar. Uma lista duplamente ligada adiciona um ponteiro prev, permitindo percorrer para trás e remover um nó do qual você tem referência em O(1), ao custo de um ponteiro adicional por nó e de atualizar dois elos a cada mudança.Quando uma lista duplamente ligada compensa a memória adicional?
Quando você precisa de travessia para trás ou remoção em
O(1) de nós arbitrários que já referencia: os casos clássicos são filas duplas (deques) e caches LRU, onde as entradas são movidas e removidas por ambas as extremidades com frequência.Por que uma lista duplamente ligada consegue remover um nó em O(1)?
Para remover um nó é preciso conectar seu predecessor ao seu sucessor. Em uma lista simplesmente ligada você teria que percorrer desde a cabeça para achar o predecessor (
O(n)); em uma lista duplamente ligada o ponteiro prev do nó dá o predecessor diretamente, então a reconexão é O(1).Lista duplamente ligada vs array: qual devo usar?
Use um array quando precisa de acesso
O(1) por índice e iteração eficiente em cache, e quando as inserções ocorrem principalmente no final. Use uma lista duplamente ligada quando insere ou remove com frequência no meio ou nas duas extremidades com uma referência de nó, pois isso é O(1) versus o deslocamento O(n) de um array. Arrays vencem em memória e localidade; a lista vence em edições estruturais.O que é um nó sentinela em uma lista duplamente ligada?
Um nó sentinela (ou fictício) é um marcador que fica antes da cabeça e/ou depois da cauda para que a lista nunca esteja de fato vazia. Ele elimina as verificações de
null para head, tail e as inserções/remoções nas bordas, deixando toda operação seguir o mesmo caminho de reconexão. Muitas implementações de cache LRU em produção usam dois sentinelas para não tratar as extremidades como casos especiais.Qual é o erro mais comum ao remover de uma lista duplamente ligada?
Esquecer de atualizar
head ou tail ao remover o primeiro ou o último nó, o que deixa um ponteiro pendente para um nó liberado. Verifique sempre se node.prev é null (atualize head) ou se node.next é null (atualize tail) antes de reconectar os vizinhos.Recursos relacionados
Mais visualizações
