O TEMA DO FÓRUM ESTÁ EM MANUTENÇÃO. FEEDBACKS AQUI: ACESSAR

Estruturas de dados 101 - Introdução a ponteiros & Listas Ligadas

Iniciado por Brandt, 26/06/2019 às 19:43

Imprimir
Ir para o fim Páginas1
Ações
26/06/2019 às 19:43 Última edição: 10/01/2020 às 16:43 por Brandt
Estruturas de dados 101



[box class=roundframe padding] [box class=floatleft send_topic padding][/box]

Oi \o

Faz um tempo que não posto nada, então pra matar a saudade, decidi montar um aulinha pra falar sobre um assunto que eu acho bem relevante pra área de computação e que raramente se ouve falar nas comunidades de RPG Maker:
estruturas de dados.

Inicialmente, eu ia criar um tópico só com todo o conteúdo, mas notei que estava crescendo demais (tipo, muito mesmo), então decidi por dividir as coisas.

[/box]

Sumário



1 Introdução



[box class=errorbox padding][box class=floatright send_topic padding][/box] Disclaimer: Eu não sou especialista em nada do que falo aqui.

Estudei computação e aplico esse conhecimento no dia a dia no trabalho, logo sinto-me relativamente à vontade para expor o que eu sei, mas é bem possível que eu cometa erros por aqui.

Se acontecer, podem dar um toque! (e por favor, deem!)[/box]

1.1 Então, o que são estruturas de dados?

Quando falamos em programas de computador, temos duas unidades fundamentais: algoritmos e dados. Os algoritmos são procedimentos desenvolvidos para resolver certo problema, e os dados são a forma que usamos para representar as variáveis desse problema no
computador.

Podemos adotar a analogia de que, enquanto os algoritmos são o "como?" e os dados são o "o quê?".

Dessa forma, podemos pensar em dados como "coisas" que temos na memória. As estruturas de dados são formas de colocar dados complexos na memória, e também geralmente fazê-lo de forma que seu uso traga vantagens do ponto de vista
algorítmico (tornando uma busca em um conjunto mais rápida, por exemplo).

Fica mais fácil ver isso quando você entende de fato esse negócio de "memória" e vê as estruturas de fato, e porque usamos cada uma delas, então não vou me estender muito aqui.

1.2 E o que é a memória?

[box class=description padding][box class=floatleft send_topic padding][/box] Nota: Essa parte trata principalmente de como as coisas ficam na memória do computador, como funciona o famoso "binário" que o computador entende e, frente a tudo isso, o que são ponteiros. Se você já tem noções
dessas coisas, pule para a lista ligada[/box]

Para fins práticos, nós vamos entender a memória como um vetor de bits, ou uma sequência arbitrariamente longa de 0s e 1s. Claramente, em um computador de verdade existe muito mais que isso, e temos algumas limitações (de espaço, por exemplo), mas essa aproximação serve pro que precisamos aqui.

Veja que é fácil quebrar a memória em blocos de 8 para formar números de 8 bits. Chamaremos esse número (que vai de 0 a 255) de "byte".

É relativamente fácil, usando bytes, representar números e até mesmo texto:

  • Suponha que queiramos o número 1729, podemos montá-lo com dois bytes: 00000110 11000001
  • Agora queremos o texto "ABC". Usando a tabela ASCII, criamos: 01000001 01000010 01000011
  • Podemos até criar listas na memória, se definirmos o tamanho de cada elemento: 00000110 11000001 01000001 01000010 01000011 pode ser uma lista de bytes [6, 193, 65, 66, 67]
1.2.1 Brincando com a memória

Beleza, vimos que conseguimos criar números e texto na memória separadamente. Mas e se quisermos juntar um número e um texto numa mesma "coisa"?

Suponhamos que queremos uma "Pessoa", que é dada por uma idade e um nome.

Notação:

Pessoa = { idade: byte, nome: string }

Podemos criar então uma sequência assim na memória:

00010010 01001101 01100001 01110011 01101011 01100101 01100100 00000000

... Pera, quê?

Não é óbvio o que acontece aí, mas se olharmos mais de perto, dá pra ver o seguinte:

  • 00010010 = 18. A idade da nossa pessoa.
  • 01001101 01100001 01110011 01101011 01100101 01100100 = 77 97 115 107 101 100, que com a tabela ASCII transformamos em Masked. O nome da nossa pessoa.
O 00000000 no final é usado para determinar onde a string do nome da pessoa termina, já que nós não sabemos de antemão seu tamanho, e a memória não faz mágica.

Olha que louco, já conseguimos criar pessoas na memória do computador! (kind of)

[box class=highlight2 padding] [box class=floatright send_topic padding][/box] Exercício!

Como ficaria uma estrutura de pessoa com nome e sobrenome na memória? [/box]

1.2.2 Vetores

Mais uma ideia: e se quisermos uma pessoa que possa ter um irmão?

Com o que já sabemos, podemos criar mais um pedaço de dados dentro da pessoa para fazer isso:

Pessoa = {
    idade: byte,
    nome: string,
    irmão: { idade: byte, nome: string }
}

Aí o nosso carinha de exemplo fica assim:

00010010 01001101 01100001 01110011 01101011 01100101 01100100 00000000             // { idade: 18, nome: "Masked"
00001001 01001110 01101001 01101110 01100101 01001011 00000000                      // irmão: { idade: 9, nome: "NineK" } }

Maneiro, e se quisermos colocar mais e mais irmãos na história, podemos sempre botar mais uma pessoa logo ao lado:

00010010 01001101 01100001 01110011 01101011 01100101 01100100 00000000             // { idade: 18, nome: "Masked"
00001001 01001110 01101001 01101110 01100101 01001011 00000000                      // irmão: { idade: 9, nome: "NineK" },
00001001 01001011 01100001 01110111 01110100 01101000 01100001 01110010 00000000    // irmão2: { idade: 9, nome: "Kawthar" } }

Podemos encarar isso também como um vetor em memória de pessoas. Porém, temos um problema: para vetores, é interessante sabermos o tamanho de cada elemento na memória, de forma que conseguimos achar qualquer elemento nele só pela posição.

[box class=highlight2 padding] [box class=floatright send_topic padding][/box] Exercício!

Tente desenvolver um algoritmo que encontre o n-ésimo elemento desse vetor.

[/box]

Mas nossa Pessoa não tem um tamanho fixo: o nome pode ter quantas letras quisermos, e seu fim é indicado apenas pelo byte nulo (00000000)

Uma solução seria fixar o tamanho do nome da pessoa (limitar a 30, por exemplo, pode servir), mas nem sempre queremos/podemos fazer isso.

E agora?

1.2.3 Ponteiros

Aí entram os ponteiros!

Lembre que a memória é uma lista de bits. Se ela é uma lista, podemos acessar os elementos dela pela posição. Quando guardamos uma posição da memória como um número, chamamos ela de ponteiro.

O legal pro nosso caso é que o ponteiro tem tamanho fixo, então podemos criar uma estrutura assim:

Pessoa = {
  idade: byte,
  nome: string* // Ponteiro para uma string
}

E nosso vetor de Pessoas então vai ter elementos que tem sempre 1 byte + o tamanho do ponteiro. Geralmente, ponteiros tem 4 ou 8 bytes, variando com a implementação do sistema (32-bit ou 64-bit). Aqui, nosso ponteiro terá 1 byte, porque já dá pro gasto.

O vetor de antes ficaria assim:

// [
//  { idade: 18, nome: ponteiro[00101010] },
//  { idade: 9, nome: ponteiro[01101010] },
//  { idade: 9, nome: ponteiro[10101010] }
// ]
00010010 00101010 00001001 01101010 00001001 10101010

E aí nos endereços 00101010, 01101010 e 10101010:

// [00101010]
01001101 01100001 01110011 01101011 01100101 01100100 00000000                    // Masked
[...]

// [01101010]
01001110 01101001 01101110 01100101 01001011 00000000                             // NineK
[...]

// [10101010]
00001001 01001011 01100001 01110111 01110100 01101000 01100001 01110010 00000000  // Kawthar

De maneira mais abstrata, podemos ver esse vetor como algo assim:

[box class=highlight2 padding] [box class=floatleft send_topic padding][/box] Exercício!

Se tivermos o ponteiro do vetor que criamos, como podemos, sem percorrer nada, pegar o ponteiro para o segundo elemento nele? E o terceiro?  [/box]

Que tal agora o seguinte: pra toda pessoa, queremos que ela possa ter um irmão, mas esse irmão possa ter um outro irmão também, que possa ter outro irmão, e assim por diante. Ou seja, cada irmão é uma pessoa também:

Pessoa = {
    idade: byte,
    nome: string,
    irmão: Pessoa
}

Mas é meio complicado definirmos uma Pessoa assim, porque toda pessoa teria que ter outra pessoa dentro, que teria outra, que teria outra...

O jeito de resolver isso é usando ponteiros!

Notação:

Pessoa = {
    idade: byte,
    nome: string,
    irmão: Pessoa* // Ponteiro para uma pessoa
}

E aí podemos criar o seguinte em um lugar qualquer na memória:

// { idade: 18, nome: "Masked", irmão: ponteiro[00101010] }
00010010 01001101 01100001 01110011 01101011 01100101 01100100 00000000 00101010

E então na posição 00101010 (42) da memória:

// { idade: 9, nome: "NineK", irmão: ponteiro[01101010] }
00001001 01001110 01101001 01101110 01100101 01001011 00000000 01101010

E depois na posição 01101010 (106) da memória:

// { idade: 9, nome: "Kawthar", irmão: null }
00001001 01001011 01100001 01110111 01110100 01101000 01100001 01110010 00000000 00000000

Onde null é um ponteiro para a posição 0, indicando a ausência de um irmão.

[box class=highlight2 padding] [box class=floatright send_topic padding][/box]Exercício!

Crie um vetor de pessoas com irmãos, usando o que vimos até agora. Veja que você pode representar uma família só com a primeira pessoa, já que ela tem ponteiros para os outros.
[/box]

2 Eis a lista ligada



Tadaaa \o/

Aprendemos nossa primeira (sem contar a Pessoa e o vetor) estrutura de dados.

Listas ligadas são uma alternativa flexível para vetores em memória: em uma lista ligada, inserir e remover elementos no meio da lista e adicionar quantos elementos for necessário é bem simples, enquanto que em vetores na memória pode ser
necessário deslocar e realocar memória para fazer isso.

Podemos definir uma lista ligada, de forma genérica, por:

ListaLigada = {
  primeiroNó: Nó*
}

Nó = {
  dado: ???, // Qualquer coisa, pra gente tanto faz.
  próximo: Nó*
}

Uma lista ligada pode ser vista, de forma abstrata, da seguinte forma:



Onde as caixas representam os "nós" (elementos) da lista, e as setas representam os ponteiros entre eles.

[box class=valid_input padding][box class=floatright send_topic padding][/box] Veja só

Os ponteiros são para uma direção apenas: o primeiro nó sabe onde está o próximo, mas este não sabe onde está o que veio antes dele.

É possível criar uma lista onde todo elemento sabe quem vem depois e quem vem antes (uma lista duplamente ligada), basta adicionar um ponteiro para o anterior em cada nó.

Infelizmente, isso adiciona complexidade à lista, uma vez que temos que garantir a estabilidade também do ponteiro do nó anterior.

Não implementaremos listas duplamente ligadas aqui, mas é um exercício interessante de se fazer uma vez que você dominar a lista ligada! [/box]

2.1 Operações

[box class=description padding][box class=floatright send_topic padding][/box] Nota: Por motivos de cansei de escrever 0 e 1 e praticidade, daqui pra frente não estaremos usando a memória diretamente como estávamos antes. Mesmo assim, todos os conceitos ainda se aplicam.

Seguiremos com pseudocódigo para demonstrar os algoritmos para as operações das estruturas de dados.[/box]

2.1.1 Travessia

Fazer uma travessia (percorrer) em uma lista ligada é a operação mais simples, e envolve simplesmente seguir os ponteiros da lista a partir do primeiro nó.

Um algoritmo para isso, tendo em vista nossa definição, seria:

def percorre(lista: ListaLigada):
    atual = lista.primeiroNó

    while atual != null:
        // Fazemos alguma coisa usando o nó aqui...
        atual = atual.próximo

Percorrer a lista, por si só, não traz nenhum ganho. Mas podemos usar a travessia para trabalhar em cima dos nós da lista.

Um exemplo de algoritmo que usa a travessia seria a soma dos números de uma lista:

def soma(lista: ListaLigada):
    total = 0
    atual = lista.primeiroNó

    while atual != null:
        total += atual.dado
        atual = atual.próximo

    return total

[box class=valid_input padding][box class=floatleft send_topic padding][/box] Veja só

Por conta da natureza dos ponteiros, a travessia da lista ligada acontece do primeiro nó para o último, a não ser que a lista seja duplamente ligada. [/box]

[box class=highlight2 padding] [box class=floatright send_topic padding][/box]  Exercício!

Usando a travessia, crie um algoritmo que calcula a média aritmética dos números em uma lista ligada.  [/box]

2.1.2 Inserção

Em linhas gerais, a inserção da lista ligada consiste apenas em manipular os ponteiros dos nós da lista e do que está sendo inserido.

A forma como isso acontece é um pouco diferente para inserção de nós no começo, no fim e no meio da lista, então veremos esses casos separadamente.

2.1.2.1 Inserção no começo

A inserção no começo da lista também é bem simples: precisamos colocar um novo primeiroNó. Só temos que nos preocupar em colocar o primeiro nó antigo logo depois do novo!

O algoritmo:

def insereNoComeço(lista: ListaLigada*, novoNó: Nó):
    novoNó.proximo = lista.primeiroNó
    lista.primeiroNó = novoNó

2.1.2.2 Inserção no meio

Para inserir um nó no meio da lista, só precisamos de outro nó que esteja na lista. Esse nó não necessariamente precisa ser o primeiro, qualquer nó serve.

Isso acontece porque, para esse caso, precisamos apenas poder modificar o nó e saber qual nó vem após ele.

Um algoritmo simples para isso seria:

def insereDepois(noDaLista: Nó*, novoNó: Nó*):
    novoNó.proximo = noDaLista.proximo
    noDaLista.proximo = novoNó

Não existem muitos casos especiais aqui, é só isso mesmo.

[box class=valid_input padding][box class=floatright send_topic padding][/box] Veja só

Esse algoritmo insere o novo nó após o nó que passamos (e, inclusive, serve para inserir ao fim! Você vê porquê?). Para inserir antes de dado nó, precisaríamos que nossa lista fosse duplamente ligada, e teríamos que tratar o caso especial em que inserimos o nó no começo da lista.
[/box]

2.1.2.3 Inserção no fim

Para inserir um elemento ao fim de um lista ligada, intuitivamente o que precisamos fazer é colocar o ponteiro do nó que queremos inserir, no ponteiro do próximo do último nó da lista.

Usando nossa definição da lista ligada, podemos criar uma função assim:

def insereNoFim(lista: ListaLigada, novoNó: Nó*):
    nóAtual = lista.primeiroNó

    while nóAtual.próximo != null:
        nóAtual = nóAtual.próximo

    nóAtual.próximo = novoNó

Olha só! Essa função faz o que precisamos, certo?

Fica mais fácil de ver se você pensar que o primeiro nó sem próximo deve, com certeza, ser o último nó da lista. Assim, nosso algoritmo procura esse nó e define o ponteiro do próximo para o ponteiro do nó que queremos inserir.

Pronto, certo? Ainda não. Falta um caso especial: e se a lista estiver vazia?

Se a lista estiver vazia, o primeiroNó é nulo, certo? E nesse caso, o que queremos na verdade é colocar o nosso nó como o primeiro mesmo (o fim de uma lista vazia é o começo, certo?).

Nosso algoritmo fica então:

def insereNoFim(lista: ListaLigada, novoNó: Nó*):
    if lista.primeiroNó == null:
        lista.primeiroNó = novoNó
    else:
        nóAtual = lista.primeiroNó

        while nóAtual.próximo != null:
            nóAtual = nóAtual.próximo

        nóAtual.próximo = novoNó

Esse algoritmo funciona para todos os casos da nossa lista! (Exceto o caso em que não existe último nó, mas veremos isso mais pra frente)

[box class=valid_input padding][box class=floatleft send_topic padding][/box] Veja só

Existe ainda mais uma melhoria que podemos fazer em relação à performance desse código: veja que esse algoritmo precisa percorrer toda a lista antes de inserir um nó no fim.

Isso fica bem ruim quando nossa lista fica muito grande.

Mas nós podemos fazer todo esse processo em tempo constante, ou seja, se nossa lista tiver dez ou dez milhões de elementos, o tempo será o mesmo. Isso pode ser feito com um ponteiro na lista para o último nó! [/box]

Uma lista com ponteiro para o último nó é praticamente igual à original, mas com mais um ponteiro:

ListaLigada = {
   primeiroNó: Nó*,
   últimoNó: Nó*
}

[box class=description padding][box class=floatleft send_topic padding][/box] Nota: O esforço de colocar esse nó a mais é quase nulo, e ele simplifica bastante a inserção no fim. Mas ele pode tornar as outras inserções mais complicadas, porque temos sempre que atualizar o ponteiro quando a lista
estava vazia.

Por isso, vamos seguir usando nossa definição de lista com apenas um ponteiro. A implementação das inserções com essa nova definição fica por conta do leitor.

Aliás... [/box]

[box class=highlight2 padding] [box class=floatright send_topic padding][/box]  Exercício!

Crie um algoritmo para cada inserção que vimos usando a nossa lista com ponteiro para o último nó. Veja o que muda em cada um.  [/box]

2.1.2.4 Inserção em ordem

Em diversos casos, é interessante que nossa lista esteja ordenada.

Para essa inserção em específico, vamos assumir que lista já está ordenada, especificamente em ordem crescente, embora as mudanças necessárias para contar com ordem decrescente sejam desprezíveis.

Mas veja que uma lista vazia, ou com apenas um elemento, é claramente ordenada. Assim, podemos criar listas ligadas ordenadas facilmente, se inserirmos todos os elementos na lista dessa forma.

De todo modo, eu gostaria de dizer que existe alternativa melhor, mas o melhor algoritmo para inserção em ordem em listas ligadas é o mais besta mesmo: procura-se o primeiro elemento maior que o que estamos inserindo na lista,
e insere-se o novo valor logo atrás dele.

Basicamente, nosso algoritmo é o seguinte:

def insereEmOrdem(lista: ListaOrdenada, novoNó: Nó*):
    if lista.primeiroNó.dado > novoNó.dado:
        novoNó.próximo = lista.primeiroNó
        lista.primeiroNó = novoNó
    else:
        anterior = lista.primeiroNó
        atual = anterior.próximo

        while atual != null && atual.dado <= novoNó.dado:
            anterior = atual
            atual = atual.próximo

        insereDepois(anterior, novoNó)

Claramente, se nosso primeiro elemento é maior que o que queremos inserir, inserimos ele no começo da lista. Caso contrário, avançamos os ponteiros de anterior e atual até encontrarmos um atual cujo dado é maior que o do novoNó.

Assim, inserimos o novoNó logo após o anterior, e temos uma inserção em ordem.

[box class=highlight2 padding] [box class=floatright send_topic padding][/box]  Exercício!

Adapte essa inserção para manter a lista em ordem decrescente.  [/box]

2.1.2.5 Inserção de lista

As listas ligadas tem uma propriedade muito interessante, que inclusive é uma de suas grandes vantagens em relação a vetores em memória, por exemplo: podemos inserir listas ao começo, no meio e ao fim de outras listas da mesma forma que
inserimos nós!

Louco né? Deixa eu explicar.

Nos três primeiros algoritmos de inserção que fizemos (a inserção em ordem não funciona aqui, infelizmente), contamos apenas com uma propriedade dos nós da lista: eles têm um ponteiro para o próximo (que pode ser nulo).

Mas se essa é a única propriedade de que dependemos, então veja que uma lista ligada pode ser vista como um "nó" também: podemos inserir seu primeiroNó como o próximo de outro nó, e podemos definir o ponteiro próximo de seu último nó para outro nó também.

Fica mais claro com imagens. Imagine as seguintes listas ligadas:



Podemos facilmente inserir a lista B no começo, no meio ou no fim da lista A, mudando apenas os ponteiros de primeiroNó ou próximo de algum nó em A, e próximo do último nó de B. Veja:

[box title=No começo]
Inserção no começo: O primeiroNó de A vira Pet (primeiroNó de B), o próximo do último nó de B vira Masked (primeiroNó de A).
[/box]

[box title=No meio]
Inserção no meio: Para inserir a lista B entre Masked e NineK, mudamos o próximo de Masked para o primeiro de B, e o próximo do último de B para NineK.
[/box]

[box title=No fim]
Inserção no fim: o processo é quase idêntico à inserção de B no começo de A, mas neste caso inserimos A no começo de B.
[/box]

Às operações de inserção de lista no começo e no fim, damos o nome especial de concatenação. A concatenação de listas ligadas é bem simples, e o algoritmo é trivial uma vez que definimos a inserção de nós no fim de listas:

def concatena(listaA: ListaLigada, listaB: listaLigada):
  insereNoFim(listaA, listaB.primeiroNó)

Veja que esse algoritmo já cobre a inserção no começo e no fim, pois podemos inverter a ordem dos parâmetros:

concatena(A, B) // Insere B ao fim de A
concatena(B, A) // Insere B ao começo de A, ou A ao fim de B. Dá no mesmo.

A inserção de lista no meio de outra lista pode parecer mais complexa, mas também é fácil de implementar usando as funções que já temos:

def insereListaDepois(nó: Nó*, lista: ListaLigada):
  insereNoFim(lista, nó.próximo)
  nó.próximo = lista.primeiroNó

Observe que a inserção de listas sempre usa inserções ao fim. Isso indica que a concatenação de listas é muito mais eficiente em listas ligadas com ponteiro para o último nó.

[box class=highlight2 padding] [box class=floatright send_topic padding][/box]  Exercício!

Implemente uma inserção de lista ligada para listas com ponteiro para o fim.

Lembre de tratar com cuidado o caso em que mudamos o último nó da lista.  [/box]

2.1.3 Remoção

A remoção na lista ligada é um processo bem simples na maioria dos casos, e é bem fácil vê-la como um processo inverso à inserção mesmo.

O que faremos nos algoritmos de remoção é, basicamente, fazer o ponteiro do nó anterior apontar direto para o próximo. Assim, "pulamos" o nó que está sendo removido, efetivamente tirando ele da lista.

Assim como a inserção, a remoção pode ser dividida em casos:

2.1.3.1 Remoção no começo

Para a remoção no começo, nosso primeiro nó sai da lista. Esse é um caso bem simples, já que podemos resolver isso simplesmente mudando nosso ponteiro do primeiro nó para o próximo:

def removeDoComeço(lista: ListaLigada):
    lista.primeiroNó = lista.primeiroNó.próximo

[box class=valid_input padding][box class=floatright send_topic padding][/box] Veja só

Para a lista com ponteiro para o último, essa remoção tem um caso especial: quando o primeiro nó é também o último.

Nesse caso, temos que mudar o ponteiro do último nó também. Isso é bem simples, visto que se o primeiro nó é o último, ao removê-lo temos uma lista vazia, e então primeiroNó = últimoNó = null. [/box]

2.1.3.2 Remoção no meio

Vamos definir nosso algoritmo de remoção de forma parecida com a inserção no meio:

def removeDepois(nó: Nó*):
    nó.próximo = nó.próximo.próximo

De forma análoga à inserção no meio, nosso algoritmo remove um nó que vem após outro.

Veja que é necessário saber o nó anterior ao que queremos remover para fazer esse "pulo" com os ponteiros.

[box class=valid_input padding][box class=floatright send_topic padding][/box] Veja só

A depender da implementação, você pode querer ter certeza que existe nó após o nó que usamos de base para a remoção. Isso porque se esse próximo for null, teremos problemas para acessar próximo.próximo. [/box]

2.1.3.3 Remoção no fim

Um algoritmo que remove ao fim consiste em dois passos: encontrar o nó anterior ao último, e definir seu próximo como nulo.

A implementação disso é a seguinte:

def removeDoFim(lista: ListaLigada):
    anterior = null
    nóAtual = lista.primeiroNó

    while nóAtual.próximo != null:
        anterior = nóAtual
        nóAtual = nóAtual.próximo

    anterior.próximo = null

Esse é um pouco mais complicado que os outros, mas também não deve ser um problema muito grande: veja que, no começo, usamos a mesma repetição que usamos para achar o último nó na inserção no fim, com um adicional: o ponteiro
anterior.

Esse ponteiro anterior é essencial para realizarmos a remoção, como vimos no caso da remoção no meio da lista.

Esse algoritmo, porém, não trata do caso em que a lista tem apenas um nó (i.e. o primeiro nó é o último). Podemos corrigir isso:

def removeDoFim(lista: ListaLigada):
    if lista.primeiroNó.próximo == null:
        lista.primeiroNó = null
    else:
        anterior = null
        nóAtual = lista.primeiroNó

        while nóAtual.próximo != null:
            anterior = nóAtual
            nóAtual = nóAtual.próximo

        anterior.próximo = null

O algoritmo é o mesmo, mas no caso em que o próximo do primeiroNó é nulo, ele define que o primeiroNó seja nulo.

Se pensarmos na própria lista como um "nó" anterior a todos os outros, cujo próximo é o primeiroNó, esse caso é basicamente igual ao outro.

[box class=valid_input padding][box class=floatright send_topic padding][/box] Veja só

Esse algoritmo é trivial e pode ser executado em tempo constante se nossa lista for duplamente ligada e com ponteiro para o final. [/box]

[box class=highlight2 padding] [box class=floatleft send_topic padding][/box]  Exercício!

Tente implementar os algoritmos de remoção com listas duplamente ligadas e com ponteiro para o último nó. Cuidado com os casos especiais.  [/box]

[box class=highlight2 padding] [box class=floatright send_topic padding][/box]  Exercício!

Usando a travessia e as remoções que aprendemos, crie um algoritmo que, dado um valor, procura ele na lista e remove o nó correspondente.  [/box]

2.2 Propriedades recursivas da lista ligada

Uma lista ligada pode ser definida sem uso de uma classe especial para nó. Isso é feito da seguinte forma:

ListaLigada = {
  dado: ???,
  sublista: ListaLigada*
}

Veja que, nessa definição, o dado está diretamente na lista, e o que seria o próximoNó é uma sublista.

Essa definição é possível porque o conjunto de todos os nós após o primeiro em uma lista ligada ainda é uma lista ligada. Leva um tempinho pra digerir, mas quando você entende fica bem intuitivo.

Os algoritmos para a lista ligada podem também ser definidos de forma recursiva. Nosso algoritmo para inserção ao fim com essa definição, por exemplo, seria:

def insereNoFim(lista: ListaLigada, sublista: ListaLigada*):
  if listaLigada.sublista == null:
    listaLigada.sublista = sublista
  else:
    insereNoFim(listaLigada.sublista, sublista)

[box class=highlight2 padding] [box class=floatright send_topic padding][/box]  Exercício!

Tente implementar os algoritmos que já vimos de forma recursiva! Você pode usar tanto a definição recursiva de lista que criamos quando a original, já que as duas são equivalentes.
[/box]

[box class=description padding][box class=floatleft send_topic padding][/box]

Nota: Daqui pra baixo até a fila, temos conteúdo extra com alguns algoritmos recursivos para listas ligadas.

Esses algoritmos não são essenciais para o seu entendimento de listas ligadas (existem alternativas não-recursivas praticamente triviais para eles), mas são um exercício bem interessante pra quem quer aprender a lidar com recursão!

Mas só pra não dizerem que não avisei, talvez eu me empolgue (risos)

[/box]

2.2.1 (Bônus) Ordenação de listas ligadas com recursão

Quando tratamos de listas, é comum querermos ordenar uma lista não ordenada.

Para isso, com listas ligadas, temos basicamente duas opções: ordenar por inserção, percorrendo a lista e inserindo (usando inserção em ordem) cada elemento em outra lista, ou ordenar de forma recursiva.

A ordenação por inserção é simples, e fica como exercício implementá-la. Já a ordenação recursiva é um pouco mais complicada, mas trás um entendimento maior sobre o conceito de recursão como um todo.

A ordenação recursiva de uma lista ligada é também interessante porque pode ser feita in-place, isto é, alterando a lista que já temos, sem criar uma nova lista.

Então, vamos ao algoritmo. Primeiro, quando trabalhamos com recursão, é essencial definir um caso base. O caso base é um caso específico do problema que queremos resolver para o qual conseguimos resolver sem precisar fazer recursão.

Isso é essencial, pois se não tivermos um caso base, nossa recursão nunca chega ao fim. Outra coisa que precisamos garantir é que todo problema pode ser derivado do(s) caso(s) base.

Para esse algoritmo em específico, vou fazer as coisas fora de ordem: primeiro veremos o algritmo correto, e depois vamos entender por quê ele funciona. Aí vai:

def ordenaRecursivo(primeiroNó: Nó*):
    if primeiroNó.próximo == null:
        return primeiroNó
    else:
        sublistaOrdenada = ordenaRecursivo(primeiroNó.próximo)
        return insereEmOrdem(sublistaOrdenada, primeiroNó)

Veja funcionando no repl.it

[box class=valid_input padding][box class=floatright send_topic padding][/box] Veja só

A função insereEmOrdem aqui é levemente diferente da que definimos antes, recebendo um primeiroNó ao invés de uma ListaLigada. Apesar disso, a lógica é exatamente a mesma.

Esse ajuste foi feito para facilitar a recursão. [/box]

Vamos entender o algoritmo então. Primeiro, temos claramente um caso base: primeiroNó.próximo == null, ou "quando a lista tem apenas um nó". Claro que esse é um caso muito bom para ser base da ordenação, já que uma lista com um nó só está sempre ordenada, sem que tenhamos que fazer nenhuma alteração nela.

Depois do caso base, temos o passo recursivo: para ordenar uma lista com N elementos, primeiro ordenamos a sublista nela que tem N - 1 elementos (ou seja, a lista que começa no próximo de seu primeiroNó); depois disso, inserimos nosso primeiroNó em ordem nessa lista ordenada, e assim ela continua ordenada.

E é isso. Temos nosso algoritmo.

Pode parecer confuso a princípio porque isso funciona, mas somente porque na programação imperativa estamos acostumados a controlar os algoritmos através de repetições, e customamos declarar todos os passos a serem tomados.

Em algoritmos recursivos, não fica claro a princípio que realmente declaramos tudo que deve ser feito. Claro, definimos o que acontece com uma lista com tamanho 1. Mas e listas maiores? Por que é que elas funcionam?

[box class=errorbox padding][box class=floatright send_topic padding][/box]

Disclaimer: Gente, provas e demonstrações não são meu forte, então tomem cuidado com o que vem aqui em baixo. Acho que consegui passar a ideia, mas tá tudo meio louco rs.

[/box]

Para esclarecer isso, vale a pena darmos uma olhada na prova de que o algoritmo termina para todo caso a partir do caso base. Podemos usar indução matemática para isso:

[box title=Prova por indução]

Seja N o número de elementos na lista ligada. Veja que, quando N = 1, é garantido que o algoritmo termina, já que ele apenas retorna a lista, sem nenhuma alteração. Esse é nossa base de indução.

Vejamos então que o algoritmo também termina ∀ n > N, n ∈ ℕ.

Hipótese de Indução: O algoritmo termina para algum n ∈ ℕ.

Tese de Indução: O algoritmo termina também para n + 1.

Mas pela definição do nosso algoritmo, a solução para uma lista de tamanho n é, justamente, resolver para uma lista de tamanho n - 1, seguido de uma inserção em ordem (que sempre termina) na mesma lista, ainda com tamanho n - 1.

Podemos então definir o tempo que nosso algoritmo (que apelidaremos de S, de sort) leva para completar por:


Onde T(f(x)) é o tempo que a função f leva para terminar para a entrada x, S(n) é nosso algoritmo de ordenação para uma lista de tamanho n e I(n) é nosso algoritmo de inserção em ordem em uma lista de tamanho n.

Veja então que, para a ordenação em n + 1, o tempo é dado pelo seguinte:


Mas, por hipótese, o algoritmo termina para S(n) e para I(n). Temos então:


Assim, sabemos que existe um r0 = r1 + r2 que satisfaz r0 ∈ ℝ e r0 > T(S(n)) + T(I(n)), e segue que:


Com isso temos que, a partir de N = 1, o algoritmo de ordenação recursiva termina para toda lista de tamanho finito N, como queríamos demonstrar.

[/box]

[box class=description padding][box class=floatleft send_topic padding][/box] Nota: Essa prova só funciona baseado na premissa de que a lista que começa a partir do próximo do primeiroNó tem tamanho N - 1 (o que, por sinal, pode não ser verdade!).

Porém, o único caso em que nossa prova não funciona é quando a lista é circular (ou seja, o último nó é ligado no primeiro), mas nesse caso nem é interessante ordenar a lista.

Aliás, é possível provar que nenhuma lista circular com mais de um valor único pode ser ordenada, mas isso está meio fora do escopo aqui, rs. [/box]

2.2.2 (Bônus) Inversão de listas ligadas com recursão

Outra operação relativamente comum em listas (embora nem de longe tão comum quanto a ordenação) é a inversão de listas.

Assim como na ordenação, temos duas maneiras de fazer essa operação com listas ligadas: criando uma nova lista e inserindo os elementos de trás para frente, ou recursivamente.

[box class=description padding][box class=floatright send_topic padding][/box] Nota: OK, existe um algoritmo iterativo que inverte a lista in-place, mas vou ser sincero: eu nunca entendi aquela desgraça. É uma sopa de ponteiros pra lá e pra cá que só por deus.

De toda forma, nosso objetivo nessa seção é falar de recursão, então vamos ignorar esse cara :^) [/box]

Um ponto curioso desse algoritmo é que ele é praticamente idêntico ao de ordenação, usando apenas um método de inserção diferente! Legal né?

A inversão recursiva pode ser definida assim:

def inverteRecursivo(primeiroNó: Nó):
    if primeiroNó.próximo == null:
        return primeiroNó
    else:
        sublista = inverteRecursivo(primeiroNó.próximo)

        primeiroNó.próximo = null
        return insereNoFim(sublista, primeiroNó)

Veja funcionando no repl.it

Novamente, temos um caso base bem definido (primeiroNó.próximo == null, assim como antes) e subproblemas que têm a mesma cara que o original, só que para um subconjunto.

Na ordenação, nós ordenávamos todos os elementos após o primeiro e então inseríamos o primeiro em ordem nessa sublista ordenada.

Aqui, nossa abordagem é parecida: para uma lista de tamanho N, invertemos a sublista de N - 1 elementos (que começa a partir do primeiroNó.próximo), e então inserimos o primeiroNó ao fim da lista.

Note que temos um passo a mais, no entanto, que apesar de dispensável na ordenação é essencial aqui: definimos o próximo do primeiroNó para nulo antes de inserirmos ele no fim. Se não fizessemos isso, criaríamos uma lista circular, gerando um loop.

Fora isso, podemos provar que esse algoritmo sempre termina usando o mesmo método que usamos para a ordenação. Como a lógica é exatamente a mesma, não farei a prova de novo.

"Mas será que esse algoritmo inverte a lista mesmo?", você pode se perguntar. Podemos provar isso por indução também!

[box title=Definição]

Antes de provar que o algoritmo inverte a lista, precisamos definir o que significa inverter a lista.

Pois bem, seja L uma lista ligada, denotaremos por L-1 a lista L invertida.

Denotaremos também todo nó de L por n, e definiremos uma função Ix(n, n0) (índice de n), dada por:


Onde:

  • L x L é o produto cartesiano dos elementos da lista
  • n é o nó que estamos procurando e n0 é o primeiro nó da lista
  • Prox(n) é o próximo do nó n.
Notação:

Assim, podemos definir que uma lista L′ é L invertida da seguinte forma:



Calma, parece difícil, mas isso só diz que as relações de ordem devem estar invertidas. Faz sentido, não?

[/box]

Legal! Sabemos como verificar se uma lista é inversa de outra, vamos agora mostrar que o que nosso algoritmo faz é, justamente, inverter uma lista ligada.

[box title=Prova por indução]

Para nossa base de indução, usaremos o caso em que a lista contém apenas um elemento (n0), para o qual nosso algoritmo simplesmente retorna a própria lista, sem alterações.

Veja que, nesse caso, L é a própria inversa, pois L × L = {(n0, n0)}, mas n0 ≤ n0 e n0 ≥ n0, e isso satisfaz os dois lados da nossa condição.

Prossigamos então para o passo indutivo. Seja k o tamanho da nossa lista:

Hipótese de Indução: O algoritmo inverte a lista para algum k.

Tese de Indução: O algoritmo inverte a lista também para k + 1.

Observe que, para uma lista de tamanho k + 1, o procedimento do algoritmo diz o seguinte:

  • Inverter a lista a partir do nó n1 (que tem k elementos)
  • Inserir o nó n0 ao fim dessa nova lista
Por hipótese, sabemos que o passo 1 funciona. Vejamos que o passo 2 garante que a nova lista obedece a condição de inversa de L.

Denotemos L′ a sublista invertida, criada no passo 2, e por n-1 o primeiro nó dessa sublista.

Mas veja que, para toda lista, vale que n0 < ni ∀ i > 0. Quando inserimos n0 ao fim de L′, garantimos que Ix(n0, n-1) > Ix(n, n-1) ∀ n ∈ L′, pela definição da inserção ao fim.

Assim, claramente L′ obedece à condição de inversa, pois:



Claro, para todo nj ∈ L, vale que n0 < nj, mas eu deixei a condição ali pra dar pra ver que os dois casos se completam. O j > 0 na primeira linha também é redundante, pois se j = 0, como i > 0, não existe nenhum par (ni, j) onde nj < nj em L, mas deixei porque a H.I. fala apenas sobre a lista onde i e j são maiores que 0.

Com isso, temos que para toda lista de tamanho k ≥ 1, nosso algoritmo inverte a lista conforme nossa definição de inversa, como queríamos demonstrar.

[/box]

[box class=errorbox padding][box class=floatright send_topic padding][/box] Disclaimer: Essa prova ficou especialmente complicada. Checando ela, não parece que tem nada errado de fato, mas se alguém puder dar uma olhada pra mim eu agradeço, rs.

De todo modo, isso é mais a critério de curiosidade do que qualquer coisa, então estou satisfeito. Qualquer dúvida podem me consultar \o[/box]

3 Conclusão



Oba, fim \o/

Essa primeira aula foi só uma introdução à ideia por trás das estruturas de dados e à nossa primeira estrutura de fato: a lista ligada.

Enquanto ia escrevendo eu já deixei vários exercícios, então imagino que não precisamos de uma seção só pra isso.

Acho que nessa conclusão só me resta dizer que espero que a aula tenha sido de alguma ajuda a alguém, nem que a critério de curiosidade (as provas dos algoritmos recursivos são bem legais, vai kk).

Tenho um pouco de material sobre filas e pilhas guardado aqui, mas vou esperar ter mais maturidade no que escrevi para publicar aqui. E talvez nem publique, porque o tempo é escasso e, sinceramente, duvido um pouco que esse tipo de aula
seja muito útil aqui.

De todo modo, me diverti bastante escrevendo e adoraria dar uma mão para quem quiser fazer os exercícios e encontrar alguma dificuldade.

See ya \o

~ Masked
26/06/2019 às 20:37 #1
Eita, bela aula. Não restou o que comentar, recomendo até que enfie na revista nas próximas edições. Tópico salvo para futuras consultas. o/

Mas continuo odiando ponteiros com toda a força do meu ser.
26/06/2019 às 20:43 #2
Mas o que foi isso  :o: ?

Citação de: Corvo online 26/06/2019 às 20:37
Mas continuo odiando ponteiros com toda a força do meu ser.

Meu problema com ponteiros, foi quando eu já conseguia "desenvolver", mas não sabia como ponteiros funcionavam, ai toda hora as coisas tinham valores esquisitos quando eu atribuia qualquer objeto hahah.

Agora sério, ficou tudo dez mano! Parabéns por escrever tudo isso e com tanta organização assim!

Agora de recursividade, é a coisa que fica mais binito e limpo visualmente, mas raramente é eficiente hahah, só que eu sempre tento encaixar em códigos que não requerem atualização XD.
26/06/2019 às 21:29 #3 Última edição: 26/06/2019 às 21:30 por Brandt
Citação de: Corvo online 26/06/2019 às 20:37
Eita, bela aula. Não restou o que comentar, recomendo até que enfie na revista nas próximas edições. Tópico salvo para futuras consultas. o/

Valeu \o

Citação de: Corvo online 26/06/2019 às 20:37
Mas continuo odiando ponteiros com toda a força do meu ser.

auheuaehuaeha

O mesmo vale pra todo programador que já passou pela terra também, provavelmente  :=p:
Uma coisa legal em várias linguagens (tipo todas, tirando, sei lá, C e C++) é justamente que a gente nem precisa se precupar com essa história toda de ponteiros e memória e o escambau. Na prática, é tudo ponteiro, mas se comporta muito melhor (glória ao garbage collector).

Eu quis incluir essa parte na aula mais porque assim consigo usar as analogias das "setinhas" das estruturas de dados de um jeito mais esclarecedor, imagino.



Citação de: Raizen online 26/06/2019 às 20:43
Mas o que foi isso  :o: ?

Meu problema com ponteiros, foi quando eu já conseguia "desenvolver", mas não sabia como ponteiros funcionavam, ai toda hora as coisas tinham valores esquisitos quando eu atribuia qualquer objeto hahah.

Agora sério, ficou tudo dez mano! Parabéns por escrever tudo isso e com tanta organização assim!

Agora de recursividade, é a coisa que fica mais binito e limpo visualmente, mas raramente é eficiente hahah, só que eu sempre tento encaixar em códigos que não requerem atualização XD.

Valeu bro o/

Pois é, recursão é um negócio lindão de escrever (e bem mais simples, diga-se de passagem), mas realmente peca em performance x(
Eu acho muito interessante como tem linguagens tipo Haskell que dependem bastante de recursão, aí tem muitas otimizações em cima e códigos recursivos rodam como se não fossem.

Numa próxima aula pensei em trazer pilhas, e aí dá pra ensinar a fazer uma "recursão" sem usar a call stack de verdade. Fica mais feinho, mas é o que tem pra hoje kk
~ Masked
28/06/2019 às 21:30 #4
Da pra ver que alguém esta estudando... o tópico segue regras de artigo, mas acho que é muito, para meros mortais aprecio o formato pré definido como padrão, e colocar as coisas mais didáticas possíveis seria bem legal. :wow:
ou pelo menos me faria sentir com que o conteúdo não fosse extremamente complicado  :lol:
29/06/2019 às 12:36 #5
Citação de: hategum rpg online 28/06/2019 às 21:30
Da pra ver que alguém esta estudando... o tópico segue regras de artigo, mas acho que é muito, para meros mortais aprecio o formato pré definido como padrão, e colocar as coisas mais didáticas possíveis seria bem legal. :wow:
ou pelo menos me faria sentir com que o conteúdo não fosse extremamente complicado  :lol:

Poxa, eu achei que tinha deixado super didático  :rick9:

Realmente, não tinha percebido, mas o tópico acabou ficando com cara de artigo científico (rs). Apesar disso, acho que o conteúdo até que ficou bem mais acessível do que seria em um artigo de verdade. Tirando talvez a parte com as provas por indução e tal, que são mais matemáticas e precisam de um background melhor pra entender.

Certo que esse conteúdo requer no mínimo um bom domínio prévio de técnicas de programação, então da parte de conteúdo não sei há muito que possa ser simplificado, mas vou me esforçar pra tentar ser mais didático no futuro (mais imagens ilustrativas e GIFs, talvez?).

Valeu pelo feedback \o
~ Masked
Imprimir
Ir para o topo Páginas1
Ações