Você deseja fazer uma operação de swap
. O swap
é uma operação que, dado um conjunto indexável e dois índices, troca de posição os elementos demorados por esses índices.
Preliminares
Chamemos a lista indexável de l
. Para o seu caso, l
é uma instância de LinkList
.
Devido à definição de LinkList
, l
não está indexado. Para fazer acessos indexados, a ideia é mais ou menos a seguinte:
def acesso_nodo(l, idx):
# se o índice for além do que está armazenado, retorna nenhum nó
if l.size <= idx < 0:
return None
atual = l.head
while idx > 0:
atual, idx = atua.next, idx - 1
return atual
Note que essa função vai retornar o nó (instância de Node
, não o elemento dentro do nó, e isso é proposital). Assim sendo, podemos dizer que, através de um índice, obtemos o nó associado. Agora podemos tratar l
como um conjunto indexado, já que transformamos sua capacidade de ser indexado em fato (antes de acesso_nodo
, instâncias de LinkList
eram passíveis de sofrerem indexação, portanto indexáveis; depois dessa função, transformamos essa capacidade em realidade, daí agora podemos chamar LinkList
de indexado).
Fazendo a troca, mantendo estrutura
Como estamos fazendo uma operação de troca, a estrutura topológica da lista. Assim, ao obtermos os nós que apontam para os elementos de índice k
e j
(doravante denominados nodo_k
e nodo_j
), precisamos fazer apenas:
nodo_k.element, nodo_j.element = nodo_j.element, nodo_k.element
Então, fica aberto apenas identificar nodo_j
e nodo_k
. Sobre a função descrita na seção anterior, podemos fazer a seguinte função (relativamente não eficiente):
def swap_toplologico_1(l, j, k):
nodo_j = acesso_nodo(l, j)
nodo_k = acesso_nodo(l,k)
if nodo_j != None and nodo_k != None:
nodo_k.element, nodo_j.element = nodo_j.element, nodo_k.element
return l
Note aqui que, para navegar até o maior índice, é necessário passar pelo menor índice. Em cima disso, podemos fazer uma otimização e diminuir o acesso a referência em pelo menos o(min(j,k))
:
def swap_toplologico_2(l, j, k):
(m, M) = (j, k) if j < k else (k, j)
if M >= l.size or m == M or m < 0:
return l
atual = l.head
while M >= 0:
if m == 0:
nodo_m = atual
if M == 0:
nodo_M = atual
atual, m, M = atual.next, m - 1, M - 1
nodo_m.element, nodo_M.element = nodo_M.element, nodo_m.element
return l
Aqui, a ideia foi fazer a mesma iteração feita em acesso_nodo
só que voltada para o maior elemento do índice passado, aproveitando quando se passa no menor índice para guardar seu valor. Note que, no laço, há condições para detectar quando se encontra o índice desejado e guardar nas variáveis nodo_m
e nodo_M
.
Para ter menos questões de ajustes condicionais, coloquei que m
será o menor dos índices j
e k
, e M
para ser o maior. Então, se j
for o menor, então nodo_j
é equivalente ao nodo_m
; caso contrário, de j
ser o maior elemento, então nodo_M
que equivale a nodo_j
. nodo_k
fica com o outro nó em ambos os casos.
Também aproveitei e pus uma pequena tratativa para não precisar realizar nenhuma ação quando o índice passado para realizar a troca for o mesmo (ie, j == k
), pois trivialmente fazer essa troca tem o mesmo efeito de não fazê-la.
Troca topológica
A outra alternativa é fazendo a troca da estrutura propriamente dita. Os nós fisicamente mudam de estrutura. Como a lista é simplesmente encadeada, não é possível acessar o elemento anterior a partir do atual. Então, precisamos obter o elemento anterior aos dos índices passados para se fazer essa troca.
Assim como na troca mantendo a topologia, é possível escrever um código mais eficiente, mas aqui vou focar mais na lógica do que na performance. Fique a vontade para fazer a versão mais eficiente.
Para acessar os elementos anteriores a j
e k
, precisamos acessar os elementos j-1
e k-1
. Também é bom garantir que o maior elemento é um elemento válido. Outro ponto de atenção é que 0 é um caso especial, onde se faz necessário alterar l.head
.
Para tratar de maneira mais simplificada quem é o maior e quem é o menor elemento, usarei a mesma lógica de m,M
da função swap_topologico_2
. Então verifico apenas se m
é zero.
def swap_trocando_estrutura(l, j, k):
(m, M) = (j, k) if j < k else (k, j)
if M >= l.size or m == M or m < 0:
return l
prev_M = acesso_nodo(l, M - 1)
# tratar primeiro o caso de m ser 0
if m == 0:
next_head = l.head.next
next_M = prev_M.next.next
# trocando as referências dos elementos seguintes
prev_M.next.next = next_head
l.head.next = next_M
# trocando as referências dos elementos desejados
l.head, prev_M.next = prev_M.next, l.head
return l
else:
prev_m = acesso_nodo(l, m - 1)
next_m = prev_m.next.next
next_M = prev_M.next.next
# trocando as referências dos elementos seguintes
prev_m.next.next = next_M
prev_M.next.next = next_m
# trocando as referências dos elementos desejados
prev_m.next, prev_M.next = prev_M.next, prev_m.next
return l
Note que foi necessário trocar os elementos de nodo_m.next
e nodo_M.next
de tal modo que fosse possível remover nodo_m
e nodo_M
de seus lugares atuais e manter a coerência da lista.
Leitura recomendada
1,4,3,2,5,6
?