Estrutura de Dados
Este repositório foi criado como registro dos meus estudo sobre estruturas de dados com Python3.
O que são estruturas de dados (ED)?🔗
Uma Estrutura de dados representa uma organização de dados na memória de um computador ou equivalente, permitindo que esses dados possam ser utilizados de forma eficiente. Há diversas EDs e cada uma pode encontrar muitas aplicações em desenvolvimento de sistemas. A velocidade do seu programa, geralmente, está na forma em que seus dados são organizados durante o processamento. Com as EDs adequadas podemos solucionar problemas extremamente complexos de forma simples e eficiente.
Exemplos de Estruturas de Dados🔗
- Lista Encadeada
- Pilha
- Fila
- Lista Duplamente Encadeada
Lista Encadeada🔗
A lista encadeada é uma estrutura onde seus elementos são arrumados numa ordem linear, onde cada elemento tem um próximo (exceto o último). Ela anda somente em um sentido, não consegue retornar.
Operações🔗
- Adicionar um item.
- Remover um item passando o índice.
- Acessar o elemento passando o índice
- Iterar sobre os elementos
- Descobrir se um certo elemento está na lista e o seu índice
- Obter o número de elementos na estrutura
Código🔗
linked_list.py
class Node:
def __init__(self, item):
self.data = item
self.next = None
class LinkedList:
def __init__(self):
self._head = None
self._size = 0
def __len__(self):
"""Retorna o número de elementos na estrutura."""
return self._size
def __str__(self):
"""Representa o conteúdo da LinkedList quando ela for printada."""
if not self._head:
return 'LinkedList[]'
linked_list = 'LinkedList['
auxiliary = self._head
while True:
linked_list += (
f"'{auxiliary.data}'"
if type(auxiliary.data) == str
else f'{auxiliary.data}'
)
if not auxiliary.next:
linked_list += ']'
break
linked_list += ', '
auxiliary = auxiliary.next
return linked_list
def __repr__(self):
"""Representa o conteúdo da LinkedList em modo de DEBUG."""
return self.__str__()
def __iter__(self):
"""Implementa iter(self). Torna a LinkedList passível de iterações."""
auxiliary = self._head
for pos in range(self._size):
yield f'{auxiliary.data}'
if auxiliary.next is None:
break
auxiliary = auxiliary.next
def __getitem__(self, index):
"""Retorna o objeto no index, self[index].
Parameters
----------
index:
índice da LinkedList.
"""
auxiliary = self._getnode(index)
if auxiliary:
return auxiliary.data
else:
raise IndexError("index out of range")
def __setitem__(self, index, item):
"""Define self[index] como item.
Parameters
----------
index:
índice a ser a inserido
item:
objeto a ser inserido
"""
auxiliary = self._getnode(index)
if not auxiliary:
raise IndexError("index out of range")
auxiliary.data = item
def append(self, item):
"""Adiciona e retorna o item no final da DoublyLinkedList.
Parameters
----------
item:
objeto a ser adicionado
"""
if not self._head:
self._head = Node(item)
self._size += 1
return self._head.data
auxiliary = self._head
while True:
if not auxiliary.next:
break
auxiliary = auxiliary.next
auxiliary.next = Node(item)
self._size += 1
return auxiliary.next.data
def _getnode(self, index):
"""Pega o objeto no index informado.
Parameters
----------
index:
índice do objeto
"""
if not self._head:
raise IndexError("index out of range")
auxiliary = self._head
for i in range(index):
if not auxiliary:
raise IndexError("index out of range") # return None
auxiliary = auxiliary.next
return auxiliary
def index(self, item):
"""Retorna o primeiro índice do item.
Parameters
----------
item:
objeto a ser verificado.
"""
if not self._head:
raise IndexError('The LinkedList is empty')
index = 0
auxiliary = self._head
while True:
if auxiliary.data == item:
return index
if auxiliary.next is None:
raise ValueError(f'{item} is not in LinkedList')
index += 1
auxiliary = auxiliary.next
def insert(self, index, item):
"""Insere e retorna o item no index.
Parameters
----------
index:
índice a ser inserido.
item:
objeto a ser inserido.
"""
node = Node(item)
if index == 0:
node.next = self._head
self._head = node
self._size += 1
return self._head.data
auxiliary = self._getnode(index - 1)
node.next = auxiliary.next
auxiliary.next = node
self._size += 1
return auxiliary.next.data
def pop(self, index=-1):
"""Remove e retorna o item no index (último por default).
Parameters
----------
index:
índice do objeto a ser removido.
"""
if index == -1:
index = self._size - 1
if not self._head:
raise IndexError('The LinkedList is empty')
if index >= self._size or index < 0:
raise IndexError('pop index out of range')
if index == 0:
if self._size == 1:
auxiliary = self._head.data
self._head = None
self._size -= 1
return auxiliary
auxiliary = self._head.data
self._head = self._head.next
self._size -= 1
return auxiliary
aux_index = 1
preceding = self._head
auxiliary = self._head.next
while True:
if aux_index == index:
item = preceding.next.data
preceding.next = auxiliary.next
auxiliary.next = None
self._size -= 1
return item
preceding = auxiliary
auxiliary = auxiliary.next
aux_index += 1
def remove(self, item):
"""Remove e retorna a primeira ocorrencia do item.
Parameters
----------
item:
objeto a ser removido.
"""
if not self._head:
raise ValueError(f'{item} is not in list')
if self._head.data == item:
auxiliary = self._head.data
self._head = self._head.next
self._size -= 1
return auxiliary
preceding = self._head
auxiliary = self._head.next
while True:
if not auxiliary:
raise ValueError(f'{item} is not in list')
if auxiliary.data == item:
preceding.next = auxiliary.next
auxiliary.next = None
self._size -= 1
return item
preceding = auxiliary
auxiliary = auxiliary.next
def count(self, item):
"""Retorna o número de ocorrencia do item.
Parameters
----------
item:
objeto a ser verificado
"""
if not self._head:
return 0
counter = 0
auxiliary = self._head
while True:
if auxiliary.data == item:
counter += 1
if auxiliary.next is None:
return counter
auxiliary = auxiliary.next
Pilha🔗
A pilha é uma estrutura onde só é possível ter acesso ao elemento do topo, para ter acesso ao elemento de baixo é necessário remover o que está no topo. Ela segue o princípio LIFO (last in, first out), o último a entrar é o primeiro a sair.
Operações🔗
- Inserir um novo item no topo da pilha
- Remover o item do topo
- Ver o item do topo
- Mostrar o número de elementos na estrutura
Código🔗
stack.py
class Node:
def __init__(self, item):
self.data = item
self.preceding = None
class Stack:
def __init__(self):
self.top = None
self._size = 0
def __len__(self):
"""Retorna o tamanho da Stack."""
return self._size
def __str__(self):
"""Representa o conteúdo da Stack quando ela for printada."""
if not self.top:
return 'Stack[]'
auxiliary = self.top
stack = 'Stack['
while True:
stack += (
f"'{auxiliary.data}'"
if type(auxiliary.data) == str
else f'{auxiliary.data}'
)
if not auxiliary.preceding:
stack += ']'
break
stack += ', '
auxiliary = auxiliary.preceding
return stack
def __repr__(self):
"""Representa o conteúdo da Stack em modo de DEBUG."""
return self.__str__()
def push(self, item):
"""Insere um objeto no topo.
Parameters
----------
item:
objeto a ser inserido.
"""
auxiliary = Node(item)
auxiliary.preceding = self.top
self.top = auxiliary
self._size += 1
return self.top.data
def pop(self):
"""Remove o objeto do topo."""
if not self.top:
raise IndexError('The stack is empty')
auxiliary = self.top
self.top = auxiliary.preceding
self._size -= 1
return auxiliary.data
def peek(self):
"""Retorna o topo sem remover."""
if not self.top:
raise IndexError('The stack is empty')
return self.top.data
def contain(self, item):
"""Verifica se contém o objeto na Stack.
Parameters
----------
item:
objeto a ser verificado.
"""
if not self.top:
raise IndexError('The stack is empty')
auxiliary = self.top
while auxiliary:
if auxiliary.data == item:
return True
auxiliary = auxiliary.preceding
return False
Fila🔗
A fila é uma estrutura onde só é possível ter acesso ao primeiro elemento, para ter acesso ao próximo elemento é necessário remover o primeiro. Ela segue o princípio FIFO (first in, first out), o primeiro a entrar é o primeiro a sair.
Operações🔗
- Inserir um elemento no fim da fila
- Remover o primeiro elemento da fila
- Mostrar o número de elementos na estrutura
- Ver o primeiro elemento
- Verificar se há um determinado elemento na fila
Código🔗
queue.py
class Node:
def __init__(self, item):
self.data = item
self.next = None
class Queue:
def __init__(self):
self.head = None
self.tail = None
self._size = 0
def __len__(self):
"""Retorna o tamanho da Queue."""
return self._size
def __str__(self):
"""Representa o conteúdo da Queue quando ela for printada."""
if not self.head:
return 'Queue[]'
queue = 'Queue['
auxiliary = self.head
while True:
queue += (
f"'{auxiliary.data}'"
if type(auxiliary.data) == str
else f'{auxiliary.data}'
)
if auxiliary == self.tail:
queue += ']'
break
queue += ', '
auxiliary = auxiliary.next
return queue
def __repr__(self):
"""Representa o conteúdo da Stack em modo de DEBUG."""
return self.__str__()
def equeue(self, item):
"""Insere um objeto no fim da Queue.
Parameters
----------
item:
objeto a ser inserido.
"""
if not self.head:
self.head = Node(item)
self.tail = self.head
return self.tail.data
self.tail.next = Node(item)
self.tail = self.tail.next
self._size += 1
return self.tail.data
def dequeue(self):
"""Remove o primeiro objeto."""
if not self.head:
raise IndexError('The queue is empty')
auxiliary = self.head.data
self.head = self.head.next
self._size -= 1
return auxiliary
def first(self):
"""Retorna o primeiro objeto."""
if not self.head:
raise IndexError('The queue is empty')
return self.head.data
def contain(self, item):
"""Verifica se contém o objeto na Queue e retorna o índice.
Parameters
----------
item:
objeto a ser verificado.
"""
if not self.head:
raise IndexError('The queue is empty')
auxiliary = self.head
_size = 0
while True:
if auxiliary.data == item:
return _size
if auxiliary == self.tail:
break
_size += 1
auxiliary = auxiliary.next
raise ValueError(f'{item} is not in Queue')
Lista Duplamente Encadeada🔗
A lista duplamente encadeada é uma estrutura onde seus elementos são arrumados numa ordem linear, onde cada elemento tem um antecessor (exceto o primeiro) e um sucessor (exceto o último). Você tem as referências tanto indo como voltando, ao percorrer uma lista você pode avançar e retornar pelos objetos.
Operações🔗
- Adicionar um item
- Remover um item passando por índice
- Acessar o elemento passando por índice
- Iterar sobre os elementos
- Buscar um certo elemento na lista e retornar seu índice
- Retornar o número de elementos na estrutura
- Limpar a lista
- Copiar a lista
- Reverter a ordem dos elementos
- Ordenar por ordem crescente ou decrescente, sendo numérico ou alfabético
Código🔗
doubly_linked_list.py
class Node:
def __init__(self, item):
self.data = item
self.preceding = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self._head = None
self._tail = None
self._size = 0
def __len__(self):
"""Retorna o número de elementos na estrutura."""
return self._size
def __str__(self):
"""Representa o conteúdo da DoublyLinkedList."""
if not self._head:
return 'DoublyLinkedList[]'
doubly_linked_list = 'DoublyLinkedList['
auxiliary = self._head
while True:
doubly_linked_list += (
f"'{auxiliary.data}'"
if type(auxiliary.data) == str
else f'{auxiliary.data}'
)
if auxiliary == self._tail:
doubly_linked_list += ']'
break
doubly_linked_list += ', '
auxiliary = auxiliary.next
return doubly_linked_list
def __repr__(self):
"""Representa o conteúdo da DoublyLinkedList em modo de DEBUG."""
return self.__str__()
def __iter__(self):
"""Implementa iter(self). Torna a estrutura passível de iterações."""
auxiliary = self._head
for pos in range(self._size):
yield f'{auxiliary.data}'
if auxiliary.next is None:
break
auxiliary = auxiliary.next
def __add__(self, obj):
"""Somar objetos."""
if (
type(obj) == list
or type(obj) == tuple
or type(obj) == set
or type(obj) == dict
):
raise TypeError(
'can only concatenate DoublyLinkedList with the same type'
)
from copy import deepcopy
if type(self) == type(obj):
auxiliary = deepcopy(self)
for item in obj:
auxiliary.append(item)
return auxiliary
def __getitem__(self, index):
"""Retorna o objeto no index, self[index].
Parameters
----------
index:
índice da DoublyLinkedList.
"""
if index >= self._size or index < 0:
raise IndexError('Index out of range')
aux_index = 0
auxiliary = self._head
while True:
if aux_index == index:
return auxiliary.data
if auxiliary.next is None:
return
aux_index += 1
auxiliary = auxiliary.next
def __setitem__(self, index, item):
"""Define self[index] como item.
Parameters
----------
index:
índice a ser a inserido
item:
objeto a ser inserido
"""
self.pop(index)
self.insert(index, item)
def clear(self):
"""Remove todos os items da DoublyLinkedList."""
self._head = None
self._tail = None
self._size = 0
def copy(self):
"""Retorna uma cópia superficial da DoublyLinkedList."""
shallow_copy = self
return shallow_copy
def reverse(self):
"""Reverte NA ORDEM."""
def sort(self, reverse=False):
"""Ordena a DoublyLinkedList.
Parameters
----------
reverse:
False por default, se True, ordena de forma decresente.
"""
def append(self, item):
"""Adiciona e retorna o item no final da DoublyLinkedList.
Parameters
----------
item:
objeto a ser adicionado
"""
if not self._head:
self._head = Node(item)
self._tail = self._head
self._size += 1
return self._head.data
auxiliary = Node(item)
auxiliary.preceding = self._tail
self._tail.next = auxiliary
self._tail = auxiliary
self._size += 1
return self._tail.data
def insert(self, index, item):
"""Insere e retorna o item no index.
Parameters
----------
index:
índice a ser inserido.
item:
objeto a ser inserido.
"""
if index >= self._size:
return self.append(item)
if index == 0:
auxiliary = Node(item)
auxiliary.next = self._head
self._head.preceding = auxiliary
self._head = auxiliary
return auxiliary.data
auxiliary = self._head
for i in range(index - 1):
auxiliary = auxiliary.next
node_new = Node(item)
node_new.preceding = auxiliary
node_new.next = auxiliary.next
node_new.next.preceding = node_new
auxiliary.next = node_new
return node_new.data
def pop(self, index=-1):
"""Remove e retorna o item no index (último por default).
Parameters
----------
index:
índice do objeto a ser removido.
"""
if index == -1:
index = self._size - 1
if not self._head:
raise IndexError('The DoublyLinkedList is empty')
if index >= self._size or index < 0:
raise IndexError('pop index out of range')
if index == 0:
if self._size == 1:
auxiliary = self._head.data
self._head = None
self._tail = None
self._size -= 1
return auxiliary
auxiliary = self._head.data
self._head = self._head.next
self._size -= 1
return auxiliary
if index == self._size - 1:
auxiliary = self._tail.data
self._tail.preceding.next = None
self._tail = self._tail.preceding
self._size -= 1
return auxiliary
auxiliary = self._head
for i in range(index):
auxiliary = auxiliary.next
auxiliary.preceding.next = auxiliary.next
auxiliary.next.preceding = auxiliary.preceding
self._size -= 1
return auxiliary.data
def count(self, item):
"""Retorna o número de ocorrencia do item.
Parameters
----------
item:
objeto a ser verificado
"""
if not self._head:
return 0
counter = 0
auxiliary = self._head
while True:
if auxiliary.data == item:
counter += 1
if auxiliary.next is None:
return counter
auxiliary = auxiliary.next
def index(self, item):
"""Retorna o primeiro índice do item.
Parameters
----------
item:
objeto a ser verificado.
"""
if not self._head:
raise IndexError('The DoublyLinkedList is empty')
index = 0
auxiliary = self._head
while True:
if auxiliary.data == item:
return index
if auxiliary.next is None:
raise ValueError(f'{item} is not in DoublyLinkedList')
index += 1
auxiliary = auxiliary.next
def remove(self, item):
"""Remove e retorna a primeira ocorrencia do item.
Parameters
----------
item:
objeto a ser removido.
"""
index = 0
auxiliary = self._head
while True:
if auxiliary.data == item:
return self.pop(index)
if auxiliary.next is None:
raise ValueError(f'{item} is not in DoublyLinkedList')
index += 1
auxiliary = auxiliary.next