Estruturas de Dados
Neste capítulo cobriremos as principais estruturas de dados usadas em programação, fornecendo exemplos de uso de cada uma delas. Explicaremos em detalhes arranjos, listas, pilhas, filas, árvores, e heaps.
Grafos não serão explicados aqui, pois há um capítulo inteiro dedicado a algoritmos envolvendo essa estrutura de dados. Grande parte deste capítulo é baseada no capítulo sobre estruturas de dados do livro "Introduction to Algorithms: A Creative Approach" escrito por Udi Manber (excelente livro, diga-se de passagem).
Grosso modo, estruturas de dados podem ser classificadas em dois grupos:
-
Estruturas contíguas: são estruturas compostas de blocos contíguos de memória. Como exemplos de estrutura de dados contíguas, podemos citar arranjos, matrizes (arranjos multi-dimensionais), heaps, e tabelas hash.
-
Estruturas ligadas (encadeadas): são estruturas compostas de blocos distintos (e possivelmente não contíguos) de memória. Esses blocos são ligados (encadeados) por apontadores (ponteiros). Como exemplos de estruturas de dados encadeadas, podemos citar listas encadeadas, árvores, e grafos (se representados por meio de listas de adjacência).
Em geral, quando falamos de uma estrutura de dados, estamos falando nas operações que essa estrutura nos permite realizar, bem como da complexidade assintótica dessas operações. A escolha da estrutura certa depende das operações que seu programa executará mais frequentemente.
Em geral, o objetivo é escolher uma estrutura de dados que minimize o custo das operações mais frequentes. Ao longo deste capítulo, falaremos de várias estruturas de dados, como elas são organizadas na memória, das operações que elas nos permitem realizar, e do custo computacional dessas operações.
Playground
# Use este espaço para praticar o que você aprendeu nesta seção.
# Basta digitar o código no espaço abaixo e clicar 'run'.