Listas: Listas Ligadas Simples e Duplas

5.1 Definição de lista e seus tipos

Lista — é uma estrutura de dados dinâmica, composta por elementos (nós), onde cada nó contém dados e links para outros nós. Ao contrário dos arrays, as listas podem mudar de tamanho durante a execução do programa.

Importante! Neste caso, não estamos falando da classe list do Python, mas sim de uma estrutura de dados da teoria dos algoritmos.

Tipos de listas:

• Lista Ligada Simples (Singly Linked List): Cada nó contém dados e um link para o próximo nó.
• Lista Ligada Dupla (Doubly Linked List): Cada nó contém dados, um link para o próximo nó e um link para o nó anterior.

5.2 Funcionamento de uma lista ligada simples

Estrutura de uma lista ligada simples:

• Nó (Node): Consiste em duas partes: dados e um link para o próximo nó.
• Cabeça (Head): Ponteiro para o primeiro nó da lista.

Funcionamento:

• Adição de nó: Acontece criando um novo nó e atualizando o link do último nó para o novo nó.
• Remoção de nó: Requer atualização do link do nó anterior para o próximo nó do nó a ser removido.

Exemplo de implementação:

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

class SinglyLinkedList:
    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 display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Exemplo de uso:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Saída: 1 -> 2 -> 3 -> None

5.3 Funcionamento de uma lista ligada dupla

Estrutura de uma lista ligada dupla:

• Nó (Node): Consiste em três partes: dados, um link para o próximo nó e um link para o nó anterior.
• Cabeça (Head): Ponteiro para o primeiro nó da lista.
• Cauda (Tail): Ponteiro para o último nó da lista (não obrigatório, mas frequentemente usado).

Funcionamento:

• Adição de nó: Acontece criando um novo nó e atualizando os links do último nó e do novo nó.
• Remoção de nó: Requer atualização dos links dos nós adjacentes ao nó a ser removido.

Exemplo de implementação:

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

class DoublyLinkedList:
    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
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Exemplo de uso:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Saída: 1 <-> 2 <-> 3 <-> None

5.4 Operações principais

Operações principais: inserção, remoção, busca

Inserção:

• Lista Ligada Simples: Inserção de um novo nó no fim da lista requere a passagem por todos os nós até o último e a atualização do link do último nó.
• Lista Ligada Dupla: Inserção de um novo nó no fim da lista é semelhante à lista ligada simples, mas também requer a atualização do link prev do novo nó para o nó anterior.

Remoção:

• Lista Ligada Simples: Remoção de nó requere a passagem pela lista até o nó que precisa ser removido, e a atualização do link do nó anterior para o próximo nó do nó a ser removido.
• Lista Ligada Dupla: Remoção de nó requer atualização dos links next e prev dos nós adjacentes ao nó a ser removido.

Busca: Passagem pela lista da cabeça à cauda e comparação dos dados de cada nó com o valor procurado. Complexidade de tempo — O(n).

5.5 Exemplo de uso das listas

Vamos implementar uma stack usando uma lista ligada simples como exemplo.

A stack pode ser facilmente implementada usando uma lista ligada simples, utilizando métodos de adição push e remoção pop de elementos. Ela deve ter 2 métodos:

• push — adição de um novo elemento no fim da lista
• pop — remoção do último elemento do fim da lista

Exemplo de implementação:

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Exemplo de uso:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Saída: 3 -> 2 -> 1 -> None
print(stack.pop())  # Saída: 3
stack.display()  # Saída: 2 -> 1 -> None