Listas vinculadas em Python: Tutorial com exemplos

Uma lista vinculada é uma estrutura de dados que desempenha um papel fundamental na organização e no gerenciamento de dados. Ele contém uma série de nós que são armazenados em locais aleatórios na memória, permitindo um gerenciamento eficiente da memória. Cada nó de uma lista vinculada contém dois componentes principais: a parte de dados e uma referência ao próximo nó da sequência.

Se esse conceito parecer complexo à primeira vista, não se preocupe!

Vamos analisar os fundamentos para explicar o que são listas vinculadas, por que as usamos e as vantagens exclusivas que elas oferecem.

Por que listas vinculadas?

As listas vinculadas foram criadas para superar várias desvantagens associadas ao armazenamento de dados em listas e matrizes regulares, conforme descrito abaixo:

Facilidade de inserção e exclusão

Em listas, a inserção ou exclusão de um elemento em qualquer posição que não seja o final requer o deslocamento de todos os itens subsequentes para uma posição diferente. Esse processo tem uma complexidade de tempo de O(n) e pode prejudicar significativamente o desempenho, especialmente à medida que o tamanho da lista aumenta. Se ainda não estiver familiarizado com o funcionamento das listas ou com sua implementação, você pode ler nosso tutorial sobre listas em Python.

As listas vinculadas, no entanto, funcionam de forma diferente. Eles armazenam elementos em vários locais de memória não contíguos e os conectam por meio de ponteiros a nós subsequentes. Essa estrutura permite que as listas vinculadas adicionem ou removam elementos em qualquer posição, bastando modificar os links para incluir um novo elemento ou ignorar o elemento excluído.

Quando a posição do elemento é identificada e há acesso direto ao ponto de inserção ou exclusão, a adição ou remoção de nós pode ser feita em tempo O(1).

Tamanho dinâmico

As listas Python são matrizes dinâmicas, o que significa que elas oferecem a flexibilidade de modificar o tamanho.

No entanto, esse processo envolve uma série de operações complexas, incluindo a realocação da matriz em um bloco de memória novo e maior. Essa realocação é ineficiente, pois os elementos são copiados para um novo bloco, possivelmente alocando mais espaço do que o imediatamente necessário.

Por outro lado, as listas vinculadas podem crescer e diminuir dinamicamente sem a necessidade de realocação ou redimensionamento. Isso os torna uma opção preferível para tarefas que exigem alta flexibilidade.

Eficiência de memória

As listas alocam memória para todos os seus elementos em um bloco contíguo. Se uma lista precisar crescer além de seu tamanho inicial, ela deverá alocar um novo bloco maior de memória contígua e copiar todos os elementos existentes para esse novo bloco. Esse processo é demorado e ineficiente, especialmente para listas grandes. Por outro lado, se o tamanho inicial da lista for superestimado, a memória não utilizada será desperdiçada.

Por outro lado, as listas vinculadas alocam memória para cada elemento separadamente. Essa estrutura leva a uma melhor utilização da memória, pois a memória para novos elementos pode ser alocada à medida que eles são adicionados.

Quando você deve usar listas vinculadas?

Embora as listas vinculadas ofereçam certos benefícios em relação às listas e matrizes regulares, como tamanho dinâmico e eficiência de memória, elas também têm suas limitações. Como os ponteiros de cada elemento devem ser armazenados para fazer referência ao próximo nó, o uso de memória por elemento é maior quando você usa listas vinculadas. Além disso, essa estrutura de dados não permite acesso direto aos dados. O acesso a um elemento requer uma passagem sequencial desde o início da lista, resultando em uma complexidade de tempo de pesquisa O(n).

A escolha entre usar uma lista vinculada ou uma matriz depende das necessidades específicas do aplicativo. As listas vinculadas são mais úteis quando:

• Você precisa inserir e excluir muitos elementos com frequência
• O tamanho dos dados é imprevisível ou pode mudar com frequência
• O acesso direto aos elementos não é um requisito
• O conjunto de dados contém elementos ou estruturas grandes

Tipos de listas vinculadas

Há três tipos de listas vinculadas, cada uma oferecendo vantagens exclusivas para diferentes cenários. Esses tipos são:

Listas com links únicos

Lista com um único link

Uma lista ligada simples é o tipo mais simples de lista ligada, em que cada nó contém alguns dados e uma referência ao próximo nó da sequência. Eles só podem ser percorridos em uma única direção - da cabeça (o primeiro nó) até a cauda (o último nó).

Cada nó em uma lista com um único link geralmente consiste em duas partes:

• Dados: As informações reais armazenadas no nó.
• Próximo ponteiro: Uma referência ao próximo nó. O próximo ponteiro do último nó geralmente é definido como nulo.

Como essas estruturas de dados só podem ser percorridas em uma única direção, o acesso a um elemento específico por valor ou índice exige que você comece no cabeçalho e percorra os nós sequencialmente até encontrar o nó desejado. Essa operação tem uma complexidade de tempo de O(n), o que a torna menos eficiente para listas grandes.

Inserir e excluir um nó no início de uma lista com um único link é altamente eficiente com uma complexidade de tempo de O(1). No entanto, a inserção e a exclusão no meio ou no final exigem que você percorra a lista até esse ponto, o que leva a uma complexidade de tempo O(n).

O design das listas com um único link faz com que elas sejam uma estrutura de dados útil ao realizar operações que ocorrem no início da lista.

Listas duplamente vinculadas

Lista duplamente vinculada

Uma desvantagem das listas com um único link é que só podemos percorrê-las em uma única direção e não podemos iterar de volta para o nó anterior, se necessário. Essa restrição limita nossa capacidade de realizar operações que exigem navegação bidirecional.

As listas duplamente vinculadas resolvem esse problema incorporando um ponteiro adicional em cada nó, garantindo que a lista possa ser percorrida em ambas as direções. Cada nó de uma lista duplamente vinculada contém três elementos: os dados, um ponteiro para o próximo nó e um ponteiro para o nó anterior.

Listas vinculadas circulares

Lista vinculada circular

As listas vinculadas circulares são uma forma especializada de lista vinculada em que o último nó aponta para o primeiro nó, criando uma estrutura circular. Isso significa que, diferentemente das listas vinculadas simples e duplas que vimos até agora, a lista vinculada circular não termina; em vez disso, ela faz um loop.

A natureza cíclica das listas vinculadas circulares as torna ideais para cenários que precisam ser percorridos continuamente, como jogos de tabuleiro que percorrem o caminho de volta do último jogador para o primeiro, ou em algoritmos de computação, como programação round-robin.

Como criar uma lista vinculada em Python

Agora que entendemos o que são listas vinculadas, por que as usamos e suas variações, vamos prosseguir com a implementação dessas estruturas de dados em Python. O bloco de notas deste tutorial também está disponível nesta pasta de trabalho do DataLab; se você criar uma cópia, poderá editar e executar o código. Essa é uma ótima opção se você tiver algum problema ao executar o código por conta própria!

Inicialização de um nó

Como aprendemos anteriormente, um nó é um elemento da lista vinculada que armazena dados e uma referência ao próximo nó da sequência. Veja como você pode definir um nó em Python:

class Node:
    def __init__(self, data):
        self.data = data  # Assigns the given data to the node
        self.next = None  # Initialize the next attribute to null

O código acima inicializa um nó executando duas ações principais: O atributo "data" do nó recebe um valor que representa as informações reais que o nó deve conter. O atributo "next" representa o endereço do próximo nó. No momento, ele está definido como None, o que significa que não está vinculado a nenhum outro nó da lista. À medida que continuarmos a adicionar novos nós à lista vinculada, esse atributo será atualizado para apontar para o nó subsequente.

Criando uma classe de lista vinculada

Em seguida, precisamos criar a classe de lista vinculada. Isso encapsulará todas as operações de gerenciamento dos nós, como inserção e remoção. Começaremos inicializando a lista vinculada:

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

Ao definir self.head como None, estamos afirmando que a lista vinculada está inicialmente vazia e que não há nós na lista para os quais apontar. Agora, continuaremos a preencher a lista inserindo novos nós.

Inserção de um novo nó no início de uma lista vinculada

Na classe LinkedList, adicionaremos um método para criar um novo nó e colocá-lo no início da lista:

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

Toda vez que você chamar o método acima, um novo nó será criado com os dados especificados. O próximo ponteiro desse novo nó é definido como o cabeçalho atual da lista, o que colocará esse nó na frente dos nós existentes. Por fim, o nó recém-criado passa a ser o cabeçalho da lista.

Agora, vamos preencher essa lista vinculada com uma série de palavras para que você entenda melhor como funciona a operação de inserção. Para fazer isso, vamos primeiro criar um método projetado para percorrer e imprimir o conteúdo da lista:

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

O método acima imprimirá o conteúdo de nossa lista vinculada. Vamos agora usar os métodos que definimos para preencher nossa lista com uma série de palavras: "A rápida raposa marrom".

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

As linhas de código acima devem gerar o seguinte resultado:

"the quick brown fox"

Inserção de um novo nó no final de uma lista vinculada

Agora, criaremos um método chamado insertAtEnd na classe LinkedList para criar um novo nó no final da lista. Se a lista estiver vazia, o novo nó se tornará o cabeçalho da lista. Caso contrário, ele será anexado ao último nó atual da lista. Vamos ver como isso funciona na prática:

def insertAtEnd(self, new_data):
        new_node = Node(new_data)  # Create a new node
        if self.head is None:
            self.head = new_node  # If the list is empty, make the new node the head
            return
        last = self.head 
        while last.next:  # Otherwise, traverse the list to find the last node
            last = last.next
        last.next = new_node  # Make the new node the next node of the last node

O método acima começa com a criação de um novo nó. Em seguida, ele verifica se a lista está vazia e, em caso afirmativo, o novo nó é atribuído como o cabeçalho da lista. Caso contrário, ele percorre a lista para encontrar o último nó e define o ponteiro desse nó como o novo nó.

Agora, precisamos incluir esse método em nossa classe LinkedList e usá-lo para adicionar uma palavra ao final da nossa lista. Para fazer isso, altere sua função principal para que fique assim:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Observe que simplesmente chamamos o método insertAtEnd para imprimir a palavra "jumps" no final da lista. O código acima deve gerar o seguinte resultado:

"the quick brown fox jumps"

Exclusão de um nó do início de uma lista vinculada

Excluir o primeiro nó de uma lista vinculada é fácil, pois você só precisa apontar o cabeçalho dessa lista para o segundo nó. Dessa forma, o primeiro nó não fará mais parte da lista. Para fazer isso, inclua o seguinte método na classe LinkedList:

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Exclusão de um nó do final de uma lista vinculada

Para excluir o último nó de uma lista vinculada, devemos percorrer a lista para encontrar o segundo último nó e alterar seu próximo ponteiro para None. Dessa forma, o último nó não fará mais parte da lista. Para isso, copie e cole o método a seguir em sua classe LinkedList:

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

O método acima primeiro verifica se a lista vinculada está vazia e, se estiver, retorna uma mensagem ao usuário. Caso contrário, se a lista contiver um único nó, esse nó será removido. Para listas com vários nós, o método localiza o penúltimo nó, e a referência do próximo nó é atualizada para None.

Vamos agora atualizar a função principal para excluir elementos do início e do fim da lista vinculada:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

O código acima imprimirá a lista antes e depois da exclusão, mostrando como as operações de inserção e exclusão funcionam em listas vinculadas. Você deverá ver a seguinte saída depois de executar esse código:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

Pesquisa de um valor específico na lista vinculada

A última operação que aprenderemos neste capítulo é a recuperação de um valor específico na lista vinculada. Para isso, o método deve começar no topo da lista e iterar por cada nó, verificando se os dados do nó correspondem ao valor da pesquisa. Aqui está uma implementação prática dessa operação:

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

Para localizar valores específicos na lista vinculada que criamos, atualize sua função principal para incluir o método de pesquisa que acabamos de criar:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

O código acima renderizará o seguinte resultado:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

A palavra "quick" foi localizada com sucesso na lista vinculada, pois existe na primeira posição da lista. No entanto, a palavra "lazy" (preguiçoso) não faz parte da lista, por isso não foi encontrada.

Considerações finais

Se você chegou até aqui, parabéns! Agora você tem uma sólida compreensão dos princípios básicos das listas vinculadas, incluindo sua estrutura, tipos, como adicionar e remover elementos e como percorrê-las.

Mas a jornada não termina aqui. As listas vinculadas são apenas o começo do mundo das estruturas de dados e dos algoritmos. Aqui estão algumas possíveis próximas etapas para você aprofundar seu conhecimento sobre o assunto:

Crie seu próprio projeto

Mergulhe nas aplicações práticas das listas vinculadas, integrando-as a um projeto de codificação ou de ciência de dados. As listas vinculadas são usadas para desenvolver sistemas de arquivos, construir tabelas de hash e até mesmo criar sistemas de navegação GPS e jogos de tabuleiro. Para começar com seus próprios projetos, confira nossos projetos gratuitos de ciência de dados guiados que ensinam você a resolver problemas do mundo real em Python, R e SQL.

Aprender sobre estruturas de dados e algoritmos

Aprender outras estruturas de dados, como árvores, pilhas e filas, é uma progressão natural a partir da compreensão das listas vinculadas. Essas estruturas se baseiam nos princípios das listas vinculadas, ajudando você a resolver uma variedade maior de problemas computacionais de forma eficiente. As árvores e as árvores de pesquisa binária, por exemplo, estendem o conceito de listas vinculadas em uma forma hierárquica, permitindo que cada nó se conecte a vários elementos na estrutura de dados.

Se esses conceitos não parecerem familiares para você, não se preocupe! A Datacamp tem um curso completo sobre estruturas de dados e algoritmos em Python que levará você a examinar esses conceitos com mais detalhes. Primeiro, você aprenderá sobre estruturas de dados, como pilhas, árvores, tabelas de hash, filas e gráficos. À medida que avança no curso, você terá uma compreensão dos algoritmos de busca e classificação, o que o ajudará a se tornar um programador e solucionador de problemas mais eficiente.

Exploração de conceitos avançados de listas vinculadas

Neste tutorial, implementamos listas com um único link, abrangendo operações como inserção, exclusão e passagem.

Você pode levar esse conhecimento um passo adiante, aprendendo a implementação de listas duplamente e circularmente vinculadas. As listas de saltos são outra extensão das listas vinculadas que permitem operações de pesquisa mais rápidas, facilitando o acesso mais rápido aos elementos.

Aprender sobre essas estruturas de dados avançadas levará suas habilidades técnicas para o próximo nível e melhorará drasticamente seus recursos de programação, preparando você para desafios mais complexos em áreas como ciência de dados, desenvolvimento de software e engenharia de aprendizado de máquina.

Se você quiser uma introdução à programação mais amigável para iniciantes antes de abordar esses tópicos avançados, explore nossa carreira de programador Python. Ele oferece uma série de cursos que ensinarão a você os fundamentos do idioma.