Lista ligada
Última atualização
Uma lista ligada armazena uma sequência como uma cadeia de nós, onde cada nó guarda um valor e um ponteiro para o próximo nó. Ao contrário de um array, os nós não são contíguos na memória: você segue os ponteiros next para percorrer a lista. Pressione reproduzir acima para ver nós serem ligados no início e no fim, um valor ser buscado percorrendo a cadeia e um nó ser removido reconectando um ponteiro.
Inserir ou remover no início é O(1) porque você apenas reaponta a cabeça. Alcançar uma posição no meio ou no fim é O(n) porque você precisa percorrer até lá primeiro. Esse compromisso -extremidades baratas, sem acesso aleatório- é o que distingue uma lista ligada de um array.
Complexidade de tempo
| Operação | Complexidade | Notas |
|---|---|---|
| Inserir no início | O(1) | Reapontar a cabeça |
| Inserir no fim | O(n) | Percorrer até o fim primeiro (O(1) com um ponteiro para o fim) |
| Buscar | O(n) | Seguir os ponteiros next |
| Remover a cabeça | O(1) | Reapontar a cabeça para além dela |
| Acesso por índice | O(n) | Sem acesso aleatório |
Lista ligada vs array
| Aspecto | Lista ligada | Array |
|---|---|---|
| Memória | Nós espalhados + ponteiros | Bloco contíguo |
| Acesso aleatório | O(n) | O(1) |
| Inserir/remover no início | O(1) | O(n) (deslocamento) |
| Amigabilidade com a cache | Ruim | Boa |
Exemplo resolvido
Construir a lista [10, 20], prepender 5 e depois remover 20:
| Passo | Estrutura | Ação |
|---|---|---|
| Início | head -> null | Lista vazia |
| Inserir no início 10 | head -> 10 -> null | Reapontar a cabeça para um novo nó cujo next é a cabeça anterior (null) |
| Inserir no fim 20 | head -> 10 -> 20 -> null | Percorrer até o nó 10, definir seu next para um novo nó 20 |
| Inserir no início 5 | head -> 5 -> 10 -> 20 -> null | O novo nó 5 aponta para a antiga cabeça 10; a cabeça agora aponta para 5 |
| Remover 20 | head -> 5 -> 10 -> null | Percorrer até 10, mudar seu next de 20 para null; o nó 20 fica desligado |
Quando usar uma lista ligada
| Use quando | Evite quando |
|---|---|
| Você insere ou remove nas extremidades (ou em um nó que já possui) muito mais do que indexa | Você precisa de acesso aleatório rápido por posição (indexação O(1)) |
| O tamanho muda muito e você não quer custo de redimensionar/copiar | Você percorre laços apertados onde a localidade de cache domina o desempenho |
| Você está construindo uma fila, uma pilha ou uma lista de adjacência | A memória é escassa: cada nó paga um ponteiro extra por elemento |
| Você precisa de referências estáveis a nós que sobrevivem a inserções em outros lugares | Você principalmente lê e raramente modifica, então um array é mais simples e rápido |
Código de Linked List
Uma implementação limpa e executável de 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 Linked List em Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)Código de Linked List em JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Código de Linked List em Java
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}Código de Linked List em C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}Código de Linked List em C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}Perguntas frequentes sobre listas ligadas
Qual é a diferença entre uma lista ligada e um array?
Um array armazena os elementos em um único bloco contíguo, dando acesso aleatório
O(1) mas inserções/remoções O(n) que deslocam elementos. Uma lista ligada armazena nós em qualquer lugar da memória conectados por ponteiros, dando inserções/remoções O(1) em uma posição conhecida mas acesso O(n) já que você precisa percorrer a cadeia.Quando devo usar uma lista ligada?
As listas ligadas brilham quando você insere ou remove frequentemente nas extremidades (ou em um nó do qual já tem uma referência) e raramente precisa de acesso aleatório, por exemplo filas, pilhas, listas de adjacência e caches LRU. Se você precisa de acesso indexado rápido, um array ou array dinâmico costuma ser melhor.
Qual é a complexidade de tempo de uma lista ligada?
Inserir ou remover na cabeça é
O(1). Buscar, ou alcançar o fim sem um ponteiro para o fim, é O(n) porque você segue os ponteiros next um por um. Não há acesso aleatório O(1): indexar em uma lista ligada é O(n).Qual é a diferença entre uma lista simplesmente ligada e uma duplamente ligada?
Uma lista simplesmente ligada armazena apenas um ponteiro
next por nó, então você pode percorrer em uma direção e remover um nó requer uma referência ao seu predecessor. Uma lista duplamente ligada adiciona um ponteiro prev, permitindo o percurso para trás e a remoção O(1) de um nó que você já possui, ao custo de um ponteiro extra por nó e mais gerenciamento em cada inserção e remoção.Por que inserir no fim é O(n) se inserir no início é O(1)?
Inserir no início apenas reconecta o ponteiro
head, que é trabalho constante. Alcançar o fim significa seguir os ponteiros next da cabeça até a extremidade, o que é O(n). Manter um ponteiro tail separado torna a inserção no fim também O(1), por isso as listas do mundo real muitas vezes rastreiam ambas as extremidades.As listas ligadas têm inserção O(1) em todos os lugares?
Não, esse é um equívoco comum. A inserção em si é
O(1) apenas quando você já possui um ponteiro para o nó após o qual insere. Encontrar essa posição por valor ou índice ainda custa O(n) porque você precisa percorrer a cadeia para chegar lá.Recursos relacionados
Mais visualizações
