{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "05c549ad",
   "metadata": {},
   "source": [
    "## Listas Encadeadas Simples em Python\n",
    "\n",
    "Neste notebook vamos implementar uma **lista encadeada simples**: uma estrutura **linear e dinâmica** formada por **nós**, em que cada nó guarda um `valor` e uma referência para o `proximo` nó.\n",
    "\n",
    "Diferente dos vetores, a lista **não tem tamanho fixo**: ela cresce e diminui conforme a necessidade, e inserir/remover exige apenas **ajustar referências**.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2f7f717",
   "metadata": {},
   "source": [
    "### A classe `No`\n",
    "\n",
    "O nó é o bloco básico da lista. Ele possui um `valor` e uma referência `proximo` (que é `None` quando o nó é o último).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "bdf8b343",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:19.579858Z",
     "iopub.status.busy": "2026-09-28T17:16:19.579669Z",
     "iopub.status.idle": "2026-09-28T17:16:19.586513Z",
     "shell.execute_reply": "2026-09-28T17:16:19.585567Z"
    }
   },
   "outputs": [],
   "source": [
    "class No:\n",
    "    def __init__(self, valor):\n",
    "        self.valor = valor\n",
    "        self.proximo = None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c46857ee",
   "metadata": {},
   "source": [
    "### A classe `ListaEncadeada`\n",
    "\n",
    "A lista guarda apenas o ponteiro para o **primeiro nó** (`primeiro`) e o `tamanho` (quantidade de elementos). A lista começa vazia: `primeiro` aponta para `None` e `tamanho` é `0`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "98787d0e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:19.589643Z",
     "iopub.status.busy": "2026-09-28T17:16:19.589437Z",
     "iopub.status.idle": "2026-09-28T17:16:19.597745Z",
     "shell.execute_reply": "2026-09-28T17:16:19.596386Z"
    }
   },
   "outputs": [],
   "source": [
    "class ListaEncadeada:\n",
    "    def __init__(self):\n",
    "        self.primeiro = None\n",
    "        self.tamanho = 0\n",
    "\n",
    "    def esta_vazia(self):\n",
    "        return self.primeiro is None\n",
    "\n",
    "    def inserir_inicio(self, valor):\n",
    "        novo = No(valor)\n",
    "        novo.proximo = self.primeiro\n",
    "        self.primeiro = novo\n",
    "        self.tamanho += 1\n",
    "\n",
    "    def inserir_fim(self, valor):\n",
    "        novo = No(valor)\n",
    "        if self.esta_vazia():\n",
    "            self.primeiro = novo\n",
    "        else:\n",
    "            atual = self.primeiro\n",
    "            while atual.proximo is not None:\n",
    "                atual = atual.proximo\n",
    "            atual.proximo = novo\n",
    "        self.tamanho += 1\n",
    "\n",
    "    def imprimir(self):\n",
    "        atual = self.primeiro\n",
    "        partes = []\n",
    "        while atual is not None:\n",
    "            partes.append(str(atual.valor))\n",
    "            atual = atual.proximo\n",
    "        print(\" -> \".join(partes))\n",
    "\n",
    "    def pesquisar(self, valor):\n",
    "        atual = self.primeiro\n",
    "        while atual is not None:\n",
    "            if atual.valor == valor:\n",
    "                return atual\n",
    "            atual = atual.proximo\n",
    "        return None\n",
    "\n",
    "    def remover(self, valor):\n",
    "        if self.esta_vazia():\n",
    "            return \"Lista vazia\"\n",
    "\n",
    "        if self.primeiro.valor == valor:\n",
    "            self.primeiro = self.primeiro.proximo\n",
    "            self.tamanho -= 1\n",
    "            return \"Removido\"\n",
    "\n",
    "        anterior = self.primeiro\n",
    "        atual = self.primeiro.proximo\n",
    "        while atual is not None:\n",
    "            if atual.valor == valor:\n",
    "                anterior.proximo = atual.proximo\n",
    "                self.tamanho -= 1\n",
    "                return \"Removido\"\n",
    "            anterior = atual\n",
    "            atual = atual.proximo\n",
    "\n",
    "        return \"Não encontrado\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "022e1cab",
   "metadata": {},
   "source": [
    "### Testando a lista vazia\n",
    "\n",
    "Criamos uma lista e tentamos remover um elemento antes de inserir qualquer coisa.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ad6c5a4b",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:19.599912Z",
     "iopub.status.busy": "2026-09-28T17:16:19.599754Z",
     "iopub.status.idle": "2026-09-28T17:16:19.603455Z",
     "shell.execute_reply": "2026-09-28T17:16:19.602803Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A lista está vazia? True\n",
      "Lista vazia\n",
      "primeiro: None | tamanho: 0\n"
     ]
    }
   ],
   "source": [
    "lista = ListaEncadeada()\n",
    "print(\"A lista está vazia?\", lista.esta_vazia())\n",
    "print(lista.remover(10))\n",
    "print(\"primeiro:\", lista.primeiro, \"| tamanho:\", lista.tamanho)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f02ba484",
   "metadata": {},
   "source": [
    "### Inserindo no início\n",
    "\n",
    "Inserimos os caracteres do primeiro nome no **início**. Repare que a ordem de impressão é invertida em relação à ordem de inserção, e que cada inserção é **O(1)**.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "4396a8c7",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:19.605574Z",
     "iopub.status.busy": "2026-09-28T17:16:19.605306Z",
     "iopub.status.idle": "2026-09-28T17:16:19.610120Z",
     "shell.execute_reply": "2026-09-28T17:16:19.609320Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "R\n",
      "A -> R\n",
      "M -> A -> R\n",
      "O -> M -> A -> R\n",
      "N -> O -> M -> A -> R\n"
     ]
    }
   ],
   "source": [
    "for letra in \"RAMON\":\n",
    "    lista.inserir_inicio(letra)\n",
    "    lista.imprimir()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9f371a1",
   "metadata": {},
   "source": [
    "### Inserindo no final\n",
    "\n",
    "Para inserir no final é preciso **percorrer a lista** até o último nó, então essa operação é **O(n)**.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d71bcf50",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:19.612012Z",
     "iopub.status.busy": "2026-09-28T17:16:19.611792Z",
     "iopub.status.idle": "2026-09-28T17:16:19.615951Z",
     "shell.execute_reply": "2026-09-28T17:16:19.615260Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N -> O -> M -> A -> R\n",
      "N -> O -> M -> A -> R -> 10\n",
      "N -> O -> M -> A -> R -> 10 -> 20\n",
      "N -> O -> M -> A -> R -> 10 -> 20 -> 30\n"
     ]
    }
   ],
   "source": [
    "lista.imprimir()\n",
    "for valor in [10, 20, 30]:\n",
    "    lista.inserir_fim(valor)\n",
    "    lista.imprimir()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dadd68d1",
   "metadata": {},
   "source": [
    "### Pesquisando valores\n",
    "\n",
    "A pesquisa percorre a lista comparando os valores, retornando o **nó** encontrado ou `None`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c95b4a2d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:19.618250Z",
     "iopub.status.busy": "2026-09-28T17:16:19.617988Z",
     "iopub.status.idle": "2026-09-28T17:16:19.622689Z",
     "shell.execute_reply": "2026-09-28T17:16:19.621718Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Encontrado: 20\n",
      "Próximo: 30\n",
      "Busca por 99: None\n"
     ]
    }
   ],
   "source": [
    "no = lista.pesquisar(20)\n",
    "print(\"Encontrado:\", no.valor if no is not None else None)\n",
    "print(\"Próximo:\", no.proximo.valor if no.proximo else None)\n",
    "\n",
    "print(\"Busca por 99:\", lista.pesquisar(99))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "caa4ed1f",
   "metadata": {},
   "source": [
    "### Removendo elementos\n",
    "\n",
    "O método `remover` trata o primeiro nó separadamente e, para os demais, localiza o nó **anterior** e \"pula\" o nó a ser removido, ajustando a referência `proximo`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "52c34b43",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:19.625617Z",
     "iopub.status.busy": "2026-09-28T17:16:19.625271Z",
     "iopub.status.idle": "2026-09-28T17:16:19.631551Z",
     "shell.execute_reply": "2026-09-28T17:16:19.630869Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Antes: 5 -> 8 -> 12 -> 20\n",
      "Removido -> remoção do início\n",
      "8 -> 12 -> 20\n",
      "Removido -> remoção do meio\n",
      "8 -> 20\n",
      "Removido -> remoção do final\n",
      "8\n",
      "Não encontrado -> valor inexistente\n",
      "tamanho: 1\n"
     ]
    }
   ],
   "source": [
    "numeros = ListaEncadeada()\n",
    "for valor in [5, 8, 12, 20]:\n",
    "    numeros.inserir_fim(valor)\n",
    "\n",
    "print(\"Antes:\", end=\" \")\n",
    "numeros.imprimir()\n",
    "\n",
    "print(numeros.remover(5), \"-> remoção do início\")\n",
    "numeros.imprimir()\n",
    "\n",
    "print(numeros.remover(12), \"-> remoção do meio\")\n",
    "numeros.imprimir()\n",
    "\n",
    "print(numeros.remover(20), \"-> remoção do final\")\n",
    "numeros.imprimir()\n",
    "\n",
    "print(numeros.remover(99), \"-> valor inexistente\")\n",
    "print(\"tamanho:\", numeros.tamanho)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94379c6d",
   "metadata": {},
   "source": [
    "### Removendo o último elemento restante\n",
    "\n",
    "Quando sobra apenas um nó, ele é o `primeiro`, então a remoção esvazia a lista corretamente.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "5d0f65d4",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:19.633391Z",
     "iopub.status.busy": "2026-09-28T17:16:19.633197Z",
     "iopub.status.idle": "2026-09-28T17:16:19.636937Z",
     "shell.execute_reply": "2026-09-28T17:16:19.635945Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Antes: 8\n",
      "Removido\n",
      "A lista está vazia? True\n",
      "primeiro: None | tamanho: 0\n"
     ]
    }
   ],
   "source": [
    "print(\"Antes:\", end=\" \")\n",
    "numeros.imprimir()\n",
    "\n",
    "print(numeros.remover(8))\n",
    "print(\"A lista está vazia?\", numeros.esta_vazia())\n",
    "print(\"primeiro:\", numeros.primeiro, \"| tamanho:\", numeros.tamanho)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa93fcea",
   "metadata": {},
   "source": [
    "### Resumo\n",
    "\n",
    "- A lista encadeada é **dinâmica** e formada por **nós**.\n",
    "- Cada nó tem um `valor` e uma referência `proximo`.\n",
    "- O `primeiro` aponta para o primeiro nó; `None` indica o fim da lista.\n",
    "- Inserir/remover no **início** é **O(1)**; pesquisar e percorrer é **O(n)**.\n",
    "- Não existe `capacidade` nem `esta_cheia()`: a lista cresce enquanto houver memória.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}