Capítulo 17: Listas encadeadas ¶

Tópicos

Capítulo 17: Listas encadeadas

17.1 Referências Embutidas ¶

Nós temos visto exemplos de atributos que referenciam outros objetos, que são chamados referências embutidas (veja a Seção 12.8). Uma estrutura de dados comum, a lista ligada, tira vantagem desta característica.

Listas ligadas são constituídas de nós (nodos), onde cada nó contém uma referência para o próximo nó na lista. Além disto, cada nó contém uma unidade de dados chamada a carga.

Uma lista ligada é considerada uma estrutura de dados recorrente porque ela tem uma definição recorrente.

Uma lista ligada é:

Uma lista vazia, representada por None, ou
Um nó que contém um objeto carga e uma referência para uma lista ligada.

Estruturas de dados recorrentes são adequadas para métodos recorrentes.

17.2 A classe `No` (Node)¶

Como é usual quando se escreve uma nova classe, nós começaremos com os métodos de inicialização e __str__ de modo que podemos testar o mecanismo básico de se criar e mostrar o novo tipo:

class No:
  def __init__(self, carga=None, proximo=None):
    self.carga = carga
    self.proximo = proximo

  def __str__(self):
    return str(self.carga)

Como de costume, os parâmetros para o método de inicialização são opcionais. Por omissão (default), ambos, a carga e a ligação, proximo, são definidas como None.

A representação string de um nó é simplesmente a representação string da carga. Como qualquer valor pode ser passado para a função str, nós podemos armazenar qualquer valor em uma lista.

Para testar a implementação até agora, nós criamos um No e o imprimimos:

>>> no = No("teste")
>>> print (no)
teste

Para ficar interessante, nós precisamos uma lista com mais do que um nó:

>>> no1 = No(1)
>>> no2 = No(2)
>>> no3 = No(3)

Este código cria três nós, mas nós ainda não temos uma lista ainda porque os nós não estão ligados. O diagrama de estado é parecido com este:

Para ligar os nós, temos que fazer o primeiro nó da lista referir ao segundo e o segundo nó referir ao terceiro:

>>> no1.proximo = no2
>>> no2.proximo = no3

A referência do terceiro nó é None, que indica que ele é o final da lista. Agora o diagrama de estado se parece com:

Agora você sabe como criar nós e ligá-los em uma lista. O que pode estar menos claro neste ponto é por quê.

17.3 Listas como Coleções ¶

Listas são úteis porque elas provêm um modo de montar múltiplos objetos em uma única entidade, algumas vezes chamada uma coleção. No exemplo, o primeiro nó da lista serve como uma referência para toda a lista.

Para passar uma lista como um parâmetro, você apenas tem que passar uma referência ao primeiro nó. Por exemplo, a função imprimeLista toma um único nó como um argumento. Iniciando com o cabeça da lista, ela imprime cada nó até que chegue ao fim:

def imprimeLista(no):
  while no:
    print (no, end="")
    no = no.proximo
  print

Para chamar este método, nós passamos uma referência ao primeiro no:

>>> imprimeLista(no1)
1 2 3

Dentro de imprimeLista nós temos uma referência para o primeiro nó da lista, mas não há variáveis que refiram aos outros nós. Nós temos que usar o valor proximo de cada nó para alcançar o próximo nó.

Para percorrer uma lista ligada, é comum usar uma variável laço como no para referir a cada um dos nós sucessivamente.

Este diagrama mostra o valor de lista e os valores que no assume:

Por convenção, listas são freqüentemente impressas em braquetes com vírgulas entre os elementos, como em [1, 2, 3]. Como um exercício, modifique imprimeLista para que ela gere uma saída neste formato.

17.4 Listas e Recorrência ¶

É natural expressar muitas operações de listas utilizando métodos recorrentes. Por exemplo, o seguinte é um algoritmo recorrente para imprimir uma lista de trás para frente.

Separe a lista em dois pedaços: o primeiro nó (chamado a cabeça); e o resto (chamado o rabo).

Imprima o rabo de trás para frente.

Imprima a cabeça.

Logicamente, o Passo 2, a chamada recorrente, assume que nós temos um modo de imprimir a lista de trás para frente. Mas se nós assumimos que a chamada recorrente funciona – o passo de fé – então podemos nos convencer de que o algoritmo funciona.

Tudo o que precisamos são um caso base e um modo de provar que para qualquer lista, nós iremos, ao final, chegar no caso base. Dada a definição recorrente de uma lista, um caso base natural é a lista vazia, representada por None:

def imprimeDeTrasParaFrente(lista):
  if lista == None : return
  cabeca = lista
  rabo = lista.proximo
  imprimeDeTrasParaFrente(rabo)
  print (cabeca, end="")

A primeira linha trata o caso base fazendo nada. As próximas duas linhas dividem a lista em cabeca e rabo. As duas últimas linhas imprimem a lista. A vírgula no final da última linha impede o Python de imprimir uma nova linha após cada nó.

Nós invocamos este método como invocamos o imprimeLista:

>>> imprimeDeTrasParaFrente(no1)
3 2 1

O resultado é a lista de trás para frente.

Você pode se perguntar por quê imprimeLista e imprimeDeTrasParaFrente são funções e não métodos da classe No. A razão é que nós queremos usar None para representa a lista vazia e não é legal invocar um método sobre None. Esta limitação torna complicado escrever código de manipulação de lista em estilo orientado a objeto limpo.

Podemos provar que imprimeDeTrasParaFrente sempre termina? Em outras palavras, irá ela sempre atingir o caso base? De fato, a resposta é não. Algumas listas farão este método falhar.

17.5 Listas Infinitas ¶

Não há nada que impeça um nó de referenciar de volta um nó anterior na lista, incluindo ele mesmo. Por exemplo, esta figura mostra uma lista com dois nós, um dos quais refere-se a si mesmo:

Se nós invocarmos imprimeLista nesta lista, ele ficará em laço para sempre. Se nós invocarmos imprimeDeTrasParaFrente, ele recorrerá infinitamente. Este tipo de comportamento torna as listas infinitas difíceis de se lidar.

A despeito disto, elas ocasionalmente são úteis. Por exemplo, podemos representar um número como uma lista de dígitos e usar uma lista infinita para representar uma fração repetente.

Mesmo assim, é problemático que não possamos provar que imprimeLista e imprimeDeTrasParaFrente terminem. O melhor que podemos fazer é a afirmação hipotética, “Se a lista não contém laços, então este método terminará.” Este tipo de hipótese é chamado uma pré-condição. Ele impõe uma limitação sobre um dos parâmetros e descreve o comportamento do método se a limitação é satisfeita. Você verá mais exemplos em breve.

17.6 O Teorema da Ambigüidade Fundamental ¶

Uma parte de imprimeDeTrasParaFrente pode ter gerado surpresa:

cabeca = lista
rabo = lista.proximo

Após a primeira atribuição, cabeca e lista têm o mesmo tipo e o mesmo valor. Então por que nós criamos uma nova variável?

A razão é que as duas variáveis têm diferentes papéis. Quando pensamos em cabeca, pensamos como uma referência a um único nó, e quando pensamos em lista o fazemos como uma referência ao primeiro nó da lista. Estes “papéis” não são parte do programa; eles estão na mente do programador.

Em geral não podemos dizer olhando para o programa qual o papel que uma variável tem. Esta ambigüidade pode ser útil, mas também pode tornar os programas difíceis de serem lidos. Usamos freqüentemente nomes de variáveis como no e lista para documentar como pretendemos usar uma variável e algumas vezes criamos variáveis adicionais para remover a ambigüidade.

Poderíamos ter escrito imprimeDeTrasParaFrente sem cabeca e rabo, que a tornaria mais concisa mas possivelmente menos clara:

def imprimeDeTrasParaFrente(lista):
  if lista == None : return
  imprimeDeTrasParaFrente(lista.proximo)
  print (lista, end="")

Olhando para as duas chamadas de função, temos que lembrar que imprimeDeTrasParaFrente trata seu argumento como uma coleção e print trata seu argumento como um objeto único.

O teorema da ambigüidade fundamental descreve a ambigüidade que é inerente à referência a um nó:

Uma variável que refere a um nó pode tratar o nó como um objeto único ou como o primeiro em uma lista de nós.

17.7 Modificando Listas ¶

Existem duas maneiras de se modificar uma lista ligada. Obviamente, podemos modificar a carga dos nós, mas as operações mais interessantes são aquelas que adicionam, removem ou reordenam os nós.

Como um exemplo, vamos escrever um método que remove o segundo nó na lista e retorna uma referência ao nó removido:

def removeSegundo(lista):
  if lista == None : return
  primeiro = lista
  segundo = lista.proximo
  # faz o primeiro no referir ao terceiro
  primeiro.proximo = segundo.proximo
  # separa o segundo no do resto da lista
  segundo.proximo = None
  return segundo

Novamente, estamos usando variáveis temporárias para tornar o código mais fácil de ser lido. Aqui está como usar este método:

>>> imprimeLista(no1)
1 2 3
>>> removido = removeSegundo(no1)
>>> imprimeLista(removido)
2
>>> imprimeLista(no1)
1 3

Este diagrama de estado mostra o efeito da operação:

O que acontece se você invocar este método e passar uma lista com somente um elemento (um singleton)? O que acontece se você passar a lista vazia como um argumento? Existe uma pré-condição para este método? Se houver, corrija o método para tratar uma violação da pré-condição de modo razoável.

17.8 Envoltórios e Ajudadores ¶

Freqüentemente é útil dividir uma operação de lista em dois métodos. Por exemplo, para imprimir uma lista de trás para frente no formato convencional de lista [3, 2, 1], podemos usar o método imprimeDeTrasParaFrente para imprimir 3, 2, mas queremos um metodo separado para imprimir os braquetes e o primeiro nó. Vamos chamá-lo de imprimeDeTrasParaFrenteLegal:

def imprimeDeTrasParaFrenteLegal(lista):
  print ("[", end="")
  if lista != None :
    cabeca = lista
    rabo = lista.proximo
    imprimeDeTrasParaFrente(rabo)
    print (cabeca, end="")
  print ("]", end="")

Novamente, é uma boa idéia verificar métodos como este para ver se eles funcionam com casos especiais como uma lista vazia ou um singleton.

Quando usamos este método em algum lugar no programa, invocamos imprimeDeTrasParaFrenteLegal diretamente, e ele invoca imprimeDeTrasParaFrente por nós. Neste sentido, imprimeDeTrasParaFrenteLegal atua como um envoltório, e usa imprimeDeTrasParaFrente como um ajudador.

17.9 A Classe `ListaLigada`¶

Existem alguns problemas sutis com o modo que implementamos listas. Em um inverso de causa e efeito, proporemos uma implementação alternativa primeiro e então explicaremos qual problema ela resolve.

Primeiro, criaremos uma nova classe chamada ListaLigada. Seus atributos são um inteiro que contém o comprimento da lista e uma referência para o primeiro nó. Objetos do tipo ListaLigada servem como cabos (handles) para se manipular listas de objetos No:

class ListaLigada:
  def __init__(self):
    self.comprimento = 0
    self.cabeca = None

Uma coisa legal acerca da classe ListaLigada é que ela provê um lugar natural para se colocar funções envoltórias como imprimeDeTrasParaFrenteLegal, que podemos transformar em um método da classe ListaLigada:

class ListaLigada:
  ...
  def imprimeDeTrasParaFrente(self):
    print ("[", end="")
    if self.cabeca != None :
      self.cabeca.imprimeDeTrasParaFrente()
    print ("]", end="")


class No:
  ...
  def imprimeDeTrasParaFrente(self):
    if self.proximo != None:
      rabo = self.proximo
      rabo.imprimeDeTrasParaFrente()
    print (self.carga, end="")

Apenas para tornar as coisas confusas, mudamos o nome de imprimeDeTrasParaFrenteLegal. Agora existem dois métodos chamados imprimeDeTrasParaFrente: um na classe No (o ajudador); e um na classe ListaLigada``(o envoltório). Quano o envoltório invoca ``self.cabeca.imprimeDeTrasParaFrente, ele está invocando o ajudador, porque self.cabeca é um objeto No.

Outro benefício da classe ListaLigada é que ela torna mais fácil adicionar e remover o primeiro elemento de uma lista. Por exemplo, adicionaPrimeiro é um método para ListaLigada; ele toma um item de carga como argumento e o coloca no início da lista:

class ListaLigada:
  ...
  def adicionaPrimeiro(self, carga):
    no = No(carga)
    no.proximo = self.cabeca
    self.cabeca = no
    self.comprimento = self.comprimento + 1

Como de costume, você deve conferir códigos como este para ver se eles tratam os casos especiais. Por exemplo, o que acontece se a lista está inicialmente vazia?

17.10 Invariantes ¶

Algumas listas são “bem formadas”; outras não o são. Por exemplo, se uma lista contém um laço, ela fará muitos de nossos métodos falharem, de modo que podemos querer requerer que listas não contenham laços. Outro requerimento é que o valor de comprimento no objeto ListaLigada seja igual ao número real de nós da lista.

Requerimentos como estes são chamados de invariantes porque, idealmente, eles deveriam ser verdade para cada objeto o tempo todo. Especificar invariantes para objetos é um prática de programação útil porque torna mais fácil provar a correção do código, verificar a integridade das estruturas de dados e detectar erros.

Uma coisa que algumas vezes é confusa acerca de invariantes é que existem momentos em que eles são violados. Por exemplo, no meio de adicionaPrimeiro, após termos adicionado o nó mas antes de termos incrementado comprimento, o invariante é violado. Este tipo de violação é aceitável; de fato, é freqüentemente impossível modificar um objeto sem violar um invariante por, no mínimo, um pequeno instante. Normalmente, requeremos que cada método que viola um invariante deve restaurar este invariante.

Se há qualquer aumento significativo de código no qual o invariante é violado, é importante tornar isto claro nos comentários, de modo que nenhuma operação seja feita que dependa daquele invariante.

17.11 Glossário ¶

referência embutida (embedded reference): Uma referência armazenada/associada em/a um atributo de um objeto.
lista ligada (linked list): Uma estrutura de dados que implementa uma coleção usando uma sequência de nós ligados.
nó ou nodo (node): Um elemento de uma lista, usualmente implementado como um objeto que contém uma referência para outro objeto do mesmo tipo.
carga (cargo): Um item de dado contido em um nó.
ligação (link): Uma referência embutida usada para ligar/conectar um objeto a outro.
pré-condição (precondition): Uma asserção que precisa/deve ser verdadeira para que um método trabalhe corretamante.
teorema da ambigüidade fundamental (fundamental ambiguity theorem): Uma referência para um nó de uma lista pode ser tratada como um objeto único ou como o primeiro em uma lista de nós.
singleton (singleton): Uma lista ligada com somente um nó.
envoltório (wrapper): Um método que atua como um intermediário (middleman) entre um chamador e um método ajudador (helper), freqüentemente tornando a invocação do método mais fácil ou menos propensa a erros.
ajudador (helper): Um método que não é invocado diretamente pelo chamador (caller) mas é usado por outro método para realizar parte de uma operação.
invariante (invariant): Uma asserção que deveria ser verdadeira sempre para um objeto (exceto talvez enquanto o objeto estiver sendo modificado).