Continuando os posts sobre estruturas de dados, hoje vamos falar sobre linked list ou listas encadeadas.
| Algoritmo | Big O |
|---|---|
| Indexar | O(n) |
| Inserir/deletar no inicio | O(1) |
| Inserir/deletar no meio | O(n) |
| Inserir/deletar no final | O(1) |
| Busca | O(n) |
Essa estrutura de dados foi inventada em 1955-1956 por Allen Newel, Cliff Shaw e Herbert A. Simon como sua principal estrutura de dados em sua linguagem de programação chamada de Information Processing Language (IPL). IPL foi usada pelos autores para desenvolver diversos programas de inteligência artificial, incluindo Logic Theory Machine, General Problem Solver e um programa de xadrez.
Linked Lists consistem em uma lista de elementos que não estão, obrigatoriamente, alocados de forma sequencial na memória. Ao invés disso, cada elemento aponta para o próximo elemento da lista.
Podemos pensar em cada um desses elementos como um node, onde cada node contém no mínimo 2 atributos. Um para guardar o dado, como uma struct por exemplo, e um que aponta para o próximo node.
Existem 3 tipos principais de linked list.
Singly linked list ou lista encadeada simples: nesse tipo de lista, só conseguimos navegar para uma direção.
Doubly linked list ou lista duplamente encadeada: nesse tipo conseguimos navegar para duas direções.
Circular linked list ou lista encadeada circular: nessa lista, só conseguimos navegar para uma direção, porém o último node aponta para o primeiro.
Eu particularmente gosto muito dessa estrutura de dados e já utilizei ela bastante. Ela é a base para que possamos estudar, dentre outras coisas, grafos, árvores (balanceadas ou não), busca binária, filas e pilhas.
E como podemos implementar essa estrutura de dados em Go?
No inicio da próxima semana vou explicar isso em um vídeo, junto com as 5 operações básicas de uma linked list. Por isso se inscreva no nosso canal do Youtube para não ficar de fora do que está rolando por lá também!!!
Deixem suas dúvidas nos comentários.
Até a próxima!
[…] Assim como na estrutura de dados de pilha, as duas formas mais comuns de se implementar uma fila são com arrays ou listas encadeadas (linked list). […]