Data structures in Python, Series 1.3: Linked Lists

Swap nodes in a linked list without swapping data

Given a linked list and two keys in it, swap nodes for two given keys. Nodes should be swapped by changing links. 

Swapping data of nodes may be expensive in many situations when data contains many fields.

It may be assumed that all keys in linked list are distinct.

Examples:

Input:  10->15->12->13->20->14,  x = 12, y = 20

Output: 10->15->20->13->12->14

Input:  10->15->12->13->20->14,  x = 10, y = 20

Output: 20->15->12->13->10->14

Input:  10->15->12->13->20->14,  x = 12, y = 13

Output: 10->15->13->12->20->14

This may look a simple problem, but is interesting question as it has following cases to be handled.

1) x and y may or may not be adjacent.

2) Either x or y may be a head node.

3) Either x or y may be last node.

4) x and/or y may not be present in linked list.

check out the swap_given_nodes which solves the above problem.

#____________ Firt of all make a node class for every future node to be shaped like ______________
class node():
    def __init__(self,data,nextnode = None):
        self.data = data
        self.nextnode = nextnode
#now make a class with the all the operations that can be operated in a list
#remember do get a __init__ as this will be used to initiate the default values for the instance in main
class linkedlist():
    def __init__(self):
        self.head = None
        self.data = 0
        self.size = 0
    def addnode(self,data):
        self.data = data
        new = node(data,self.head)
        self.head = new
        self.size +=1
    def __print__(self):
        cur = self.head
        while cur:
            print(str(cur.data),end = '>>')
            cur = cur.nextnode
        print('None')
    def swap_given_nodes(self,data1,data2):
        if data1 == data2:
            return True
        curx = self.head
        head = self.head
        cury = self.head
        prevx = None
        prevy = None
        while curx:
            if curx.data == data1:
                break
            prevx = curx
            curx = curx.nextnode
        print('para 1')
     
        while cury:
            if cury.data == data2:
                break
            prevy = cury
            cury = cury.nextnode
        if curx == None or cury == None:
            return False
        print('para 2')
        print(curx.data)
        print(cury.data)
     
        if prevx != None:
            prevx.nextnode = cury
        if prevy != None:
            prevy.nextnode = curx
        temp = curx.nextnode
     
        if curx == head:
            self.head = cury
        elif cury == head:
            self.head = curx
     
        curx.nextnode = cury.nextnode
        cury.nextnode = temp

if __name__ == '__main__':
    lis = linkedlist()
    for i in range(int(input('enter the number of elements to be inserted'))):
        lis.addnode(int(input('enter the value')))
    lis.__print__()
    print(lis.reccursive_length())
    #use the below line to use swap
    lis.swap_given_nodes(int(input('enter the second val')),int(input('enter the second val')))