Lista Ligada (ou Encadeada)

Uma lista ligada é uma estrutura de dados linear que consiste em uma sequência de elementos, onde cada elemento aponta para o próximo.

Existem duas versões principais de listas ligadas: efêmera e persistente. A versão efêmera altera diretamente a lista, perdendo o estado anterior, enquanto a versão persistente preserva todas as versões anteriores após cada modificação.

História e Origem

As listas ligadas foram introduzidas por Allen Newell, Cliff Shaw e Herbert A. Simon em 1956, no desenvolvimento do Logic Theorist, o primeiro programa de inteligência artificial. As estruturas de dados persistentes foram propostas mais tarde, em 1986, por Driscoll, Sarnak, Sleator e Tarjan no artigo “Making Data Structures Persistent”.

Aplicações

As listas ligadas são amplamente utilizadas em várias aplicações:

• Implementação de outras estruturas de dados: como filas e pilhas.
• Sistemas de gerenciamento de memória: onde o uso de ponteiros permite alocações dinâmicas eficientes.
• Controle de versão: especialmente em sua forma persistente.
• Ambientes de programação funcional: que favorecem a imutabilidade das estruturas de dados.

Funcionamento

Na lista ligada efêmera, as operações alteram diretamente a estrutura, resultando na perda do estado anterior.

• Inserção: Adiciona um novo nó no início da lista.
• Remoção: Remove um nó ajustando os ponteiros dos nós adjacentes.
• Acesso: Navega pelos ponteiros da lista para encontrar o elemento desejado.

Na lista ligada persistente, cada modificação gera uma nova versão da lista, preservando as versões anteriores através do “compartilhamento de estrutura”. Cada operação retorna uma nova instância da lista.

• Inserção: Cria um novo nó que aponta para o primeiro nó da versão anterior.
• Remoção: Cria uma nova lista excluindo o nó desejado, reutilizando os nós não afetados.
• Acesso: Navega pelos ponteiros, semelhante à lista ligada efêmera.

Complexidade

• Inserção: O(1) – Adiciona o novo nó no início.
• Remoção: O(n) – Pode exigir a busca pelo nó a ser removido.
• Acesso: O(n) – Deve navegar pelos nós.

Implementação

Lista Ligada Efêmera em Python

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

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

    def insert(self, value):
        new_node = Node(value, self.head)
        self.head = new_node

    def delete(self, value):
        current = self.head
        prev = None
        while current:
            if current.value == value:
                if prev:
                    prev.next = current.next
                else:
                    self.head = current.next
                return
            prev = current
            current = current.next

    def print_list(self):
        current = self.head
        while current:
            print(current.value, end=" -> ")
            current = current.next
        print("None")

Lista Ligada Persistente em Python

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

class PersistentLinkedList:
    def __init__(self, head=None):
        self.head = head

    def insert(self, value):
        new_head = Node(value, self.head)
        return PersistentLinkedList(new_head)

    def delete(self, value):
        current = self.head
        new_head = None
        tail = None
        while current:
            if current.value != value:
                new_node = Node(current.value)
                if not new_head:
                    new_head = new_node
                    tail = new_node
                else:
                    tail.next = new_node
                    tail = new_node
            current = current.next
        return PersistentLinkedList(new_head)

    def print_list(self):
        current = self.head
        while current:
            print(current.value, end=" -> ")
            current = current.next
        print("None")

Exemplos

Exemplo Básico com Lista Ligada Efêmera

ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.print_list()  # 3 -> 2 -> 1 -> None
ll.delete(2)
ll.print_list()  # 3 -> 1 -> None

Exemplo Básico com Lista Ligada Persistente

pll = PersistentLinkedList()
pll = pll.insert(1)
pll = pll.insert(2)
pll = pll.insert(3)
pll.print_list()  # 3 -> 2 -> 1 -> None
pll2 = pll.delete(2)
pll2.print_list()  # 3 -> 1 -> None
pll.print_list()   # 3 -> 2 -> 1 -> None (original list remains unchanged)

Comparações

Vantagens da Lista Ligada Efêmera:
A principal vantagem de uma lista ligada efêmera é a sua simplicidade. Ela é mais fácil de implementar e usar, o que a torna uma escolha adequada para casos onde a complexidade mínima é desejada. Além disso, a eficiência de memória é uma grande vantagem, pois a lista efêmera utiliza a memória de forma mais eficiente ao não preservar estados anteriores, economizando espaço.

Desvantagens da Lista Ligada Efêmera:
A maior desvantagem da lista ligada efêmera é a perda de estado. Ela não preserva versões anteriores da lista, o que pode ser uma limitação em contextos onde é necessário acessar ou rastrear estados passados da estrutura de dados. Isso pode complicar operações que envolvem backtracking ou desfazer ações.

Vantagens da Lista Ligada Persistente:
Por outro lado, a lista ligada persistente oferece a grande vantagem da imutabilidade. Ela preserva estados anteriores, o que é extremamente útil para controle de versão, depuração e operações que exigem acesso a versões passadas dos dados. Essa característica facilita a depuração, pois permite rastrear e inspecionar estados anteriores da estrutura de dados.

Desvantagens da Lista Ligada Persistente:
No entanto, a lista ligada persistente pode consumir mais memória devido à necessidade de preservar múltiplas versões da lista. Além disso, sua implementação e gerenciamento são mais complexos, exigindo um entendimento mais profundo de estruturas de dados persistentes e técnicas de manipulação de memória.

Melhores Práticas

• Uso em contextos de acesso sequencial: Onde a navegação é linear.
• Evitar uso excessivo em contextos de buscas frequentes: Considerar estruturas alternativas como árvores (persistentes e efêmeras).
• Gerenciamento de versões: Manter um controle eficiente das versões para evitar uso excessivo de memória.

Referências

• Driscoll, J. R., Sarnak, N., Sleator, D. D., & Tarjan, R. E. (1986). Making data structures persistent. Proceedings of the eighteenth annual ACM symposium on Theory of computing – STOC ’86.
• Newell, A., Shaw, J. C., & Simon, H. A. (1956). Report on a General Problem-Solving Program.

Conclusão

As listas ligadas são estruturas de dados versáteis, com variantes efêmeras e persistentes oferecendo diferentes benefícios. A escolha entre elas depende dos requisitos específicos da aplicação, como necessidade de preservação de estados anteriores ou eficiência de memória. Para estudos futuros, explorar estruturas de dados persistentes mais complexas pode proporcionar benefícios adicionais em termos de desempenho e funcionalidade.