### swap any node Doubly linked list, python

Update: 12-23-17

Found a bug, adding a fix. The first if, depends on the node1 or node2 having a prev, and they may or may not. I tried adding this function set_sides() to my swap_left(self) also and it kept rejecting it... will figure that out later. Christmas is here, and trying to quicksort this doubly linked list.... is driving me mad.... Does anyone actually sort a doubly linked list inside a doubly linked list with this swap method??

Happy joyful whatever holidays you may celebrate, and Merry Christmas too!

I'll be adding this to my old Doubly Linked List post.

It uses my swap_left method for if nodes are next to each other...

I will go and see if I can combine these after I get the quicksort figured out. I'm sure it's possible, but I'm debating if they should be combined. Another one of those, I don't know enough about how these lists are used and manipulated to know if it's a good idea to put that much control over the list into one method.... But it kinda is.... because I use the left_swap in the swap_any...

Anyhoo..... Less gremlins lurking on this one. Once I figured out the order in which the links had to be reset and established.....

If you do it in the wrong order, the nodes will runaway with nothing to chain them to your list. Especially since python likes to clean things up for you. If there's no reference to the thing, python will garbage collect it.... POOF... gone... Makes this sorting stuff kinda scary ... If this was important data and I did this wrong... Gone!

I tested this with my print methods, and count methods... the where_begin() uses self.begin and next to go through list , and the graphical uses self.end previous links to go through the list. I used count() to make sure also that counting from the front of the list, I still had all my items. My graphical shows the counts, so that part was covered for going prev... to get counts.

OK, enough of that. Here is the swap_any() for doubly linked list.

def swap_any(self, node1, node2):

#[or NONE spam -- n1-->][<---spam---node1--eggs--->][<--n1--eggs or NONE]

#[or NONE bags -- n2-->][<---bags---node2---nots-->]<---n2--nots or NONE]

### make sure they are not next to each other ###

def set_sides(node1, node2):

if node1.prev != None:

node1prev = node1.prev

else:

node1prev = None

if node1.next != None:

node1next = node1.next

else:

node1next = None

if node2.prev != None:

node2prev = node2.prev

else:

node2prev = None

if node2.next != None:

node2next = node2.next

else:

node2next = None

return node1prev, node1next, node2prev, node2next

node1prev, node1next, node2prev, node2next = set_sides(node1,node2)

if node1prev == node2 or node2prev == node1 or node1next == node2 or node2next == node1:

## might have to fix swap_left..... I think it doesn't care which order they are

self.swap_left(node1,node2)

elif node1.prev != None and node1.next != None and node2.next != None and node2.prev != None:

print(" swap any 1")

### not sure why this order is important...

## ohhhhh............

## you change the link by accessing it through the original node given...

## if you change that node before the address get's assigned it will assign

## a wrong address...... try to add something later to show it.

node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

node1.next.prev = node2 #eggs

node2.next.prev = node1 #nots

# this swaps the links without having to set any temps.

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

elif node1.prev == None and node2.next != None:

## node1 is a begin node:

print(" Swap begin node, node 1 .....")

#node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

node2.next.prev = node1 #nots

node1.next.prev = node2 #eggs

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.begin = node2

#print(f"{node1}{node2}")

elif node2.prev == None and node1.next != None:

## node2 is a begin node:

print(" Swap begin node, node 2...")

node1.prev.next = node2 #spam

#node2.prev.next = node1 #bags

node1.next.prev = node2 #eggs

node2.next.prev = node1 #nots

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.begin = node1

elif node1.next == None and node2.prev != None:

## node1 is an end node:

print(" node1 is end node, swap")

node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

#node1.next.prev = node2 #eggs

node2.next.prev = node1 #nots

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.end = node2

elif node2.next == None and node1.prev != None:

#node 2 is an end node:

print(" end node swap, node 2 .....")

node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

node1.next.prev = node2 #eggs

#node2.next.prev = node1 #nots

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.end = node1

elif node1.prev == None and node2.next == None:

# node1 is a begin node, node2 is an end node:

print(" swap node1 begin, node2 end ")

#node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

node1.next.prev = node2 #eggs

#node2.next.prev = node1 #nots

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.end = node1

self.begin = node2

print(f"{node1} : {node2}")

elif node2.prev == None and node1.next == None:

# node 2 is begin, node 1 is end:

print(" swap node2 begin, node1 end ...")

node1.prev.next = node2

node2.next.prev = node1

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.end = node2

self.begin = node1

else:

print(" not complete -----------")

Found a bug, adding a fix. The first if, depends on the node1 or node2 having a prev, and they may or may not. I tried adding this function set_sides() to my swap_left(self) also and it kept rejecting it... will figure that out later. Christmas is here, and trying to quicksort this doubly linked list.... is driving me mad.... Does anyone actually sort a doubly linked list inside a doubly linked list with this swap method??

Happy joyful whatever holidays you may celebrate, and Merry Christmas too!

I'll be adding this to my old Doubly Linked List post.

It uses my swap_left method for if nodes are next to each other...

I will go and see if I can combine these after I get the quicksort figured out. I'm sure it's possible, but I'm debating if they should be combined. Another one of those, I don't know enough about how these lists are used and manipulated to know if it's a good idea to put that much control over the list into one method.... But it kinda is.... because I use the left_swap in the swap_any...

Anyhoo..... Less gremlins lurking on this one. Once I figured out the order in which the links had to be reset and established.....

If you do it in the wrong order, the nodes will runaway with nothing to chain them to your list. Especially since python likes to clean things up for you. If there's no reference to the thing, python will garbage collect it.... POOF... gone... Makes this sorting stuff kinda scary ... If this was important data and I did this wrong... Gone!

I tested this with my print methods, and count methods... the where_begin() uses self.begin and next to go through list , and the graphical uses self.end previous links to go through the list. I used count() to make sure also that counting from the front of the list, I still had all my items. My graphical shows the counts, so that part was covered for going prev... to get counts.

OK, enough of that. Here is the swap_any() for doubly linked list.

def swap_any(self, node1, node2):

#[or NONE spam -- n1-->][<---spam---node1--eggs--->][<--n1--eggs or NONE]

#[or NONE bags -- n2-->][<---bags---node2---nots-->]<---n2--nots or NONE]

### make sure they are not next to each other ###

def set_sides(node1, node2):

if node1.prev != None:

node1prev = node1.prev

else:

node1prev = None

if node1.next != None:

node1next = node1.next

else:

node1next = None

if node2.prev != None:

node2prev = node2.prev

else:

node2prev = None

if node2.next != None:

node2next = node2.next

else:

node2next = None

return node1prev, node1next, node2prev, node2next

node1prev, node1next, node2prev, node2next = set_sides(node1,node2)

if node1prev == node2 or node2prev == node1 or node1next == node2 or node2next == node1:

## might have to fix swap_left..... I think it doesn't care which order they are

self.swap_left(node1,node2)

elif node1.prev != None and node1.next != None and node2.next != None and node2.prev != None:

print(" swap any 1")

### not sure why this order is important...

## ohhhhh............

## you change the link by accessing it through the original node given...

## if you change that node before the address get's assigned it will assign

## a wrong address...... try to add something later to show it.

node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

node1.next.prev = node2 #eggs

node2.next.prev = node1 #nots

# this swaps the links without having to set any temps.

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

elif node1.prev == None and node2.next != None:

## node1 is a begin node:

print(" Swap begin node, node 1 .....")

#node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

node2.next.prev = node1 #nots

node1.next.prev = node2 #eggs

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.begin = node2

#print(f"{node1}{node2}")

elif node2.prev == None and node1.next != None:

## node2 is a begin node:

print(" Swap begin node, node 2...")

node1.prev.next = node2 #spam

#node2.prev.next = node1 #bags

node1.next.prev = node2 #eggs

node2.next.prev = node1 #nots

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.begin = node1

elif node1.next == None and node2.prev != None:

## node1 is an end node:

print(" node1 is end node, swap")

node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

#node1.next.prev = node2 #eggs

node2.next.prev = node1 #nots

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.end = node2

elif node2.next == None and node1.prev != None:

#node 2 is an end node:

print(" end node swap, node 2 .....")

node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

node1.next.prev = node2 #eggs

#node2.next.prev = node1 #nots

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.end = node1

elif node1.prev == None and node2.next == None:

# node1 is a begin node, node2 is an end node:

print(" swap node1 begin, node2 end ")

#node1.prev.next = node2 #spam

node2.prev.next = node1 #bags

node1.next.prev = node2 #eggs

#node2.next.prev = node1 #nots

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.end = node1

self.begin = node2

print(f"{node1} : {node2}")

elif node2.prev == None and node1.next == None:

# node 2 is begin, node 1 is end:

print(" swap node2 begin, node1 end ...")

node1.prev.next = node2

node2.next.prev = node1

node1.prev, node2.prev = node2.prev, node1.prev

node2.next, node1.next = node1.next, node2.next

self.end = node2

self.begin = node1

else:

print(" not complete -----------")

## Comments

## Post a Comment