You want to do a swap operation. The swap is an operation that, given an indexable set and two indexes, exchanges the elements delayed by those indexes.
Preliminaries
Let's call the indexable list of l . For your case, l is an instance of LinkList .
Due to the definition of LinkList , l is not indexed. To do indexed access, the idea is more or less the following:
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 that this function will return the node (instance of Node , not the element inside the node, and this is purposeful). Thus, we can say that, through an index, we get the associated node. Now we can treat l as an indexed set, since we transform its ability to be indexed in fact (before acesso_nodo , instances of LinkList were indexable, therefore indexable; reality, we can now call LinkList indexed).
Making the exchange, maintaining structure
As we are doing an exchange operation, the topological structure of the list. So, when we get the nodes that point to the index elements k and j (hereinafter referred to as nodo_k and nodo_j ), we need to do only:
nodo_k.element, nodo_j.element = nodo_j.element, nodo_k.element
Then, it is only open to identify nodo_j and nodo_k . On the function described in the previous section, we can do the following (relatively inefficient) function:
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 that to navigate to the highest index, you have to scroll through the lowest index. On top of that, we can do an optimization and decrease access to the reference by at least 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
Here, the idea was to do the same iteration made in
acesso_nodo only turned to the largest element of the index passed, taking advantage of when you pass in the lowest index to save its value. Note that, in the loop, there are conditions to detect when the desired index is found and to store the variables
nodo_m and
nodo_M .
In order to have fewer conditional adjustment questions, I put m to be the smallest of the j and k indexes, and M to be the largest. So, if j is the smallest, then nodo_j is equivalent to nodo_m ; otherwise, j is the largest element, then nodo_M that is equal to nodo_j . nodo_k gets the other node in both cases.
I also took advantage of it and made a little effort not to take any action when the index passed to make the change is the same (ie, j == k ), because to trivially make this exchange has the same effect of not doing it.
Topological change
The other alternative is to change the structure itself. The nodes physically change structure. Because the list is simply chained, you can not access the previous element from the current one. So, we need to get the previous element of the indexes passed to make this exchange.
As with the topology exchange, you can write more efficient code, but here I'll focus on logic rather than performance. Feel free to make the release more efficient.
To access elements prior to j and k , we need to access elements j-1 and k-1 . It is also good to ensure that the largest element is a valid element. Another point of attention is that 0 is a special case where it is necessary to change l.head .
To deal more simply with who is the largest and who is the smallest element, I will use the same logic as m,M of the function swap_topologico_2 . So I only check if m is 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 that it was necessary to change the elements of nodo_m.next and nodo_M.next so that it was possible to remove nodo_m and nodo_M from their current places and maintain list coherence.
Recommended reading
