Estrutura de Dados - Parte 1
Tags: datastructures, java, algorithms
Published: 2023-11-13 22:15:54

## 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.

![Array com 1 elemento](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x4zu438k7evsdwgcaua0.png)

Exemplo de um array com 5 elementos.

![Array com 5 elementos](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ti76xbmyl00pu0v9qpwf.png)

## 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:

![Singly Node](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tg85up92kkhv3y3hp150.png)

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.

![Singly Linked List](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lrhtsbmc2lpwsbf295eo.png)

#### Implementação
Principais métodos:
* `add(data)` - Para adicionar um elemento.
* `remove(data)` - Para remover um elemento.
* `get(data)` - Retorna `true` ou `false` caso encontre ou não o elemento.

```java
/*
	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".

![Circular Singly Linked List](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9e9yjx8isnovo4lr29ov.png)

#### Implementação
Principais métodos:
* `add(data)` - Para adicionar um elemento.
* `remove(data)` - Para remover um elemento.
* `get(data)` - Retorna `true` ou `false` caso encontre ou não o elemento.

```java
/*
	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:

![Doubly Node](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7abcmmb4qawmdbk5jk9x.png)

Exemplo de uma doubly linked list com os elementos:

![Doubly Linked List](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jzj5h064shcq04ak0nb6.png)

#### Implementação
Principais métodos:
* `add(data)` - Para adicionar um elemento.
* `remove(data)` - Para remover um elemento.
* `get(data)` - Retorna `true` ou `false` caso encontre ou não o elemento.

```java
/*
	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`.

![Circular Doubly Linked List](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ff8qwe6cb4382s0f6yv1.png)

#### Implementação
Principais métodos:
* `add(data)` - Para adicionar um elemento.
* `remove(data)` - Para remover um elemento.
* `get(data)` - Retorna `true` ou `false` caso encontre ou não o elemento.

```java
/*
	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: 

![Stack](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kveus49nuyovct5jmv3p.png)

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:

```java
/*
	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()` - Retorna `true` ou `false` para caso a fila esteja vazia ou não.

O funcionamento de uma queue é da seguinte maneira:

![Queue](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c5bohoc7j2gkvuryr72g.png)

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 `node`vamos 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:

```java
/*
	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.