Lista Encadeada = corrente de Nos

Cada Node tem dado + ponteiro pro proximo. A lista rastreia a cabeca.

Big-O:
• append (cauda) — O(n) caminhar ate o fim
• prepend (cabeca) — O(1)
• busca — O(n)
• inserir/remover na posicao — O(n)
Python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
Python
class LinkedList:
    def __init__(self):
        self.head = None
    def append(self, data):
        node = Node(data)
        if not self.head:
            self.head = node
return
cur = self.head
Python
        while cur.next:
cur = cur.next
cur.next = node
Python
    def to_list(self):
        result, cur = [], self.head
        while cur:
            result.append(cur.data)
cur = cur.next
Python
        return result