{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "acb51be1",
   "metadata": {},
   "source": [
    "## Listas Duplamente Encadeadas em Python\n",
    "\n",
    "Neste notebook vamos implementar uma **lista duplamente encadeada**: uma estrutura dinâmica em que cada nó guarda um valor e **duas referências** — para o **próximo** nó (`proximo`) e para o **anterior** (`anterior`).\n",
    "\n",
    "Além do `primeiro`, a lista também guarda o `ultimo` (último nó), o que permite inserir e remover nas duas extremidades em **O(1)**.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2497c057",
   "metadata": {},
   "source": [
    "### A classe `No`\n",
    "\n",
    "O nó é o bloco básico da lista. Agora ele possui os atributos `valor`, `proximo` e `anterior`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "74fa8b91",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:23.644221Z",
     "iopub.status.busy": "2026-09-28T17:16:23.644029Z",
     "iopub.status.idle": "2026-09-28T17:16:23.651144Z",
     "shell.execute_reply": "2026-09-28T17:16:23.650170Z"
    }
   },
   "outputs": [],
   "source": [
    "class No:\n",
    "    def __init__(self, valor):\n",
    "        self.valor = valor\n",
    "        self.proximo = None\n",
    "        self.anterior = None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a801f434",
   "metadata": {},
   "source": [
    "### A classe `ListaDuplamenteEncadeada`\n",
    "\n",
    "A lista começa **vazia**: `primeiro` e `ultimo` apontam para `None` e `tamanho` é `0`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1f10542",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:23.653711Z",
     "iopub.status.busy": "2026-09-28T17:16:23.653483Z",
     "iopub.status.idle": "2026-09-28T17:16:23.662221Z",
     "shell.execute_reply": "2026-09-28T17:16:23.661234Z"
    }
   },
   "outputs": [],
   "source": [
    "class ListaDuplamenteEncadeada:\n",
    "    def __init__(self):\n",
    "        self.primeiro = None\n",
    "        self.ultimo = 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",
    "        if self.esta_vazia():\n",
    "            self.ultimo = novo\n",
    "        else:\n",
    "            self.primeiro.anterior = novo\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",
    "            self.ultimo.proximo = novo\n",
    "            novo.anterior = self.ultimo\n",
    "        self.ultimo = novo\n",
    "        self.tamanho += 1\n",
    "\n",
    "    def imprimir_frente(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 imprimir_tras(self):\n",
    "        atual = self.ultimo\n",
    "        partes = []\n",
    "        while atual is not None:\n",
    "            partes.append(str(atual.valor))\n",
    "            atual = atual.anterior\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",
    "        atual = self.primeiro\n",
    "        while atual is not None and atual.valor != valor:\n",
    "            atual = atual.proximo\n",
    "\n",
    "        if atual is None:\n",
    "            return \"Não encontrado\"\n",
    "\n",
    "        if atual.anterior is None:\n",
    "            self.primeiro = atual.proximo\n",
    "        else:\n",
    "            atual.anterior.proximo = atual.proximo\n",
    "\n",
    "        if atual.proximo is None:\n",
    "            self.ultimo = atual.anterior\n",
    "        else:\n",
    "            atual.proximo.anterior = atual.anterior\n",
    "\n",
    "        self.tamanho -= 1\n",
    "        return \"Removido\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e89e283",
   "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": null,
   "id": "63ef2b8a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:23.664386Z",
     "iopub.status.busy": "2026-09-28T17:16:23.664224Z",
     "iopub.status.idle": "2026-09-28T17:16:23.668304Z",
     "shell.execute_reply": "2026-09-28T17:16:23.667241Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A lista está vazia? True\n",
      "Não encontrado\n",
      "primeiro: None | ultimo: None | tamanho: 0\n"
     ]
    }
   ],
   "source": [
    "lista = ListaDuplamenteEncadeada()\n",
    "print(\"A lista está vazia?\", lista.esta_vazia())\n",
    "print(lista.remover(10))\n",
    "print(\"primeiro:\", lista.primeiro, \"| ultimo:\", lista.ultimo, \"| tamanho:\", lista.tamanho)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a41ce08",
   "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.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b47862fb",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:23.670075Z",
     "iopub.status.busy": "2026-09-28T17:16:23.669916Z",
     "iopub.status.idle": "2026-09-28T17:16:23.673692Z",
     "shell.execute_reply": "2026-09-28T17:16:23.673023Z"
    }
   },
   "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 \"PROFESSOR\":\n",
    "    lista.inserir_inicio(letra)\n",
    "    lista.imprimir_frente()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ebac3ed",
   "metadata": {},
   "source": [
    "### Inserindo no final\n",
    "\n",
    "Como a lista guarda o `ultimo`, a inserção no final é **O(1)**.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e07c3a1e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:23.675596Z",
     "iopub.status.busy": "2026-09-28T17:16:23.675418Z",
     "iopub.status.idle": "2026-09-28T17:16:23.679898Z",
     "shell.execute_reply": "2026-09-28T17:16:23.679148Z"
    }
   },
   "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_frente()\n",
    "for valor in [10, 20, 30]:\n",
    "    lista.inserir_fim(valor)\n",
    "    lista.imprimir_frente()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a9cc98d",
   "metadata": {},
   "source": [
    "### Percorrendo nos dois sentidos\n",
    "\n",
    "Podemos imprimir do início para o fim (usando `proximo`) e do fim para o início (usando `anterior`).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ff27a146",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:23.681698Z",
     "iopub.status.busy": "2026-09-28T17:16:23.681539Z",
     "iopub.status.idle": "2026-09-28T17:16:23.685142Z",
     "shell.execute_reply": "2026-09-28T17:16:23.684545Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Do início para o fim:\n",
      "N <-> O <-> M <-> A <-> R <-> 10 <-> 20 <-> 30\n",
      "Do fim para o início:\n",
      "30 <-> 20 <-> 10 <-> R <-> A <-> M <-> O <-> N\n"
     ]
    }
   ],
   "source": [
    "print(\"Do início para o fim:\")\n",
    "lista.imprimir_frente()\n",
    "\n",
    "print(\"Do fim para o início:\")\n",
    "lista.imprimir_tras()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a02b21f",
   "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": null,
   "id": "51e7c193",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:23.686899Z",
     "iopub.status.busy": "2026-09-28T17:16:23.686713Z",
     "iopub.status.idle": "2026-09-28T17:16:23.690458Z",
     "shell.execute_reply": "2026-09-28T17:16:23.689855Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Encontrado: 20\n",
      "Anterior: 10\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(\"Anterior:\", no.anterior.valor if no.anterior 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": "c8936b44",
   "metadata": {},
   "source": [
    "### Removendo elementos\n",
    "\n",
    "O método `remover` trata os quatro casos: primeiro nó, último nó, nó do meio e nó único. Observe como `primeiro` e `ultimo` são atualizados.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "86cca091",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:23.692603Z",
     "iopub.status.busy": "2026-09-28T17:16:23.692305Z",
     "iopub.status.idle": "2026-09-28T17:16:23.696325Z",
     "shell.execute_reply": "2026-09-28T17:16:23.695624Z"
    }
   },
   "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 = ListaDuplamenteEncadeada()\n",
    "for valor in [5, 8, 12, 20]:\n",
    "    numeros.inserir_fim(valor)\n",
    "\n",
    "print(\"Antes:\", end=\" \")\n",
    "numeros.imprimir_frente()\n",
    "\n",
    "print(numeros.remover(5), \"-> remoção do início\")\n",
    "numeros.imprimir_frente()\n",
    "\n",
    "print(numeros.remover(12), \"-> remoção do meio\")\n",
    "numeros.imprimir_frente()\n",
    "\n",
    "print(numeros.remover(20), \"-> remoção do final\")\n",
    "numeros.imprimir_frente()\n",
    "\n",
    "print(numeros.remover(99), \"-> valor inexistente\")\n",
    "print(\"tamanho:\", numeros.tamanho)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e98dda5",
   "metadata": {},
   "source": [
    "### Removendo o último elemento restante\n",
    "\n",
    "Quando sobra apenas um nó, `anterior` e `proximo` são `None`, e o mesmo algoritmo esvazia a lista corretamente.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e4f8b20",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:16:23.698103Z",
     "iopub.status.busy": "2026-09-28T17:16:23.697919Z",
     "iopub.status.idle": "2026-09-28T17:16:23.701761Z",
     "shell.execute_reply": "2026-09-28T17:16:23.700833Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Antes: 8\n",
      "Removido\n",
      "A lista está vazia? True\n",
      "primeiro: None | ultimo: None | tamanho: 0\n"
     ]
    }
   ],
   "source": [
    "print(\"Antes:\", end=\" \")\n",
    "numeros.imprimir_frente()\n",
    "\n",
    "print(numeros.remover(8))\n",
    "print(\"A lista está vazia?\", numeros.esta_vazia())\n",
    "print(\"primeiro:\", numeros.primeiro, \"| ultimo:\", numeros.ultimo, \"| tamanho:\", numeros.tamanho)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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
}