Switch chained list pointers - python

Question

I created a function to change the pointers of a chained list, the idea is very simple, change them and update the next element so that it does not lose the reference, only that the function is losing the reference, for example, I tested a list l = 1, 2, 3, 4, 5, 6, and I want to change the 2 and the 4 position, it returns me l = 1, 2, 5, 6, when it should be l = 1, 4, 3, 2, 5, 6. I do not know more what to do, tested several alternatives and nothing, follows the code:

def troca_teste(L): 
        p = L.head
        aux = p
        while p:
            if p.element == 2:
                q = p.next
                while q:                  
                    if q.element == 4:          
                        #swap dos ponteiros          
                        aux = q
                        q = p
                        q.next = aux.next                        
                        aux.next = p.next
                        p = aux                        
                        p.next = aux.next                                     
                        break  
                    q = q.next                   
            p = p.next

Definition of classes:

class LinkList:

    class Node:

        def __init__ (self, element = None, next = None):
            self.element = element
            self.next = next

    def __init__ (self):
        self.head = None
        self.size = 0

Answer 1

You wish to do an operation of swap. The swap is an operation which, given an indexable set and two indices, changes the time-consuming elements of these indices.

Foreplay

Let’s call the indexable list l. For your case, l is an instance of LinkList.

Due to the definition of LinkList, l nay is indexed. To make indexed accesses, 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 within the node, and this is purposeful). So we can say that, through an index, we get the associated node. Now we can deal with l as an indexed set, since we transform its ability to be indexed in fact (before acesso_nodo, instances of LinkList were liable to be indexable, therefore indexable; after this function, we transform this capacity into reality, hence now we can call LinkList indexed).

Making the exchange, maintaining structure

How 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 just:

nodo_k.element, nodo_j.element = nodo_j.element, nodo_k.element

So it’s open just to identify nodo_j and nodo_k. About the function described in the previous section, we can do the following function (relatively inefficient):

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 here that to navigate to the highest index, you need to pass the lowest index. On top of that, we can do an optimization and decrease access to reference in 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 make the same iteration made in acesso_nodo Only it is aimed at the largest element of the past index, taking advantage when it passes in the lowest index to keep its value. Note that, in the loop, there are conditions to detect when the desired index is found and save in the variables nodo_m and nodo_M.

To have fewer issues of conditional adjustments, I put that m will be the lowest of the j and k, and M to be the greatest. So, if j is the smallest, then nodo_j is equivalent to nodo_m; otherwise of j be the greatest element, then nodo_M which amounts to nodo_j. nodo_k gets the other node in both cases.

I also took advantage and put a small deal to not need to perform any action when the index passed to perform the exchange is the same (ie, j == k), because trivially making that exchange has the same effect of not making it.

Topological exchange

The other alternative is to change the structure itself. The nodes physically change structure. Since the list is simply chained, it is not possible to access the previous element from the current one. So, we need to get the element previous to the past indexes to make this exchange.

As in the exchange keeping topology, it is possible to write more efficient code, but here I will focus more on logic than on performance. Feel free to make the version more efficient.

To access the elements prior to j and k, we need to access the 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 treat in a more simplified way who is the largest and who is the smallest element, I will use the same logic of m,M of function swap_topologico_2. So I just 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 exchange the elements of nodo_m.next and nodo_M.next in such a way that it would be possible to remove nodo_m and nodo_M and maintain the coherence of the list.

---

Recommended reading

• Invert Simple List
• How to order a chained list in alphabetical order?
• What is the best implementation of 'Mergesort Algorithm'?
• Stackoverflow in Quick Sort
• In practice, what is the use of C pointers?
• Comment distinguishing pointer and reference