Listas ligadas em Python: tutorial com exemplos

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

Se esse conceito parecer complexo à primeira vista, calma!

Vamos destrinchar os fundamentos para explicar o que são listas ligadas, por que as usamos e as vantagens que elas oferecem.

Por que usar listas ligadas?

As listas ligadas foram criadas para contornar várias desvantagens de armazenar dados em listas e arrays tradicionais, como descrito abaixo:

Facilidade de inserção e remoção

Em listas, inserir ou remover um elemento em qualquer posição que não seja o final exige deslocar todos os itens seguintes para outra posição. Esse processo tem complexidade de tempo O(n) e pode degradar bastante o desempenho, especialmente à medida que a lista cresce. Se você ainda não está familiarizado com o funcionamento das listas ou sua implementação, confira nosso tutorial sobre listas em Python.

Já as listas ligadas funcionam de forma diferente. Elas armazenam elementos em locais de memória variados e não contíguos e os conectam por ponteiros para os nós seguintes. Essa estrutura permite adicionar ou remover elementos em qualquer posição apenas modificando os links para incluir o novo elemento ou pular o que foi removido.

Quando você já tem uma referência direta ao nó no ponto de inserção ou remoção, a operação em si é O(1). Ainda assim, encontrar essa posição exige uma varredura O(n), então o benefício de O(1) só se aplica quando você já possui um ponteiro para o nó relevante (como ao trabalhar na cabeça da lista).

Tamanho dinâmico

As listas em Python são arrays dinâmicos, o que significa que oferecem flexibilidade para modificar o tamanho.

No entanto, esse processo envolve uma série de operações complexas, incluindo realocar o array para 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 necessário naquele momento.

Em contraste, as listas ligadas podem crescer e encolher dinamicamente sem necessidade de realocação ou redimensionamento. Isso as torna uma opção preferível para tarefas que exigem alta flexibilidade.

Eficiência de memória

Listas alocam memória para todos os seus elementos em um bloco contíguo. Se uma lista precisar crescer além do tamanho inicial, ela deve alocar um novo bloco contíguo maior e então 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 é desperdiçada.

Já as listas ligadas alocam memória separadamente para cada elemento. Essa estrutura leva a uma melhor utilização de memória, já que a memória para novos elementos pode ser alocada conforme eles são adicionados.

Quando usar listas ligadas?

Embora listas ligadas ofereçam benefícios em relação a listas e arrays comuns, como tamanho dinâmico e eficiência de memória, elas também possuem limitações. Como é necessário armazenar ponteiros para cada elemento referenciar o próximo nó, o uso de memória por elemento é maior em listas ligadas. Além disso, essa estrutura de dados não permite acesso direto aos dados. Para acessar um elemento, é preciso percorrer a lista sequencialmente a partir do início, resultando em complexidade O(n) para busca.

A escolha entre usar uma lista ligada ou um array depende das necessidades específicas da aplicação. As listas ligadas são mais úteis quando:

• Você precisa inserir e remover muitos elementos com frequência
• O tamanho dos dados é imprevisível ou muda 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 ligadas

Existem três tipos de listas ligadas, cada uma com vantagens para cenários diferentes. São elas:

Listas simplesmente ligadas

Lista simplesmente ligada

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

Cada nó em uma lista simplesmente ligada geralmente possui duas partes:

• Dados: a informação armazenada no nó.
• Ponteiro "next": uma referência para o próximo nó. O ponteiro do último nó geralmente é definido como null.

Como essas estruturas só podem ser percorridas em uma direção, acessar um elemento específico por valor ou índice exige começar pela cabeça e avançar nó a nó até encontrar o desejado. Essa operação tem complexidade O(n), sendo menos eficiente para listas grandes.

Inserir e remover um nó no início de uma lista simplesmente ligada é altamente eficiente, com complexidade O(1). Porém, inserções e remoções no meio ou no final exigem percorrer a lista até o ponto desejado, levando a complexidade O(n).

O design das listas simplesmente ligadas as torna úteis para operações que ocorrem no início da lista.

Listas duplamente ligadas

Lista duplamente ligada

Uma desvantagem das listas simplesmente ligadas é que só podemos percorrê-las em uma direção e não conseguimos voltar ao nó anterior quando necessário. Essa limitação restringe operações que exigem navegação bidirecional.

As listas duplamente ligadas resolvem esse problema adicionando um ponteiro extra em cada nó, permitindo que a lista seja percorrida em ambas as direções. Cada nó em uma lista duplamente ligada contém três elementos: os dados, um ponteiro para o próximo nó e um ponteiro para o nó anterior.

Listas ligadas circulares

Lista ligada circular

As listas ligadas circulares são uma forma especializada de lista ligada em que o último nó aponta de volta para o primeiro, criando uma estrutura circular. Isso significa que, ao contrário das listas simplesmente e duplamente ligadas que vimos até agora, a lista circular não termina; em vez disso, ela dá a volta.

A natureza cíclica das listas circulares as torna ideais para cenários que precisam de iteração contínua, como jogos de tabuleiro que voltam do último para o primeiro jogador, ou em algoritmos de computação como o escalonamento round-robin.

Resumo de complexidade de tempo

É útil ver rapidamente como listas ligadas se comparam às listas em Python:

O principal recado: listas ligadas vencem em inserções e remoções na cabeça (O(1)), mas perdem no resto. Se você não está adicionando ou removendo elementos com frequência no início da sua estrutura, provavelmente uma lista comum do Python é a melhor escolha.

Como criar uma lista ligada em Python

Agora que entendemos o que são listas ligadas, por que as usamos e suas variações, vamos implementar essas estruturas em Python. O notebook deste tutorial também está disponível neste workbook do DataLab; se você criar uma cópia, poderá editar e executar o código. Essa é uma ótima opção caso você tenha algum problema para rodar o código localmente!

Inicializando um nó

Como vimos, um nó é um elemento da lista ligada que armazena dados e uma referência para o próximo nó na sequência. Veja como definir um nó em Python:

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

    def __repr__(self):
        return f"Node({self.data})"

O código acima inicializa um nó realizando duas ações principais: o atributo "data" do nó recebe um valor que representa a informação que o nó deve conter. O atributo "next" representa o endereço do próximo nó. Ele está definido como None no momento, indicando que não aponta para nenhum outro nó na lista. À medida que adicionarmos novos nós à lista ligada, esse atributo será atualizado para apontar para o nó seguinte.

Criando a classe da lista ligada

Em seguida, precisamos criar a classe da lista ligada. Ela encapsulará todas as operações de gerenciamento de nós, como inserção e remoção. Vamos começar inicializando a lista ligada:

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

Ao definir self.head como None, estamos dizendo que a lista ligada está inicialmente vazia e não há nós para apontar. Agora vamos popular a lista inserindo novos nós.

Inserindo um novo nó no início de uma lista ligada

Dentro da classe LinkedList, vamos adicionar um método para criar um novo nó e colocá-lo no começo 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

Sempre que você chamar o método acima, um novo nó será criado com os dados informados. O ponteiro next desse novo nó é definido para a cabeça atual da lista, o que coloca o nó à frente dos demais. Por fim, o novo nó passa a ser a cabeça da lista.

Agora vamos popular essa lista ligada com uma série de palavras para entender melhor como funciona a inserção. Para isso, primeiro crie um método 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 imprime o conteúdo da nossa lista ligada. Agora vamos usar os métodos que definimos para popular a lista com as palavras: “the quick brown fox”.

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()

O código acima deve gerar a seguinte saída:

"the quick brown fox"

Inserindo um novo nó no final de uma lista ligada

Agora vamos criar 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á a cabeça. Caso contrário, ele será anexado ao último nó atual da lista. Veja na prática:

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

O método acima começa criando um novo nó. Em seguida, verifica se a lista está vazia e, se estiver, o novo nó é atribuído como cabeça. Caso contrário, percorre a lista para encontrar o último nó e define o ponteiro desse nó para o novo nó.

Agora precisamos incluir esse método na classe LinkedList e usá-lo para adicionar uma palavra ao final da lista. Para isso, ajuste sua função principal para ficar 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()

Repare que simplesmente chamamos o método insertAtEnd para adicionar a palavra “jumps” ao final da lista. O código acima deve gerar a seguinte saída:

"the quick brown fox jumps"

Removendo um nó do início de uma lista ligada

Remover o primeiro nó de uma lista ligada é simples, pois basta apontar a cabeça da lista para o segundo nó. Assim, o primeiro nó deixa de fazer parte da lista. Para 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

Removendo um nó do final de uma lista ligada

Para remover o último nó de uma lista ligada, precisamos percorrer a lista até encontrar o penúltimo nó e mudar seu ponteiro next para None. Assim, o último nó deixa de fazer parte da lista. Copie e cole o método abaixo na sua classe LinkedList para fazer isso:

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 ligada está vazia, retornando uma mensagem ao usuário caso esteja. Se a lista contiver um único nó, esse nó é removido. Para listas com vários nós, o método localiza o penúltimo nó e atualiza a referência do seu próximo nó para None.

Agora vamos atualizar a função principal para remover elementos do início e do final da lista ligada:

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 das remoções, mostrando como as operações de inserção e exclusão funcionam em listas ligadas. Você deve ver a seguinte saída ao executar esse código:

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

Buscando um valor específico na lista ligada

A última operação que vamos aprender neste capítulo é a recuperação de um valor específico na lista ligada. Para isso, o método deve começar pela cabeça da lista e iterar por cada nó, verificando se os dados do nó correspondem ao valor procurado. Veja 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 encontrar valores específicos na lista ligada que criamos, atualize sua função principal para incluir o método de busca 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 gerará a seguinte saída:

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 encontrada com sucesso na lista ligada, pois está na primeira posição. Já a palavra “lazy” 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 base sólida dos princípios das listas ligadas, incluindo sua estrutura, tipos, como adicionar e remover elementos e como percorrê-las.

Mas a jornada não para por aqui. Listas ligadas são apenas o começo do mundo de estruturas de dados e algoritmos. Aqui vão alguns próximos passos para aprofundar seu conhecimento no assunto:

Crie seu próprio projeto

Mergulhe nas aplicações práticas de listas ligadas integrando-as a um projeto de programação ou de ciência de dados. Listas ligadas são usadas para desenvolver sistemas de arquivos, construir hash tables e até criar sistemas de navegação por GPS e jogos de tabuleiro. Para começar seus próprios projetos, explore nossos projetos de ciência de dados gratuitos e guiados que ensinam a resolver problemas reais em Python, R e SQL.

Aprenda sobre estruturas de dados e algoritmos

Aprender outras estruturas de dados, como árvores, pilhas e filas, é um passo natural após entender listas ligadas. Essas estruturas se baseiam nos princípios das listas ligadas, ajudando você a resolver uma gama mais ampla de problemas computacionais com eficiência. Árvores e árvores binárias de busca, por exemplo, estendem o conceito das listas ligadas para uma forma hierárquica, permitindo que cada nó se conecte a múltiplos elementos na estrutura de dados.

Se esses conceitos soam desconhecidos, não se preocupe! A Datacamp tem um curso completo de estruturas de dados e algoritmos em Python que vai aprofundar esses tópicos. Primeiro, você aprenderá estruturas como pilhas, árvores, hash tables, filas e grafos. Ao avançar no curso, você vai entender algoritmos de busca e ordenação, o que vai ajudar você a programar e resolver problemas com mais eficiência.

Explorando conceitos avançados de listas ligadas

Implementamos listas simplesmente ligadas neste tutorial, cobrindo operações como inserção, remoção e travessia.

Você pode dar um passo além aprendendo a implementação de listas duplamente ligadas e circulares. Skip lists são outra extensão de listas ligadas que permitem buscas mais rápidas, facilitando o acesso acelerado aos elementos.

Aprender essas estruturas de dados avançadas vai levar suas habilidades técnicas para o próximo nível e melhorar bastante sua capacidade de programar, preparando você para desafios mais complexos em áreas como ciência de dados, desenvolvimento de software e engenharia de machine learning.

Se você quiser uma introdução ainda mais amigável à programação antes de encarar esses tópicos avançados, explore nossa trilha de habilidades Python Programming. Ela oferece uma sequência de cursos que ensinam os fundamentos da linguagem.