Conhecendo estruturas de dados: Linked List

Continuando os posts sobre estruturas de dados, hoje vamos falar sobre linked list ou listas encadeadas.

AlgoritmoBig O
IndexarO(n)
Inserir/deletar no inicioO(1)
Inserir/deletar no meioO(n)
Inserir/deletar no finalO(1)
BuscaO(n)
Big O de uma linked list

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.

lista encadeada simples

Doubly linked list ou lista duplamente encadeada: nesse tipo conseguimos navegar para duas direções.

lista duplamente encadeada

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.

lista encadeada circular

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!


Subscreva

Fique por dentro de tudo o que acontece no mundo Go.

Um comentário sobre “Conhecendo estruturas de dados: Linked List

Deixe uma resposta