Implementação de lista vinculada individualmente em Python

Aprenda como implementar uma lista vinculada individualmente em Python. Explore a alocação dinâmica de memória, operações de nó, inserção, passagem e exclusão.

Experimente no Editor

Visão geral

Uma lista vinculada é uma estrutura de dados linear onde os elementos não são armazenados em locais de memória contíguos. Em vez disso, cada elemento (chamado nó) é um objeto separado que contém uma referência ao próximo nó na sequência.

O principal benefício de uma lista vinculada em relação a um array tradicional é seu dimensionamento dinâmico e a capacidade de inserir ou excluir elementos em tempo O(1) constante no início. No entanto, acessar elementos por índice requer travessia linear, que leva tempo O(n).

Em Python, implementamos uma lista vinculada definindo uma classe Node para armazenar os dados e o ponteiro de referência, e uma classe LinkedList para gerenciar o nó principal, inserções no início ou final e exclusões.

Saída de código e execução

Implementação de lista vinculada individualmente em Python, mostrando criação de nó, acréscimo e travessia de lista.

linked_list.py

Experimente no Editor

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

class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        
    def delete(self, key):
        curr = self.head
        if curr and curr.data == key:
            self.head = curr.next
            curr = None
            return
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        if not curr:
            return
        prev.next = curr.next
        curr = None
        
    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> None")

# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()

print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()

Saída terminal

Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> None

Implementação passo a passo

Implementando funcionalidade de desfazer e refazer em editores de texto
Construindo estruturas de dados complexas como gráficos, pilhas e filas
Gerenciando listas onde as frequências de inserção e exclusão superam as ações de pesquisa

Perguntas frequentes

Qual é a diferença entre listas vinculadas simples e duplamente?

Em uma lista vinculada individualmente, cada nó aponta apenas para o próximo nó. Em uma lista duplamente vinculada, cada nó contém referências ao nó seguinte e ao nó anterior, permitindo a travessia bidirecional ao custo de memória extra.

Por que o Python não possui uma classe LinkedList integrada?

Matrizes (listas) Python são implementadas como matrizes dinâmicas. Devido ao gerenciamento de memória do Python e às otimizaçõesCPython, as listas padrão são extremamente rápidas e eficientes para a maioria das tarefas, reduzindo a necessidade prática de uma lista vinculada integrada.

Tópicos Relacionados

Tutorial de estrutura de dados de pilha Python

Implemente uma pilha LIFO em Python. Execute nosso exemplo de código de pilha interativo para dominar os limites de push, pop, peek e capacidade.

Tutorial de estrutura de dados de fila Python

Domine as operações da fila FIFO em Python. Execute e execute nosso exemplo de fila interativa apresentando métodos de enfileiramento e desenfileiramento.