Cannot swap LinkedList node references in Python

Question

My LinkedList and Node class implementation has been stolen from here.

class Node:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next

    def __str__(self):
        return 'Node[' + self.value +']'

class Linked_List:
    def __init__(self):
        self.first = None
        self.last = None

    def insert(self, x):
        if self.first is None:
            self.first = Node(x, None)
            self.last = self.first
        elif self.last is self.first:
            self.last = Node(x,None)
            self.first.next = self.last
        else:
            current = Node(x, None)
            self.last.next = current
            self.last = current

    def __str__(self):
        if self.first is not None:
            current = self.first
            out = 'LinkedList[\n' + str(current.value) + '\n'
            while current.next is not None:
                current = current.next
                out += str(current.value) + '\n'
            return out + ']'

    def clear(self):
        self.__init__()

I want to swap every two nodes in the LinkedList, as an example:

Input: 0 1 2 3 4 5 6 7 8 9 
Output: 1 0 3 2 5 4 7 6 9 8

My code to create, and then attempt to swap every two elements in the list, is as follows:

for i in range(10):
    if i is 0:
        linkedlist = Linked_List()
        linkedlist.insert(str(i))
    else:
        linkedlist.insert(str(i))

current = linkedlist.first
while current is not linkedlist.last:
    print(str(current))
    print("NEXT =" + str(current.next))
    print("NEXT.NEXT=" + str(current.next.next))
    if current is linkedlist.first:
        linkedlist.first = current.next
    current.next, current.next.next = current.next.next, current.next 
    print(str(current))
    print("NEXT =" + str(current.next))
    print("NEXT.NEXT=" + str(current.next.next))
    current = current.next

The meat of my question:

current.next, current.next.next = current.next.next, current.next

In my mind, this should swap the current node's reference, and the next node's reference. Resulting in the first case:

Node[0].next=Node[2]
Node[1].next=Node[0]

Thus altering the list from/to:

0 1 2 3 4 5 6 7 8 9 
1 0 2 3 4 5 6 7 8 9

And it seems to nearly work, as the output from the first iteration of this while loop is:

Node[0]
NEXT =Node[1]
NEXT.NEXT=Node[2]
Node[0]
NEXT =Node[2]
NEXT.NEXT=Node[1]

It looks as expected, except for the last line. Node[0].next=Node[2] is what I next to see. I do not see why Node[2].next=Node[1], but I believe the swap operation did not perform like I expected it to, and I am having difficulty understanding why.

Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. We need *all* of the example in your posting, not references to outside sources. — Prune, Feb 06 '18 at 21:52
Thank you, I have added the Node and Linked_List implementation — NPE_Exception, Feb 06 '18 at 21:54

Moinuddin Quadri · Answer 1 · 2018-02-06T21:59:29.707

1

If you are having just a list, and want to swap the elements alternatively, then the simplest way to achieve this is using list slicing as:

>>> my_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

#            v slice from `0`th index with step of `2`
#            v             v slice from `1`st index with step of `2`
>>> my_list[::2], my_list[1::2] = my_list[1::2], my_list[::2]
>>> my_list
[1, 0, 3, 2, 5, 4, 7, 6, 9, 8]

edited Feb 06 '18 at 21:59

answered Feb 06 '18 at 21:54

Moinuddin Quadri

46,825
13
96
126

score 0 · Answer 2 · answered Feb 06 '18 at 22:03

0

Shouldn't

current.next, current.next.next = current.next.next, current.next

be

current.next, current.next.next = current.next.next, current

?

answered Feb 06 '18 at 22:03

kszl

1,203
1
11
18

Ah, I see now that you are correct. My original code was just resulting in an endless loop, because the second and third nodes just ended up pointing at each other. Thank you! – NPE_Exception Feb 06 '18 at 22:14
On second thought, there is still some bug. Here is the output of the first loop, with your change included: `Node[0] NEXT =Node[1] NEXT.NEXT=Node[2] Node[0] NEXT =Node[2] NEXT.NEXT=Node[0]` Now, if `current.next==Node[2]`, how is `current.next.next==Node[0]`? We, I believe, have not changed the reference of `Node[2].next`... Apologies for the formatting. – NPE_Exception Feb 06 '18 at 22:29

Cannot swap LinkedList node references in Python

2 Answers2