Data StructuresEstruturas de Dados
Data structures in programming refer to the way data is organized, stored, and manipulated in a computer's memory. They are essential for efficient data storage, retrieval, and manipulation, and they provide a means to represent relationships between data elements.
Arrays
Arrays are used to store multiple values of the same type under a single variable name, arranged in contiguous memory locations. Each element in the array is accessed by its index, which represents its position within the array.
They allow for efficient storage and retrieval of data elements and are commonly used in various programming languages for a wide range of applications, such as storing lists of items, managing data sets, and representing multi-dimensional structures.
Types of Arrays
-
One-dimensional arrays - also known as vectors or lists, are arrays with a single row or column. They are the simplest form of arrays and are often used to store a collection of values of the same data type, such as integers or characters
-
Two-dimensional arrays - on the other hand, are arrays with two dimensions, typically represented as rows and columns. They are arranged in a grid-like structure, allowing for the storage of data in rows and columns. Two-dimensional arrays are commonly used to represent matrices, tables, or grids of values, such as a spreadsheet or a game board
One-dimensional array
Two-dimensional array
It is important to remember that all of the above represents only a superficial demonstration of what arrays are.
If you want to complement what you've read, I suggest watching this video:
Linked Lists
A linear data structure consisting of a sequence of elements, called nodes, where each node contains a value and a reference (or pointer) to the next node in the sequence.
Unlike arrays, where elements are stored in contiguous memory locations, linked lists use pointers to connect nodes, allowing for dynamic memory allocation and flexible insertion and deletion operations.
Types of Linked Lists
-
Singly Linked List - each node contains a data element and a pointer to the next node in the sequence. The last node points to NULL, indicating the end of the list
-
Doubly Linked List - each node contains a data element, a pointer to the next node, and a pointer to the previous node. This allows for traversal in both forward and backward directions
-
Circular Linked List - similar to a singly linked list, but the last node points back to the first node, forming a circular structure. This can be useful for certain applications, such as representing a circular buffer
Types of Linked Lists (Tsuji, Yutaro. 2019)
Stacks
A Stack is a linear data structure, which means that the data is organized in a sequence, one after another.
They are very similar to arrays, but it is important to note that in arrays you can remove and add values wherever you'd like, whereas in stacks you can only remove and add values from one side, the top.
To understand that, think of it as a stack of coins, in order to get to any coin in the middle of the stack, you have to start from the top and remove coins one by one until you get to the one you want.
Therefore, this data structure operates on the Last In, First Out (LIFO) principle.
It is important to know that stacks are the building blocks of function calls and recursive functions. For further information, check this article on Medium.
Stack Data Structure
Trees
A hierarchical data structure composed of nodes, where each node contains a value and references (or pointers) to its child nodes.
Trees are used to represent hierarchical relationships between elements, such as the hierarchical structure of file systems, organization charts, or the structure of HTML documents. They are also fundamental for implementing various data structures and algorithms, such as binary search trees and heaps.
This guide doesn't aim to exhaustively delve into every detail of this complex topic. If you wish to learn more about the types of trees, read this article on freeCodeCamp.
Trees overview (Vijini, Mallawaarachchi. 2020)
Graphs
Graphs are a non-linear data structure consisting of a collection of nodes (vertices) and a set of edges that connect pairs of nodes. Each edge represents a relationship or connection between two vertices.
Graphs are used to represent networks of interconnected entities, such as social networks (e.g. in Facebook, each person is represented with a vertex or node and each node is a structure and contains information like personalized name, gender, or location), computer networks, transportation networks (e.g GPS systems and Google maps use graphs to find the shortest path from one destination to another), and more.
Graphs overview
There's a lot to explore when it comes to Graphs implementation and usage, if you want to further your knowledge check this article on Medium.
Hash Tables
A Hash Table is a data structure that allows you to store and retrieve values efficiently using a key-value pair mapping (it can map keys to values).
A hash table works by using a hash function to transform the key (input) into an index or address in the underlying array where the corresponding value is stored (Majeed, Ahsan. 2023).
When adding a key-value pair into the hash table, the hash function is utilized to ascertain the index where the value ought to be placed. Similarly, when retrieving a value using a key, the hash function is employed once more to locate the corresponding index and retrieve the associated value.
Hash Function (TutorialsPoint - DSA Hash Table)
As I often emphasize, this topic has way more details to explore and understand, if you wish to take a deeper dive I suggest this tutorial or this article on Medium.
Em programação, estruturas de dados são a forma como os dados são organizados, armazenados e manipulados na memória de um computador. Elas são essenciais para guardar, recuperar e manipular dados com eficiência, e oferecem um meio de representar as relações entre os elementos.
Arrays
Arrays servem para guardar vários valores do mesmo tipo sob um único nome de variável, dispostos em posições contíguas de memória. Cada elemento do array é acessado pelo seu índice, que representa a sua posição dentro do array.
Eles permitem guardar e recuperar elementos com eficiência e são muito usados em várias linguagens de programação para uma grande variedade de aplicações, como guardar listas de itens, gerenciar conjuntos de dados e representar estruturas multidimensionais.
Tipos de arrays
-
Arrays unidimensionais - também chamados de vetores ou listas, são arrays com uma única linha ou coluna. São a forma mais simples de array e costumam ser usados para guardar uma coleção de valores do mesmo tipo, como inteiros ou caracteres
-
Arrays bidimensionais - por outro lado, são arrays com duas dimensões, normalmente representadas como linhas e colunas. Eles são organizados como uma grade, o que permite guardar dados em linhas e colunas. Arrays bidimensionais são muito usados para representar matrizes, tabelas ou grades de valores, como uma planilha ou um tabuleiro de jogo
Array unidimensional
Array bidimensional
É importante lembrar que tudo isso é apenas uma demonstração superficial do que são arrays.
Se quiser complementar o que leu, sugiro assistir a este vídeo:
Listas ligadas
Uma estrutura de dados linear formada por uma sequência de elementos, chamados de nós, em que cada nó contém um valor e uma referência (ou ponteiro) para o próximo nó da sequência.
Diferentemente dos arrays, em que os elementos ficam em posições contíguas de memória, as listas ligadas usam ponteiros para conectar os nós, o que permite alocação dinâmica de memória e operações flexíveis de inserção e remoção.
Tipos de listas ligadas
-
Lista simplesmente ligada - cada nó contém um elemento de dado e um ponteiro para o próximo nó da sequência. O último nó aponta para NULL, indicando o fim da lista
-
Lista duplamente ligada - cada nó contém um elemento de dado, um ponteiro para o próximo nó e um ponteiro para o nó anterior. Isso permite percorrer a lista nos dois sentidos, para frente e para trás
-
Lista ligada circular - parecida com a lista simplesmente ligada, mas o último nó aponta de volta para o primeiro, formando uma estrutura circular. Isso pode ser útil em certas aplicações, como representar um buffer circular
Tipos de listas ligadas (Tsuji, Yutaro. 2019)
Pilhas
Uma pilha (stack) é uma estrutura de dados linear, ou seja, os dados ficam organizados em sequência, um depois do outro.
Ela é muito parecida com o array, mas é importante notar que no array você pode remover e adicionar valores onde quiser, enquanto na pilha você só pode remover e adicionar valores por um lado, o topo.
Para entender, pense numa pilha de moedas: para chegar a qualquer moeda no meio da pilha, você precisa começar pelo topo e tirar as moedas uma a uma até chegar à que quer.
Por isso, essa estrutura de dados funciona pelo princípio Last In, First Out (LIFO): o último a entrar é o primeiro a sair.
É importante saber que as pilhas são a base das chamadas de função e das funções recursivas. Para saber mais, veja este artigo no Medium.
Estrutura de dados pilha
Árvores
Uma estrutura de dados hierárquica formada por nós, em que cada nó contém um valor e referências (ou ponteiros) para os seus nós filhos.
As árvores servem para representar relações hierárquicas entre elementos, como a estrutura de um sistema de arquivos, um organograma ou a estrutura de um documento HTML. Elas também são fundamentais para implementar várias estruturas de dados e algoritmos, como árvores binárias de busca e heaps.
Este guia não pretende esgotar todos os detalhes de um tema tão complexo. Se quiser aprender mais sobre os tipos de árvore, leia este artigo no freeCodeCamp.
Visão geral de árvores (Vijini, Mallawaarachchi. 2020)
Grafos
Grafos são uma estrutura de dados não linear formada por uma coleção de nós (vértices) e um conjunto de arestas que conectam pares de nós. Cada aresta representa uma relação ou conexão entre dois vértices.
Grafos servem para representar redes de entidades interligadas, como redes sociais (por exemplo, no Facebook cada pessoa é representada por um vértice, ou nó, e cada nó é uma estrutura com informações como nome, gênero ou localização), redes de computadores, redes de transporte (por exemplo, sistemas de GPS e o Google Maps usam grafos para encontrar o caminho mais curto entre um destino e outro) e muito mais.
Visão geral de grafos
Há muito a explorar sobre a implementação e o uso de grafos. Se quiser ir além, veja este artigo no Medium.
Tabelas hash
Uma tabela hash é uma estrutura de dados que permite guardar e recuperar valores com eficiência usando um mapeamento de pares chave-valor (ela associa chaves a valores).
Uma tabela hash funciona usando uma função hash para transformar a chave (entrada) num índice ou endereço do array interno onde o valor correspondente está guardado (Majeed, Ahsan. 2023).
Ao inserir um par chave-valor na tabela, a função hash é usada para descobrir o índice em que o valor deve ser colocado. Da mesma forma, ao buscar um valor pela chave, a função hash é usada de novo para localizar o índice correspondente e recuperar o valor associado.
Função hash (TutorialsPoint - DSA Hash Table)
Como costumo reforçar, esse tema tem muito mais detalhes para explorar e entender. Se quiser se aprofundar, sugiro este tutorial ou este artigo no Medium.