Implementando uma lista encadeada em Python

[

Implementação de Listas Encadeadas em Python

Neste tutorial, você aprenderá a implementar listas encadeadas em Python. As listas encadeadas são uma coleção de elementos ordenados, onde cada elemento é chamado de “nó” e contém um valor e uma referência ao próximo nó da lista.

Entendendo as Listas Encadeadas

Antes de explorar a implementação das listas encadeadas, é importante compreender a estrutura dessas listas. Cada nó de uma lista encadeada possui dois campos:

1. Dado: contém o valor a ser armazenado no nó.
2. Próximo: contém uma referência ao próximo nó da lista.

Aqui está uma representação visual de um nó típico:

Node:

+-------+
| Dado  |
+-------+
| Próximo |
+-------+

A lista encadeada é formada por uma sequência de nós. O primeiro nó é conhecido como “cabeça” da lista e é usado como ponto de partida para qualquer iteração pela lista. O último nó tem sua referência “próximo” apontando para None, indicando o final da lista.

Aqui está uma representação visual da estrutura de uma lista encadeada:

Linked List:

+-------+
| Dado  |
+-------+
| Próximo |
+-------+
   |
   v
+-------+
| Dado  |
+-------+
| Próximo |
+-------+
   |
   v
   .
   .
   .

Agora que você entende a estrutura das listas encadeadas, vamos analisar algumas aplicações práticas.

Aplicações Práticas

As listas encadeadas são utilizadas em diversas áreas do mundo real. Elas podem ser usadas para implementar estruturas de dados como filas e pilhas, além de serem úteis em algoritmos de busca e ordenação.

Implementando sua Própria Lista Encadeada

Agora que você já conhece a estrutura e as aplicações das listas encadeadas, vamos aprender a implementar sua própria lista encadeada em Python.

Passo 1: Criando uma Lista Encadeada

Primeiro, vamos criar a classe Node para representar um nó da lista encadeada. Cada nó possui um valor e uma referência ao próximo nó da lista.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Em seguida, podemos criar a classe LinkedList que representa a lista encadeada em si. A lista encadeada possui um único atributo, que é o nó “cabeça”.

class LinkedList:
    def __init__(self):
        self.head = None

Agora, podemos criar uma instância da LinkedList. Inicialmente, a lista estará vazia.

# Criando uma instância da lista encadeada
my_list = LinkedList()

Passo 2: Percorrendo uma Lista Encadeada

Agora que temos uma lista encadeada vazia, vamos aprender a percorrer os elementos da lista.

# Percorrendo a lista encadeada
current = my_list.head
while current:
    print(current.data)
    current = current.next

Neste exemplo, utilizamos uma variável chamada current para percorrer os nós da lista começando pelo nó “cabeça”. Enquanto current não for None, ou seja, enquanto não chegarmos ao final da lista, imprimimos o valor do nó atual e avançamos para o próximo nó.

Passo 3: Inserindo um Novo Nó na Lista

Agora, vamos aprender a inserir um novo nó em nossa lista encadeada. Para isso, vamos criar um método chamado insert na classe LinkedList.

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

Neste exemplo, criamos um novo nó com o valor fornecido e, em seguida, verificamos se a lista encadeada está vazia. Se estiver vazia, o novo nó se torna o nó “cabeça”. Caso contrário, percorremos a lista até o último nó e adicionamos o novo nó como próximo do último nó.

Agora, podemos inserir nós em nossa lista encadeada.

# Inserindo nós na lista encadeada
my_list.insert(1)
my_list.insert(2)
my_list.insert(3)

Após inserir os nós, podemos percorrer a lista e imprimir os valores.

Passo 4: Removendo um Nó da Lista

Por fim, vamos aprender a remover um nó da lista encadeada. Para remover um nó, precisamos percorrer a lista até encontrar o nó que desejamos remover e ajustar as referências para “pular” o nó.

class LinkedList:
    # outros códigos omitidos

    def remove(self, data):
        current = self.head
        previous = None

        while current:
            if current.data == data:
                if previous:
                    previous.next = current.next
                else:
                    self.head = current.next
                return
            previous = current
            current = current.next

Neste exemplo, percorremos a lista até encontrar o nó com o valor fornecido. Se encontrarmos o nó, ajustamos as referências para remover o nó. Caso contrário, percorremos a próxima iteração da lista até encontrar o nó ou chegar ao final da lista.

Agora, podemos remover um nó da lista encadeada.

# Removendo um nó da lista encadeada
my_list.remove(2)

Após remover o nó, podemos percorrer a lista novamente para verificar se o nó foi removido corretamente.

Conclusão

As listas encadeadas são uma estrutura de dados poderosa e útil em diversas aplicações. Neste tutorial, você aprendeu a implementar sua própria lista encadeada em Python, desde a criação de nós até a inserção e remoção de elementos na lista. Agora você tem o conhecimento necessário para utilizar listas encadeadas em seus projetos. Experimente criar diferentes implementações e explorar as diversas possibilidades que as listas encadeadas oferecem!