Introdução
Nessa primeira parte vamos falar sobre o que é uma estrutura de dados, para que serve e sobre alguns dos tipos de estrutura de dados, array, linked list, stack e queue. Na segunda parte vou falar sobre hash table, graph e tree.
O que é uma estrutura de dados
Uma estrutura de dados é a forma de como organizamos os dados para que possamos guardá-los, acessá-los e modificá-los com frequência e eficiência.
Principais estrutura de dados
- Array
- Linked List
- Stack
- Queue
- Hash Table
- Graph
- Tree
Array
O array é um tipo de estrutura de dados básica que temos já implementado na maioria das linguagens de programação. Sua principal característica é que seu tamanho é fixo, não podemos aumentar e nem diminuir seu tamanho e o tipo de dado dos valores armazenados devem ser todos iguais. Para acessar algum valor armazenado utilizamos índices que sempre começa com 0.
Arrays são armazenados de forma contígua na memória, isso explica o fato de que não podemos aumentar ou diminuir o seu tamanho, pois caso aumentarmos o seu tamanho não saberemos se vamos conseguir usar o próximo local de memória gratuitamente.
Exemplo de um array com 1 elemento.
Exemplo de um array com 5 elementos.
Linked List
Linked list em português significa "lista ligada", basicamente esta estrutura de dados é uma lista onde cada elemento aponta para o próximo elemento e também pode apontar para o elemento anterior, isso significa que, diferente de arrays, os dados são armazenados de forma não contígua na memória, permitindo que modifiquemos o tamanho da lista.
Cada elemento pode ser chamado de node este node contem um atributo data para armazenar o valor e outro atributo para armazenar o endereço do próximo node chamado next e/ou do node anterior prev. Além disso temos também um atributo chamado head este é responsável por armazenar uma referência para o primeiro node da lista.
Singly Linked List
Em uma singly linked list, cada node possuí dois atributos, um deles é o valor que queremos armazenar na lista e o outro atributo é a referência ao próximo node da lista.
Em uma representação gráfica ele se parece com isso:
Aqui está um exemplo de uma singly linked list, com letras de 'A' até 'E' (poderia ser uma lista de compras, uma lista de livros, etc. Foi colocado letras para facilitar o exemplo). Nesse tipo de linked list o último node aponta para null, pois não tem nenhum outro valor após ele.
Implementação
Principais métodos:
-
add(data)- Para adicionar um elemento. -
remove(data)- Para remover um elemento. -
get(data)- Retornatrueoufalsecaso encontre ou não o elemento.
/*
Exemplo totalmente manual, o certo é
criar os métodos básicos para que
tudo fique dinâmico.
*/
public class SinglyLinkedList {
public Node head;
public static class Node {
public String data;
public Node next;
}
public static void main(String[] args) {
// Crio os nodes.
Node node1 = new Node("a");
Node node2 = new Node("b");
Node node3 = new Node("c");
// Coloco eles em ordem.
node1.next = node2;
node2.next = node3;
node3.next = null;
// Crio a lista e adiciono o primeiro elemento no head.
SinglyLinkedList list = new SinglyLinkedList();
list.head = node1;
}
}
Circular Singly Linked List
Este tipo de linked list é basicamente uma singly linked list só que com uma diferença, o último node em vez de apontar para null, ele aponta para o primeiro elemento da lista, por isso o nome "circular".
Implementação
Principais métodos:
-
add(data)- Para adicionar um elemento. -
remove(data)- Para remover um elemento. -
get(data)- Retornatrueoufalsecaso encontre ou não o elemento.
/*
Exemplo totalmente manual, o certo é
criar os métodos básicos para que
tudo fique dinâmico.
*/
public class CircularSinglyLinkedList {
public Node head;
public static class Node {
public String data;
public Node next;
}
public static void main(String[] args) {
// Crio os nodes.
Node node1 = new Node("a");
Node node2 = new Node("b");
Node node3 = new Node("c");
// Coloco eles em ordem.
node1.next = node2;
node2.next = node3;
node3.next = node1; // Note que este último node aponta para o primeiro.
// Crio a lista e adiciono o primeiro elemento no head.
CircularSinglyLinkedList list = new CircularSinglyLinkedList();
list.head = node1;
}
}
Doubly Linked List
Nesse tipo de linked list além de termos um campo next que aponta para o próximo node, também temos um campo prev que aponta para o node anterior. O último node aponta para null como próximo node e o primeiro node da lista aponta para null como node anterior.
Exemplo do node de uma doubly linked list:
Exemplo de uma doubly linked list com os elementos:
Implementação
Principais métodos:
-
add(data)- Para adicionar um elemento. -
remove(data)- Para remover um elemento. -
get(data)- Retornatrueoufalsecaso encontre ou não o elemento.
/*
Exemplo totalmente manual, o certo é
criar os métodos básicos para que
tudo fique dinâmico.
*/
public class DoublyLinkedList {
public Node head;
public static class Node {
public String data;
public Node prev;
public Node next;
}
public static void main(String[] args) {
// Crio os nodes.
Node node1 = new Node("a");
Node node2 = new Node("b");
Node node3 = new Node("c");
// Coloco eles em ordem.
node1.prev = null;
node1.next = node2;
node2.prev = node1;
node2.next = node3;
node3.prev = node2;
node3.next = null;
// Crio a lista e adiciono o primeiro elemento no head.
DoublyLinkedList list = new DoublyLinkedList();
list.head = node1;
}
}
Circular Doubly Linked List
Aqui o funcionamento é como a circular singly linked list, mas como estamos falando de um circular doubly linked list vamos ter o campo prev. O primeiro elemento aponta para o último elemento da lista no campo prev e o último elemento da lista aponta para o primeiro elemento de lista no campo next.
Implementação
Principais métodos:
-
add(data)- Para adicionar um elemento. -
remove(data)- Para remover um elemento. -
get(data)- Retornatrueoufalsecaso encontre ou não o elemento.
/*
Exemplo totalmente manual, o certo é
criar os métodos básicos para que
tudo fique dinâmico.
*/
public class CircularDoublyLinkedList {
public Node head;
public static class Node {
public String data;
public Node next;
}
public static void main(String[] args) {
// Crio os nodes.
Node node1 = new Node("a");
Node node2 = new Node("b");
Node node3 = new Node("c");
// Coloco eles em ordem.
node1.prev = node3; // Note que este primeiro node aponta (prev) para o último.
node1.next = node2;
node2.prev = node1;
node2.next = node3;
node3.prev = node2;
node3.next = node1; // Note que este último node aponta (next) para o primeiro.
// Crio a lista e adiciono o primeiro elemento no head.
CircularDoublyLinkedList list = new CircularDoublyLinkedList();
list.head = node1;
}
}
Stack
Stack em português significa "pilha", imagine essa estrutura de dados como uma pilha de livros ou como uma pilha de pratos. Essa Estrutura de Dados tem um princípio chamado de LIFO (Last In First Out/Último a Entrar Primeiro a Sair).
Vamos com um exemplo simples, imagine que estamos lavando pratos e a medida que os pratos são lavados vamos empilhando eles, quando terminamos temos que guardá-los e aqui o princípio LIFO entra em ação, o último prato empilhado será o primeiro prato a sair.
Implementação
Principais métodos:
-
push(data)- Para adicionar um elemento no topo. -
pop()- Para remover o elemento do top. -
isEmpty()- Para verificar se a stack está vazia. -
peek()- Retorna o elemento do topo da stack.
O funcionamento de uma Stack é da seguinte maneira:
Para implementar um Stack podemos usar dois tipos de abordagens em relação à forma de armazenamento dos dados, a primeira é utilizando um node como em uma linked list para armazenar os dados com os ponteiros para os próximos elementos, a segunda forma é utilizando um array, tudo depende de como a Stack irá funcionar, caso ela precise mudar de tamanho a abordagem com node vai funcionar melhor, caso não mude de tamanho, utilizando array vai funcionar muito bem.
Um ponto importante é que caso utilize a abordagem utilizando node em vez de termos um atributo head como em uma linked list que aponta para o primeiro elemento da lista, vamos ter um chamado top que irá apontar para o último elemento adicionado na pilha.
Aqui está um exemplo de uma implementação utilizando node com seu funcionamento totalmente manual:
/*
Exemplo totalmente manual, o certo é
criar os métodos básicos para que
tudo fique dinâmico.
*/
public class Stack {
public Node top;
public static class Node {
public String data;
public String next;
}
public static void main(String[] args) {
// Crio 3 nodes.
Node node1 = new Node("a");
Node node2 = new Node("b");
Node node3 = new Node("c");
// Coloco eles em ordem.
node3.next = node2;
node2.next = node1;
node1.next = null;
// Crio a stack adicionando o último node no top.
Stack stack = new Stack();
stack.top = node3;
}
}
Queue
Queue em português significa "fila", você pode imaginar esta estrutura de dados como uma fila de pessoas para entrar em um show ou qualquer outra fila. Essa estrutura de dados segue princípio FIFO (First In First Out/Primeiro a Chegar Primeiro a Sair), ou seja, a primeira pessoa a entrar em uma fila será a primeira a sair dela.
Implementação
Principais métodos:
-
enqueue(data)- Adiciona um elemento no final da fila. -
dequeue()- Remove o primeiro elemento da fila. -
isEmpty()- Retornatrueoufalsepara caso a fila esteja vazia ou não.
O funcionamento de uma queue é da seguinte maneira:
Para implementar uma queue podemos usar duas abordagens para a foram de armazenamento dos dados, uma utilizando node para os elementos assim como em uma linked list ou podemos fazer a implementação utilizando array. Caso sua queue mude de tamanho pode ser mais interessante implementar utilizando node, mas caso não mude de tamanho, com array vai se sair muito bem.
Para implementar utilizando nodevamos ter dois atributos importantes, o front que aponta para o primeiro elemento da fila e o rear que aponta para o último elemento da fila. Aqui está um exemplo:
/*
Exemplo totalmente manual, o certo é
criar os métodos básicos para que
tudo fique dinâmico.
*/
public class Queue {
public Node front;
public Node rear;
public static class Node {
public String data;
public Node prev;
}
public static void main(String[] args) {
// Crio 3 nodes.
Node node1 = new Node("a");
Node node2 = new Node("b");
Node node3 = new Node("c");
// Coloco eles em ordem.
node1.prev = node2;
node2.prev = node3;
node3.prev = null;
// Crio a stack.
Queue queue = new Queue();
queue.front = node1; // Adiciono o primeiro node no front.
queue.rear = node3; // Adiciono o último node no front.
}
}
Conclusão
Nesse artigo vimos o que são estrutura de dados e alguns dos principais tipos, um ponto importante é que as implementações estão totalmente de forma manual, isto é, temos que criar cada node (nos tipos de precisam) e dependendo da quantidade de dados isso se torna inviável. O correto é criar métodos que vão automatizar todo o processo da criação da estrutura de dados e métodos para adicionar, remover, alterar, etc.
Top comments (0)