Estrutura de Dados #2 - Listas Encadeadas e Árvores.
No post anterior(Estrutura de Dados #1) foi abordado os tipos principais de estrutura de dados. Neste post será mostrados outros tipos que também são muito importantes no estudo de Algoritmo.
Listas Encadeadas:
Lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por uma sequência de nodos ou células que contém seus dados e também um ou dois ponteiros ("links") que apontam para o nodo anterior ou posterior. As listas encadeadas são úteis para representar conjuntos dinâmicos de dados. Ou seja, você não precisa definir um tamanho máximo para uma lista encadeada.
O início aponta para um ponteiro que inicia a estrutura ou o primeiro nó da lista e no final o ponteiro aponta para um Null indicando o fim da lista.
Árvores:
Árvore é uma estrutura de dados que herda as características das topologias em árvore. Conceptualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica. Este tipo de estruturas de dados é muito utilizada em banco de dados e sistema de arquivos.
As árvores consistem de Raiz, Nodo e Folhas.
Raiz: um nodo sem pai
Nodo: um elemento qualquer
Folha: um nodo sem filhos
Referências:
https://medium.com/aprendacpp/criando-uma-lista-encadeada-em-c-17e7f5692f36
https://www.caelum.com.br/apostila-java-estrutura-dados/
Listas Encadeadas:
Lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por uma sequência de nodos ou células que contém seus dados e também um ou dois ponteiros ("links") que apontam para o nodo anterior ou posterior. As listas encadeadas são úteis para representar conjuntos dinâmicos de dados. Ou seja, você não precisa definir um tamanho máximo para uma lista encadeada.
O início aponta para um ponteiro que inicia a estrutura ou o primeiro nó da lista e no final o ponteiro aponta para um Null indicando o fim da lista.
Árvores:
Árvore é uma estrutura de dados que herda as características das topologias em árvore. Conceptualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica. Este tipo de estruturas de dados é muito utilizada em banco de dados e sistema de arquivos.
Raiz: um nodo sem pai
Nodo: um elemento qualquer
Folha: um nodo sem filhos
https://medium.com/aprendacpp/criando-uma-lista-encadeada-em-c-17e7f5692f36
https://www.caelum.com.br/apostila-java-estrutura-dados/
As listas encadeadas também podem ser implementadas com vetores que são estáticos, diferentemente de utilizar ponteiros. Mas, nem sempre, há como saber se o tamanho de um vetor já definido, ocupará menos espaço de vários ponteiros que estão sendo alocados na memória porque nem sempre será utilizado a função "free" como na liguagem C. Por isso, é bom estudar os tipos de casos para cada algoritmo para ser o mais otimizado possível.
ResponderExcluirBoa postagem!
Muito obrigado!
ExcluirÓtimo post. Só pra confirmar, então na imagem sobre árvores em estrutura de dados que você postou os números 5, 11, 2, 4 seriam folhas enquanto o 2 seria raiz?
ResponderExcluirExato!
Excluir